Sebelum sampai pada bentuk lengkap rumus Pólya, kita harus mengembangkan suatu fungsi pembangkit seperti yang dijanjikan pada awal bab. Untuk melakukannya, kita kembali ke contoh pada Subbab 15.1.
Berbeda dari fungsi-fungsi pembangkit yang ditemui dalam Bab 8, fungsi pembangkit yang akan kita kembangkan dalam bab ini mempunyai lebih dari satu variabel. Kita mulai dengan mengaitkan sebuah monomial dengan setiap elemen grup permutasi yang terlibat. Dalam kasus ini, grup tersebut ialah \(D_8\text{,}\) grup dihedral persegi. Untuk menentukan monomial yang berkaitan dengan suatu permutasi, kita perlu menuliskan permutasi tersebut dalam notasi siklus, lalu menentukan monomial berdasarkan banyak siklus dari setiap panjang. Secara khusus, jika \(\pi\) merupakan permutasi \([n]\) dengan \(j_k\) siklus yang panjangnya \(k\) untuk \(1\leq k\leq n\text{,}\) monomial yang berkaitan dengan \(\pi\) ialah \(x_1^{j_1}x_2^{j_2}\cdots x_n^{j_n}\text{.}\) Perhatikan bahwa \(j_1 + 2j_2 + 3j_3 + \cdots + nj_n = n\text{.}\) Sebagai contoh, permutasi \(r_1=(1234)\) berkaitan dengan monomial \(x_4^1\) karena terdiri atas satu siklus dengan panjang \(4\text{.}\) Permutasi \(r_2=(13)(24)\) mempunyai dua siklus dengan panjang \(2\text{,}\) sehingga monomialnya ialah \(x_2^2\text{.}\) Untuk \(p=(13)(2)(4)\text{,}\) terdapat dua siklus-\(1\) dan satu siklus-\(2\text{,}\) yang menghasilkan monomial \(x_1^2x_2^1\text{.}\) Dalam Gambar 15.10, ditampilkan seluruh delapan permutasi dalam \(D_8\) beserta monomial yang berkaitan dengannya.
Sekarang mari kita lihat bagaimana banyak pewarnaan-\(2\) persegi yang ditetapkan oleh suatu permutasi dapat ditentukan dari struktur siklus dan monomial yang berkaitan dengannya. Jika \(\pi(i)=j\text{,}\) agar \(\pi\) menetapkan suatu pewarnaan \(C\text{,}\) simpul \(i\) dan \(j\) harus mempunyai warna yang sama dalam \(C\text{.}\) Jadi, simpul kedua dalam suatu siklus harus berwarna sama dengan simpul pertama. Selanjutnya, simpul ketiga harus berwarna sama dengan simpul kedua, yang juga sama dengan warna simpul pertama. Bahkan, jika \(\pi\) menetapkan \(C\text{,}\) semua simpul yang muncul dalam satu siklus \(\pi\) harus mempunyai warna yang sama dalam \(C\text{!}\) Karena kita menggunakan dua warna, putih dan emas, titik-titik dalam setiap siklus dapat dipilih untuk diwarnai seluruhnya putih atau seluruhnya emas. Sebagai contoh, agar permutasi \(v=(12)(34)\) menetapkan suatu pewarnaan persegi, simpul \(1\) dan \(2\) harus berwarna sama (\(2\) pilihan), dan simpul \(3\) serta \(4\) harus berwarna sama (\(2\) pilihan). Jadi, terdapat \(2\cdot 2=4\) pewarnaan yang ditetapkan oleh \(v\text{.}\) Karena terdapat dua pilihan untuk mewarnai secara seragam elemen-elemen suatu siklus, substitusi \(x_i=2\) untuk setiap \(i\) dalam monomial yang berkaitan dengan \(\pi\) memberikan banyak pewarnaan yang ditetapkan oleh \(\pi\text{.}\) Dalam Gambar 15.10, kolom “Pewarnaan tetap” memberikan banyak pewarnaan-\(2\) persegi yang ditetapkan oleh setiap permutasi. Sebelumnya, kita memperoleh hasil ini secara manual dengan memperhatikan aksi \(D_8\) pada himpunan seluruh \(16\) pewarnaan. Sekarang kita hanya memerlukan notasi siklus dan monomial yang dihasilkannya!
Ingat bahwa Lemma Burnside menyatakan bahwa banyak pewarnaan yang ditetapkan oleh aksi suatu grup dapat diperoleh dengan menjumlahkan banyak pewarnaan yang ditetapkan oleh setiap permutasi, lalu membaginya dengan banyak permutasi dalam grup. Jika prosedur yang sama diterapkan pada monomial-monomial yang berasal dari permutasi dalam grup permutasi \(G\text{,}\) dengan setiap siklus dari setiap permutasi mempunyai paling banyak \(n\) entri, kita memperoleh polinomial yang disebut indeks siklus \(P_G(x_1,x_2,\dots,x_n)\text{.}\) Untuk contoh kita, diperoleh
Untuk menentukan banyak pewarnaan-\(2\) persegi yang berbeda, kita tetapkan \(x_i=2\) untuk setiap \(i\) dan kembali memperoleh \(P_{D_8}(2,2,2,2) = 6\text{.}\) Namun, perhatikan bahwa sekarang kita memiliki alat yang lebih kuat daripada lemma Burnside. Kita dapat menyubstitusikan sebarang bilangan bulat positif \(m\) untuk setiap \(x_i\) guna menentukan banyak pewarnaan-\(m\) persegi yang tidak ekuivalen. Kita tidak lagi perlu menganalisis banyak pewarnaan yang ditetapkan oleh setiap permutasi. Sebagai contoh, \(P_{D_8}(3,3,3,3) = 21\text{,}\) yang berarti bahwa \(21\) dari \(81\) pewarnaan simpul-simpul persegi menggunakan tiga warna merupakan pewarnaan yang berbeda.
Mudah-mudahan kekuatan indeks siklus untuk menghitung pewarnaan yang berbeda setelah simetri diperhitungkan mulai terlihat. Pada bagian berikutnya, kita akan memberikan contoh tambahan penggunaannya. Namun, kita masih belum melihat seluruh kekuatan teknik Pólya. Dari indeks siklus saja, kita dapat menentukan banyak pewarnaan simpul persegi yang berbeda. Akan tetapi, bagaimana jika kita ingin mengetahui berapa banyak di antaranya yang mempunyai dua simpul putih dan dua simpul emas? Di sinilah rumus enumerasi Pólya benar-benar berperan sebagai fungsi pembangkit.
Alih-alih menyubstitusikan bilangan bulat untuk \(x_i\text{,}\) mari kita perhatikan apa yang terjadi jika kita menyubstitusikan sesuatu yang memungkinkan warna-warna yang digunakan tetap terlacak. Karena \(x_1\) menyatakan siklus dengan panjang \(1\) dalam suatu permutasi, pemilihan putih atau emas untuk simpul dalam siklus semacam itu berarti satu simpul menerima warna tersebut. Apa yang terjadi jika \(w+g\) disubstitusikan untuk \(x_1\text{?}\) Suku pertama dalam \(P_{D_8}\) bersesuaian dengan permutasi identitas \(\iota\text{,}\) yang menetapkan semua pewarnaan persegi. Menetapkan \(x_1=w+g\) dalam suku tersebut menghasilkan
yang memberi tahu kita bahwa \(\iota\) menetapkan satu pewarnaan dengan empat simpul emas, empat pewarnaan dengan tiga simpul emas dan satu simpul putih, enam pewarnaan dengan dua simpul emas dan dua simpul putih, empat pewarnaan dengan satu simpul emas dan tiga simpul putih, serta satu pewarnaan dengan empat simpul putih.
Mari kita lanjutkan pola ini dengan memperhatikan variabel \(x_2\text{.}\) Variabel tersebut menyatakan siklus-siklus dengan panjang \(2\) dalam suatu permutasi. Agar ditetapkan oleh permutasi, siklus semacam itu harus diwarnai secara seragam dengan putih atau emas. Jadi, pemilihan putih atau emas untuk simpul-simpul dalam siklus menghasilkan dua simpul putih atau dua simpul emas dalam pewarnaan. Karena hal ini terjadi pada setiap siklus dengan panjang \(2\text{,}\) kita menyubstitusikan \(w^2+g^2\) untuk \(x_2\) dalam indeks siklus. Suku-suku \(x_1^2x_2^1\) dalam \(P_{D_8}\) berkaitan dengan pencerminan \(p\) dan \(n\text{.}\) Dengan menetapkan \(x_1=w+g\) dan \(x_2 = w^2+g^2\text{,}\) diperoleh
Dari sini kita dapat menyimpulkan bahwa \(p\) dan \(n\) masing-masing menetapkan satu pewarnaan dengan empat simpul emas, dua pewarnaan dengan tiga simpul emas dan satu simpul putih, dan seterusnya. Perbandingan dengan Gambar 15.2 menunjukkan bahwa fungsi pembangkit tersebut tepat.
Sekarang polanya mulai terlihat. Jika kita menyubstitusikan \(w^i+g^i\) untuk \(x_i\) dalam indeks siklus bagi setiap \(i\text{,}\) banyak simpul yang diwarnai putih dan banyak simpul yang diwarnai emas dapat tetap dilacak. Penyederhanaan indeks siklus dalam hal ini menghasilkan fungsi pembangkit yang koefisien \(g^s w^t\)-nya merupakan banyak pewarnaan berbeda pada simpul-simpul persegi dengan \(s\) simpul berwarna emas dan \(t\) simpul berwarna putih. Substitusi dan penyederhanaan tersebut memberikan
Dari hasil ini, kita memperoleh satu pewarnaan dengan semua simpul emas, satu pewarnaan dengan semua simpul putih, satu pewarnaan dengan tiga simpul emas dan satu simpul putih, satu pewarnaan dengan satu simpul emas dan tiga simpul putih, serta dua pewarnaan dengan dua simpul dari setiap warna.
Seperti hasil-hasil lain yang ditemukan dalam bab ini, sifat indeks siklus tersebut berlaku lebih luas daripada sekadar pewarnaan simpul persegi dengan dua warna. Bentuk lengkapnya ialah teorema enumerasi Pólya:
Misalkan \(S\) merupakan himpunan dengan \(|S|=r\) dan \(\cgC\) merupakan himpunan pewarnaan \(S\) menggunakan warna \(c_1,\dots,c_m\text{.}\) Jika suatu grup permutasi \(G\) bertindak pada \(S\) sehingga menginduksi relasi ekuivalensi pada \(\cgC\text{,}\) maka
Jika kita kembali mewarnai simpul-simpul persegi, tetapi sekarang juga mengizinkan warna biru, diperoleh
\begin{equation*}
P_{D_8}(w+g+b,w^2+g^2+b^2,w^3+g^3+b^3,w^4+g^4+b^4) = b^4+b^3 g+2 b^2 g^2\\+b g^3+g^4+b^3 w+2 b^2 g w+2 b g^2 w+g^3 w+2 b^2 w^2+2 b g w^2+2 g^2 w^2\\+b w^3+g w^3+w^4.
\end{equation*}
Dari fungsi pembangkit ini, kita segera menentukan bahwa terdapat \(2\) pewarnaan tak ekuivalen dengan dua simpul biru, satu simpul emas, dan satu simpul putih. Karena fungsi pembangkit dalam Teorema Enumerasi Pólya mencatat banyak pola tak ekuivalen, fungsi itu kadang-kadang disebut inventaris pola.
Bagaimana jika kita ingin membuat kalung dengan \(500\) manik-manik (yang sangat kecil) berwarna putih, emas, dan biru? Hal ini ekuivalen dengan mewarnai simpul-simpul segi-\(500\) beraturan, dan grup dihedral \(D_{1000}\) memberikan transformasi yang sesuai. Dengan sistem aljabar komputer 1
Dengan pengalaman tambahan dalam teori grup, kita dapat memberikan rumus umum untuk indeks siklus grup dihedral \(D_{2n}\text{.}\) Jadi, sistem aljabar komputer merupakan alat yang berguna, tetapi tidak wajib.
seperti Mathematica®, inventaris pola untuk persoalan semacam itu dapat dihasilkan dengan cepat. Dari perhitungan tersebut, terdapat
