Subbab 15.5 Penerapan Rumus Enumerasi Pólya

Musik Barat pada umumnya didasarkan pada sistem \(12\) nada yang berjarak sama. Meskipun nada-nada ini biasanya dinamai dengan huruf alfabet (beserta tanda pengubah), untuk keperluan kita cukup diberi nomor \(0,1,\dots,11\text{.}\) Nada-nada tersebut disusun dalam oktaf sehingga tinggi nada sesudah \(11\) kembali dinamai \(0\text{,}\) sedangkan tinggi nada sebelum \(0\) dinamai \(11\text{.}\) Karena itu, sistem nada tersebut dapat dipandang bersesuaian dengan bilangan bulat modulo \(12\text{.}\) Dengan definisi ini, tangga nada ialah himpunan bagian dari \(\{0,1,\dots,11\}\) yang disusun dalam urutan naik. Transposisi tangga nada ialah transformasi seragam yang mengganti setiap nada \(x\) dalam tangga nada dengan \(x+a\pmod{12}\) untuk suatu konstanta \(a\text{.}\) Musisi menganggap dua tangga nada ekuivalen jika salah satunya merupakan transposisi dari yang lain. Karena tangga nada merupakan himpunan bagian, nada mana yang memulai tangga nada juga tidak diperhitungkan. Pertanyaan yang kita selidiki dalam bagian ini ialah “Berapa banyak tangga nada tak ekuivalen yang masing-masing terdiri atas tepat \(k\) nada?”

Karena penamaan nada bersifat siklis, kita dapat menyusunnya berurutan searah jarum jam mengelilingi sebuah lingkaran. Pemilihan nada untuk tangga nada lalu menjadi persoalan pewarnaan jika nada terpilih diberi warna hitam dan nada yang tidak terpilih diberi warna putih. Dalam Gambar 15.12, ditampilkan tiga tangga nada yang masing-masing terdiri atas \(5\) nada dengan konvensi ini. Perhatikan bahwa \(S_2\) dapat diperoleh dari \(S_1\) dengan memutarnya maju tujuh posisi. Karena itu, \(S_1\) dan \(S_2\) ekuivalen melalui transposisi penambahan \(7\text{.}\) Namun, \(S_3\) tidak ekuivalen dengan \(S_1\) ataupun \(S_2\) karena tidak dapat diperoleh dari keduanya melalui rotasi. (Perhatikan bahwa \(S_3\) dapat diperoleh dari \(S_1\) jika pencerminan diizinkan selain rotasi. Karena satu-satunya operasi yang diizinkan ialah transposisi, yang bersesuaian dengan rotasi, keduanya tidak ekuivalen.)

Benzena merupakan senyawa kimia dengan rumus \(\text{C} _6\text{H} _6\text{,}\) yang berarti senyawa itu terdiri atas enam atom karbon dan enam atom hidrogen. Atom-atom tersebut berikatan sedemikian sehingga keenam atom karbon membentuk cincin heksagonal dengan ikatan tunggal dan rangkap yang berselang-seling. Satu atom hidrogen terikat pada setiap atom karbon (di bagian luar cincin). Dari benzena dapat dibentuk senyawa kimia lain yang termasuk dalam keluarga hidrokarbon aromatik. Senyawa-senyawa ini dibentuk dengan mengganti satu atau lebih atom hidrogen dengan atom unsur lain atau gugus fungsi seperti \(\text{CH} _3\) (gugus metil) atau \(\text{OH}\) (gugus hidroksil). Karena terdapat enam pilihan atom hidrogen yang akan diganti, cara ini dapat menghasilkan molekul dengan rumus kimia yang sama tetapi struktur berbeda. Molekul semacam itu disebut isomer. Dalam subbagian ini, kita akan melihat bagaimana Teorema Enumerasi Pólya dapat digunakan untuk menentukan banyak isomer hidrokarbon aromatik xilenol (juga dikenal sebagai dimetilfenol).

Sebelum membahas struktur molekul xilenol, kita perlu membahas grup permutasi yang bertindak pada cincin benzena. Seperti pada contoh pewarnaan simpul persegi, di sini terdapat rotasi dan pencerminan. Grup yang diperlukan ialah grup dihedral segi enam, \(D_{12}\text{.}\) Jika keenam atom karbon diberi nomor \(1,2,\dots,6\) dalam urutan searah jarum jam, rotasi \(60^\circ\) searah jarum jam bersesuaian dengan permutasi \(r=(123456)\text{.}\) Rotasi lainnya merupakan pangkat-pangkat \(r\) yang lebih tinggi, seperti ditunjukkan dalam Gambar 15.13. Pencerminan terhadap sumbu vertikal merupakan permutasi \(f=(16)(25)(34)\text{.}\) Semua elemen \(D_{12}\) lainnya (selain identitas \(\iota\)) dapat dinyatakan sebagai suatu rotasi yang diikuti pencerminan ini. Daftar lengkap permutasi ditampilkan dalam Gambar 15.13; setiap permutasi disertai monomial yang disumbangkannya kepada indeks siklus.

