Banyak buku telah ditulis khusus tentang teori struktur matematika yang disebut grup. Namun, untuk mempelajari teorema enumerasi Pólya, kita hanya memerlukan beberapa fakta tentang suatu kelas grup tertentu yang diperkenalkan dalam bagian ini. Ingat bahwa bijeksi dari suatu himpunan \(X\) ke dirinya sendiri disebut permutasi. Sebuah grup permutasi ialah himpunan \(P\) yang terdiri atas permutasi-permutasi suatu himpunan \(X\) sedemikian sehingga
permutasi identitas \(\iota\) berada dalam \(P\text{;}\)
Untuk keperluan kita, \(X\) selalu hingga dan biasanya kita ambil \(X=[n]\) untuk suatu bilangan bulat positif \(n\text{.}\) Grup simetris pada \(n\) elemen, yang dinyatakan dengan \(S_n\text{,}\) ialah himpunan seluruh permutasi \([n]\text{.}\) Setiap grup permutasi hingga (dan, secara lebih umum, setiap grup hingga) merupakan subgrup \(S_n\) untuk suatu bilangan bulat positif \(n\text{.}\)
Sebagai contoh pertama grup permutasi, perhatikan himpunan permutasi yang dibahas dalam Subbab 15.1, yang disebut grup dihedral persegi. Grup ini kita nyatakan dengan \(D_8\text{.}\) Grup transformasi serupa kita nyatakan dengan \(D_{2n}\) untuk segi-\(n\) beraturan; subskrip \(2n\) digunakan karena grup ini memuat \(2n\) permutasi. 1
Sebagian penulis dan sistem aljabar komputer menggunakan \(D_n\) sebagai notasi untuk grup dihedral segi-\(n\text{.}\)
Kriteria pertama grup permutasi jelas dipenuhi oleh \(D_8\text{.}\) Memeriksa kedua kriteria lainnya cukup melelahkan, sehingga kita hanya menyajikan beberapa contoh. Pertama, perhatikan bahwa \(r_2\circ r_1=r_3\text{.}\) Hal ini dapat ditentukan dengan melakukan komposisi fungsi-fungsi tersebut sebagai permutasi atau dengan memperhatikan bahwa rotasi \(90^\circ\) searah jarum jam yang diikuti rotasi \(180^\circ\) searah jarum jam sama dengan rotasi \(270^\circ\) searah jarum jam. Untuk \(v\circ r_1\text{,}\) kita memperoleh \(v\circ r_1(1) = 1\text{,}\)\(v\circ r_1(3)=3\text{,}\)\(v\circ r_1(2)=4\text{,}\) dan \(v\circ r_1(4)=2\text{,}\) sehingga \(v\circ r_1=n\text{.}\) Untuk invers, sebelumnya telah kita bahas bahwa \(r_1\inv = r_3\text{.}\) Selain itu, \(v\inv = v\text{,}\) dan secara lebih umum, invers dari setiap pencerminan ialah pencerminan itu sendiri.
Cara suatu permutasi menyusun ulang elemen-elemen \(X\) merupakan inti teorema enumerasi Pólya. Pemilihan representasi permutasi yang tepat sangat penting di sini, sehingga mari kita bahas cara menyatakan permutasi. Salah satu cara menyatakan permutasi \(\pi\) dari \([n]\) ialah sebagai matriks \(2\times n\text{.}\) Baris pertama menyatakan domain, sedangkan baris kedua menyatakan \(\pi\) dengan menempatkan \(\pi(i)\) pada posisi \(i\text{.}\) Sebagai contoh,
merupakan permutasi \([5]\) dengan \(\pi(1) =2\text{,}\)\(\pi(2)=4\text{,}\)\(\pi(3)=3\text{,}\)\(\pi(4) = 5\text{,}\) dan \(\pi(5) = 1\text{.}\) Notasi ini agak merepotkan dan hanya memberikan informasi paling dasar tentang permutasi. Notasi yang lebih ringkas (dan lebih berguna bagi keperluan kita) disebut notasi siklus. Salah satu cara memvisualisasikan pembentukan notasi siklus ialah dengan membangun digraf dari suatu permutasi \(\pi\) atas \([n]\text{.}\) Digraf tersebut mempunyai himpunan simpul \([n]\) dan sisi berarah dari \(i\) ke \(j\) jika dan hanya jika \(\pi(i) = j\text{.}\) (Di sini kita mengizinkan sisi berarah dari suatu simpul ke dirinya sendiri jika \(\pi(i) = i\text{.}\)) Digraf yang bersesuaian dengan permutasi \(\pi\) di atas ditunjukkan pada Gambar 15.3.
Karena \(\pi\) merupakan permutasi, setiap komponen digraf semacam itu berupa siklus berarah. Siklus-siklus ini dapat digunakan untuk menuliskan permutasi secara ringkas. Untuk setiap siklus, kita mulai dari simpul berlabel terkecil lalu mengelilingi siklus mengikuti arah sisi sambil menuliskan label-label simpul secara berurutan. Barisan bilangan bulat ini ditempatkan di dalam tanda kurung. Untuk siklus-\(4\) pada Gambar 15.3, kita memperoleh \((1245)\text{.}\) (Jika \(n\geq 10\text{,}\) kita menempatkan spasi atau koma di antara bilangan-bilangan bulat tersebut.) Komponen yang hanya memuat satu simpul cukup dinyatakan dengan \((3)\text{,}\) sehingga kita dapat menulis \(\pi=(1245)(3)\text{.}\) Berdasarkan konvensi, siklus-siklus saling lepas suatu permutasi didaftarkan sedemikian sehingga entri pertamanya berurutan naik.
Permutasi \(\pi=(1483)(27)(56)\) memenuhi \(\pi(1)=4\text{,}\)\(\pi(8)=3\text{,}\)\(\pi(3)=1\text{,}\) dan \(\pi(5)=6\text{.}\) Permutasi \(\pi'=(13)(2)(478)(56)\) memenuhi \(\pi'(1)=3\text{,}\)\(\pi'(2) = 2\text{,}\) dan \(\pi'(8)=4\text{.}\) Kita mengatakan bahwa \(\pi\) terdiri atas dua siklus dengan panjang \(2\) dan satu siklus dengan panjang \(4\text{.}\) Untuk \(\pi'\text{,}\) terdapat satu siklus dengan panjang \(1\text{,}\) dua siklus dengan panjang \(2\text{,}\) dan satu siklus dengan panjang \(3\text{.}\) Dalam bab ini, siklus dengan panjang \(k\) juga disebut siklus-\(k\text{.}\)
Karena operasi dalam suatu grup sembarang sering disebut perkalian, komposisi permutasi lazim disebut perkalian dan ditulis \(\pi_2\pi_1\text{,}\) bukan \(\pi_2\circ \pi_1\text{.}\) Namun, hal penting yang perlu diingat ialah bahwa operasi tersebut hanyalah komposisi fungsi. Mari kita lihat beberapa contoh.
Misalkan \(\pi_1 = (1234)\) dan \(\pi_2 = (12)(34)\text{.}\) (Perhatikan bahwa keduanya berturut-turut merupakan permutasi \(r_1\) dan \(v\) dari \(D_8\text{.}\)) Misalkan \(\pi_3=\pi_2\pi_1\text{.}\) Untuk menentukan \(\pi_3\text{,}\) mula-mula kita hitung \(\pi_3(1) = \pi_2\pi_1(1) = \pi_2(2) = 1\text{.}\) Selanjutnya, kita memperoleh \(\pi_3(2) = \pi_2\pi_1(2) = \pi_2(3)=4\text{.}\) Demikian pula, \(\pi_3(3) = 3\) dan \(\pi_3(4)=2\text{.}\) Jadi, \(\pi_3=(1)(24)(3)\text{,}\) yang sebelumnya kita sebut \(n\text{.}\)
Sekarang misalkan \(\pi_4 = \pi_1\pi_2\text{.}\) Maka \(\pi_4(1) = 3\text{,}\)\(\pi_4(2)=2\text{,}\)\(\pi_4(3)=1\text{,}\) dan \(\pi_4(4)=4\text{.}\) Oleh karena itu, \(\pi_4=(13)(2)(4)\text{,}\) yang sebelumnya kita sebut \(p\text{.}\) Penting untuk diperhatikan bahwa \(\pi_1\pi_2\neq \pi_2\pi_1\text{.}\) Hal ini semestinya tidak mengejutkan karena komposisi fungsi pada umumnya tidak komutatif. Untuk menggambarkan lebih lanjut ketidakkomutatifan grup permutasi, ambillah sebuah buku (Bukan buku ini! Anda masih perlu membaca petunjuk di sini.) dengan sampul menghadap ke atas dan punggung buku berada di kiri. Pertama, balik buku dari kiri ke kanan. Kemudian putar buku \(90^\circ\) searah jarum jam. Di mana letak punggung buku? Sekarang kembalikan buku ke posisi semula, dengan sampul menghadap ke atas dan punggung di kiri. Putar buku \(90^\circ\) searah jarum jam, lalu balik dari kiri ke kanan. Di mana letak punggung buku kali ini?
Menuliskan ke mana hasil kali dua (atau lebih) permutasi memetakan setiap elemen dengan cepat menjadi melelahkan. Pendekatan yang lebih efisien ialah menggambar digraf, lalu menuliskan struktur siklusnya. Namun, dengan sedikit latihan, Anda dapat membangun notasi siklus sambil melakukan perhitungan, seperti yang ditunjukkan dalam contoh berikut.
Misalkan \(\pi_1=(123)(487)(5)(6)\) dan \(\pi_2=(18765)(234)\text{.}\) Misalkan \(\pi_3 = \pi_2\pi_1\text{.}\) Untuk mulai membangun notasi siklus \(\pi_3\text{,}\) kita harus menentukan ke mana \(\pi_3\) memetakan \(1\text{.}\) Kita memperoleh bahwa elemen tersebut dipetakan ke \(3\text{,}\) sebab \(\pi_1\) memetakan \(1\) ke \(2\) dan \(\pi_2\) memetakan \(2\) ke \(3\text{.}\) Jadi, siklus pertama dimulai dengan \(13\text{.}\) Sekarang, ke mana \(3\) dipetakan? Elemen ini dipetakan ke \(8\text{,}\) lalu ke \(6\text{,}\) kemudian ke \(5\text{,}\) dan akhirnya ke \(1\text{.}\) Dengan demikian, siklus pertama lengkap sebagai \((13865)\text{.}\) Bilangan bulat pertama yang tidak berada dalam siklus ini ialah \(2\text{,}\) yang kita gunakan untuk memulai siklus berikutnya. Kita memperoleh bahwa \(2\) dipetakan ke \(4\text{,}\) kemudian ke \(7\text{,}\) lalu kembali ke \(2\text{.}\) Jadi, siklus kedua ialah \((247)\text{.}\) Sekarang seluruh \(8\) elemen telah terwakili dalam siklus-siklus tersebut, sehingga \(\pi_3 = (13865)(247)\text{.}\)
Mari kita tentukan \([(123456)][(165432)]\text{,}\) dengan kedua permutasi yang dikalikan ditulis di dalam tanda kurung siku. Karena kita bekerja dari kanan ke kiri, permutasi pertama yang diterapkan memetakan \(1\) ke \(6\text{,}\) sedangkan permutasi kedua memetakan \(6\) ke \(1\text{.}\) Jadi, siklus pertama ialah \((1)\text{.}\) Selanjutnya, kita memperoleh bahwa hasil kali tersebut memetakan \(2\) ke \(2\text{.}\) Hasil kali itu juga memetakan \(i\) ke \(i\) untuk setiap \(i\leq 6\) lainnya. Jadi, hasil kalinya ialah \((1)(2)(3)(4)(5)(6)\text{,}\) yang lebih dikenal sebagai permutasi identitas. Dengan demikian, \((123456)\) dan \((165432)\) saling invers.
Dalam bagian berikutnya, kita akan menggunakan teknik pencacahan standar yang telah dibahas sebelumnya untuk membuktikan hasil-hasil tentang grup yang bertindak pada himpunan. Kita akan menyatakan hasil tersebut untuk grup sembarang, tetapi Anda dapat mengganti “grup” dengan “grup permutasi” tanpa kehilangan pemahaman yang diperlukan untuk sisa bab ini.
