Mewarnai Kalung dengan Cauchy-Frobenius

1. Formula Cauchy-Frobenius

Misalkan grup {G} beraksi pada himpunan {\Omega}. Kita hendak menghitung banyaknya orbit dari aksi ini. Untuk setiap {g\in G} definisikan {\text{Fix}(g):=\{\alpha \in \Omega \mid \alpha\cdot g=\alpha\}} dan untuk setiap {\alpha \in \Omega} definisikan {G_\alpha:=\{g\in G\mid \alpha\cdot g=\alpha\}}.

Untuk menghitung banyaknya orbit dari aksi, pertama kita tinjau himpunan

\displaystyle  \mathcal{S}:=\{(\alpha,g)\mid \alpha\cdot g=\alpha\}

Kita akan menghitung banyaknya kardinalitas dari {\mathcal{S}}. Misalkan unsur-unsur di {\Omega} adalah {\alpha_1,\ldots, \alpha_s} dan unsur-unsur di {G} adalah {g_1,\ldots, g_t}. Definisikan matriks {M=(m_{ij})} dengan

\displaystyle  m_{ij}:=\begin{cases}1& \text{ jika } (\alpha_i,g_j)\in \mathcal{S}\\ 0&\text{ jika } (\alpha_i,g_j)\not\in \mathcal{S} \end{cases}

Banyaknya angka 1 pada baris ke-{i} adalah banyaknya {g\in G} sehingga {\alpha_i\cdot g=\alpha_i}, yakni {|G_{\alpha_i}|}. Sehingga banyaknya total angka 1 yang terdapat pada matriks {M} adalah

\displaystyle  \sum_{i=1}^s |G_{\alpha_i}|=\sum_{\alpha \in \Omega} |G_\alpha|.

Di lain pihak kita bisa menghitung banyaknya angka 1 pada {M} kolom-demi kolom. Banyaknya angka 1 pada kolom ke-{j} sama dengan banyaknya {i=1,\ldots,s} sehingga {(\alpha_i,g_j)\in S}, yakni sebesar {|\text{Fix}(g_i)|}. Dengan demikian banyaknya total angka 1 pada matriks {M} adalah

\displaystyle  \sum_{j=1}^t |\text{Fix}(g_j)|=\sum_{g\in G} |\text{Fix}(g)|.

Karena kedua hal di atas menghitung dua objek yang sama, maka

\displaystyle  \sum_{g\in G} |\text{Fix}(g)|=\sum_{\alpha \in \Omega} |G_\alpha|

Bagi kedua ruas dengan {|G|} kita peroleh

    \begin{align*} \frac{1}{|G|}\sum_{g\in G} |\text{Fix}(g)|&=\sum_{\alpha \in \Omega} \frac{|G_\alpha|}{|G|}\\ &=\sum_{\alpha \in \Omega} \frac{1}{|O_\alpha|} \end{align*}

Misalkan {O_1,O_2,\ldots, O_k} adalah orbit-orbit yang mempartisi {\Omega}. Maka

    \begin{align*} \sum_{\alpha \in \Omega} \frac{1}{|O_\alpha|}&=\sum_{i=1}^k \sum_{\alpha \in O_i} \frac{1}{|O_\alpha|}\\ &= \sum_{i=1}^k \frac{|O_i|}{|O_i|}\\ &=k\\ &= \text{banyaknya orbit} \end{align*}

Dengan demikian

\displaystyle  \text{banyaknya orbit }=\frac{1}{|G|}\sum_{g\in G} |\text{Fix}(g)|.

Berikut contoh aplikasi sederhana dari Teorema Cauchy-Frobenius yang dikenal juga sebagai Teorema Frobenius yang menurut beberapa matematikawan merupakan pengatributan yang keliru kepada Burnside.

Example 1 Misalkan kita ingin membuat kalung manik-manik yang terdiri dari 6 butiran manik-manik. Jenis manik-manik yang tersedia ada 2 warna, berwarna hitam dan putih. Kita ingin menghitung banyaknya cara membuat manik-manik seperti itu. Perhatikan bahwa dua kalung manik-manik kita anggap sama jika kita bisa merotasi kalung yang satu untuk mendapatkan konfigurasi manik-manik pada kalung kedua.

Kita tinjau himpunan semua warna kalung sebagai himpunan