Dalam makalah aslinya, Pólya menggunakan tekniknya untuk menghitung banyak isomer alkana \(\text{C} _n\text{H} _{2n+2}\text{.}\) Jika dimodelkan sebagai graf, senyawa kimia tersebut merupakan jenis pohon khusus. Sejak saat itu, Teorema Enumerasi Pólya telah digunakan untuk menghitung isomer berbagai senyawa kimia.

Persoalan yang lebih sulit muncul ketika kita ingin menghitung graf tak isomorfik pada \(n\) simpul. (Graf tersebut juga dapat dipandang sebagai graf tak berlabel.) Sebagai contoh, Gambar 15.14 menampilkan empat graf berlabel yang berbeda pada empat simpul. Namun, ketiga graf pertama di sana saling isomorfik. Jadi, gambar tersebut hanya memperlihatkan dua graf tak isomorfik pada empat simpul. Untuk memperhitungkan isomorfisme, kita perlu menggunakan Teorema Enumerasi Pólya.

Kita mulai dengan memperhatikan seluruh \(2^{C(n,2)}\) graf dengan himpunan simpul \([n]\) dan memilih grup permutasi yang sesuai untuk bertindak dalam situasi ini. Agar tetap mudah dikelola, kita menggunakan contoh \(n=4\text{,}\) tetapi seluruh metodenya dapat digeneralisasi. Karena setiap simpul dapat dipetakan ke simpul lain mana pun, grup simetris \(S_4\) bertindak pada simpul-simpul tersebut. Namun, kita harus berhati-hati dalam menentukan indeks siklusnya. Ketika bekerja dengan pewarnaan simpul-simpul persegi, kita mengetahui bahwa semua simpul yang muncul dalam siklus yang sama dari permutasi \(\pi\) harus diberi warna yang sama. Karena sekarang yang diperhatikan ialah sisi, bukan pewarnaan simpul, syarat agar suatu permutasi menetapkan sebuah graf ialah setiap sisi dipetakan ke sisi dan setiap bukan-sisi dipetakan ke bukan-sisi. Secara khusus, jika \(\{1,2\}\) merupakan sisi suatu \(\bfG\) dan \(\pi\in S_4\) menetapkan \(\bfG\text{,}\) maka \(\{\pi(1),\pi(2)\}\) juga harus merupakan sisi \(\bfG\text{.}\) Demikian pula, jika simpul \(3\) dan \(4\) tidak bertetangga dalam \(\bfG\text{,}\) maka \(\pi(3)\) dan \(\pi(4)\) juga harus tidak bertetangga dalam \(\bfG\text{.}\)

Untuk memperhitungkan sisi, kita beralih dari grup simetris \(S_4\) ke grup pasangan \(S_4^{(2)}\text{.}\) Objek yang dipermutasikan oleh \(S_4^{(2)}\) ialah himpunan-himpunan bagian beranggotakan \(2\) dari \(\{1,2,3,4\}\text{.}\) Agar notasinya mudah, himpunan bagian beranggotakan \(2\text{,}\) yaitu \(\{i,j\}\text{,}\) kita nyatakan dengan \(e_{ij}\text{.}\) Untuk mencari permutasi dalam \(S_4^{(2)}\text{,}\) kita memperhatikan permutasi simpul dalam \(S_4\) dan melihat bagaimana permutasi tersebut menyusun ulang \(e_{ij}\text{.}\) Permutasi identitas \(\iota=(1)(2)(3)(4)\) dalam \(S_4\) bersesuaian dengan permutasi identitas \(\iota=(e_{12})(e_{13}) (e_{14}) (e_{23}) (e_{24}) (e_{34})\) dalam \(S_4^{(2)}\text{.}\) Sekarang perhatikan permutasi \((12)(3)(4)\text{.}\) Permutasi ini menetapkan \(e_{12}\) karena memetakan \(1\) ke \(2\) dan \(2\) ke \(1\text{.}\) Permutasi ini juga menetapkan \(e_{34}\) dengan menetapkan \(3\) dan \(4\text{.}\) Namun, permutasi tersebut menukar \(e_{13}\) dengan \(e_{23}\) (\(3\) ditetapkan, sedangkan \(1\) ditukar dengan \(2\)) dan menukar \(e_{14}\) dengan \(e_{24}\) (\(1\) dipetakan ke \(2\text{,}\) sedangkan \(4\) ditetapkan). Jadi, permutasi pasangan yang bersesuaian ialah \((e_{12})(e_{13}e_{23})(e_{14}e_{24})(e_{34})\text{.}\) Sebagai contoh lain, perhatikan permutasi \((123)(4)\text{.}\) Permutasi ini bersesuaian dengan \((e_{12}e_{23}e_{13})(e_{14}e_{24}e_{34})\) dalam \(S_4^{(2)}\text{.}\)