\displaystyle C=\{(c_1,c_2,\ldots, c_6)\mid c_i=1 \text{ atau } c_i=0\}

dengan {c_i=1} jika manik-manik {i} berwarna hitam dan {c_i=0} jika manik-manik {i} berwarna putih. Himpunan semua rotasi pada 6 buah manik-manik bisa kita nyatakan sebagai grup {G=\langle \tau \rangle} dengan {\tau} adalah putaran {(1\,2\,3\,4\,5\,6)}. Perhatikan bahwa {G=\{\text{id},\tau,\tau^2\tau^3,\tau^4,\tau^5\}} dengan {\tau} bisa kita anggap juga sebagai rotasi sebesar {60^\circ} searah jarum jam.

Disini kita melihat bahwa {G} beraksi pada {C} dengan rotasi. Misalkan diberikan kalung dengan konfigurasi {c=(1,1,0,1,0,0)} maka semua hasil rotasi dari {c} dianggap sebagai konfigurasi kalung yang sama atau dengan kata lain mereka semua tinggal dalam satu orbit. Pewarnaan kalung yang berbeda menyatakan orbit yang lain. Dengan demikian yang kita cari adalah banyaknya orbit dari aksi {\langle \tau\rangle} terhadap {C}.

Kita akan menghitung banyaknya orbit ini dengan menggunakan Teorema Cauchy-Frobenius dengan cara menghitung {|\text{Fix}(\tau^i)|} untuk {i=0,1,2,3,4,5}.

  1. Pertama kita akan menghitung banyaknya unsur di {\text{Fix (id)}}. Oleh pemetaan {\text{id}} setiap {c\in C} dipetakan ke dirinya sendiri. Semua konfigurasi kalung yang mungkin merupakan anggota {\text{Fix(id)}}. Dengan {|\text{Fix (id)}|=|C|=2^6}.
  2. Oleh {\tau} konfigurasi {(c_1,c_2,c_3,c_4,c_5,c_6)} dibawa ke konfigurasi {(c_6,c_1,c_2,c_3,c_4,c_5)}. Dengan demikian {(c_1,\ldots,c_6)\in \text{Fix}(\tau)} jika {c_6=c_1} kemudian {c_1=c_2} dan seterusnya sehingga berturut-turut kita memiliki {c_6=c_1=c_2=c_3=c_4=c_5}. Dengan demikian pewarnaan kalung bergantung pada salah satu manik-manik saja, misal {c_1}. Banyaknya cara untuk mewarnai {c_1} dengan dua warna adalah {2^1} cara. Jadi {|\text{Fix}(\tau)|=2^1}. Dengan cara yang serupa, karena {\tau^5=\tau^{-1}} adalah rotasi 60 derajat berlawanan arah kita dapatkan pula {|\text{Fix}(\tau^5)|=2^1}.
  3. Jika {c\in \text{Fix}(\tau)} maka konfigurasi {(c_1,c_2,c_3,c_4,c_5,c_6)} haruslah sama dengan {(c_5,c_6,c_1,c_2,c_3,c_4)} dengan demikian {c_1=c_5=c_3} dan {c_2=c_4=c_6}. Jadi pewarnaan kalung ditentukan oleh warna {c_1} dan {c_2}. Ada {2^2} cara untuk mewarnai {c_1} dan {c_2}. Dengan demikian {|\text{Fix}(\tau^2)|=2^2}. Dengan cara yang sama {|\text{Fix}(\tau^4)|=|\text{Fix}(\tau^{-2})|=2^2}.
  4. Oleh {\tau^3}, {(c_1,c_2,c_3,c_4,c_5,c_6)} di petakan menjadi {(c_4,c_5,c_6,c_1,c_2,c_3)}. Jadi haruslah {c_1=c_4,c_2=c_5} dan {c_3=c_6}. Pewarnaan kalung ditentukan oleh pewarnaan {c_1,c_2,c_3}, Jadi {|\text{Fix}(\tau^3)|=2^3}.

Sekarang menurut Teorema Cauchy-Frobenius banyaknya pewarnaan kalung adalah

    \[  \frac{1}{6}\left(2^6+2^1+2^1+2^2+2^2+2^3\right)=14.\]

Jadi ada 14 konfigurasi kalung yang mungkin.

Leave a Reply

Your email address will not be published. Required fields are marked *