Karena kita hanya mencari indeks siklus \(S_4^{(2)}\text{,}\) tidak perlu ditentukan seluruh \(24\) permutasi dalam grup pasangan. Namun, kita perlu mengetahui jenis permutasi tersebut berdasarkan panjang siklus agar dapat mengaitkan monomial yang sesuai. Dalam contoh-contoh yang telah diperhatikan, struktur siklus permutasi dalam grup pasangan tidak bergantung pada permutasi asalnya dalam \(S_4\) selain pada struktur siklusnya. Setiap permutasi dalam \(S_4\) yang terdiri atas satu siklus-\(2\) dan dua siklus-\(1\) bersesuaian dengan permutasi yang mempunyai dua siklus-\(2\) dan dua siklus-\(1\) dalam \(S_4^{(2)}\text{.}\) Permutasi dalam \(S_4\) dengan satu siklus-\(3\) dan satu siklus-\(1\) bersesuaian dengan permutasi yang mempunyai dua siklus-\(3\) dalam grup pasangan. Dengan memperhatikan contoh permutasi dalam \(S_4\) yang terdiri atas satu siklus-\(4\text{,}\) kita memperoleh bahwa permutasi yang bersesuaian dalam grup pasangan mempunyai satu siklus-\(4\) dan satu siklus-\(2\text{.}\) Terakhir, permutasi \(S_4\) yang terdiri atas dua siklus-\(2\) bersesuaian dengan permutasi dalam \(S_4^{(2)}\) yang mempunyai dua siklus-\(2\) dan dua siklus-\(1\text{.}\) (Latihan 15.6.8 meminta Anda memverifikasi pernyataan-pernyataan ini dengan permutasi tertentu.)

Setelah mengetahui struktur siklus permutasi dalam \(S_4^{(2)}\text{,}\) satu-satunya tugas yang tersisa sebelum menentukan indeks siklusnya ialah menghitung banyak permutasi yang mempunyai setiap struktur siklus yang mungkin. Untuk itu, kita kembali memperhatikan permutasi dalam grup simetris \(S_4\text{.}\) Permutasi yang terdiri atas satu siklus-\(4\) dimulai dengan \(1\text{,}\) lalu memuat \(2\text{,}\) \(3\text{,}\) dan \(4\) dalam salah satu dari \(3!=6\) urutan yang mungkin. Jadi, terdapat \(6\) permutasi semacam itu. Untuk permutasi yang terdiri atas satu siklus-\(1\) dan satu siklus-\(3\text{,}\) terdapat \(4\) cara memilih elemen bagi siklus-\(1\text{,}\) lalu \(2\) cara menyusun tiga elemen lainnya sebagai siklus-\(3\text{.}\) (Ingat bahwa elemen terkecil harus ditempatkan pertama, sehingga terdapat \(2\) cara menyusun dua elemen sisanya.) Jadi, terdapat \(8\) permutasi semacam itu. Untuk permutasi yang terdiri atas dua siklus-\(1\) dan satu siklus-\(2\text{,}\) terdapat \(C(4,2)=6\) cara memilih dua elemen bagi siklus-\(2\text{.}\) Jadi, terdapat \(6\) permutasi semacam itu. Agar suatu permutasi terdiri atas dua siklus-\(2\text{,}\) terdapat \(C(4,2)=6\) cara memilih dua elemen bagi siklus-\(2\) pertama. Dua elemen lainnya lalu ditempatkan dalam siklus-\(2\) kedua. Namun, cara ini menghitung setiap permutasi dua kali: sekali ketika siklus-\(2\) pertama merupakan pasangan terpilih dan sekali ketika siklus itu merupakan “dua elemen lainnya.” Jadi, terdapat \(3\) permutasi yang terdiri atas dua siklus-\(2\text{.}\) Terakhir, hanya \(\iota\) yang terdiri atas empat siklus-\(1\text{.}\)