Lema 14.3.2.
Misalkan \(X\) adalah himpunan-\(G\) dan misalkan \(x \sim y\text{.}\) Maka \(G_x\) isomorfik dengan \(G_y\text{.}\) Secara khusus, \(|G_x| = |G_y|\text{.}\)
Bagian 14.3 Teorema Pencacahan Burnside
Misalkan kita ingin mewarnai titik-titik sudut suatu persegi dengan dua warna berbeda, misalnya hitam dan putih. Kita mungkin menduga bahwa terdapat \(2^4=16\) pewarnaan yang berbeda. Namun, sebagian pewarnaan tersebut ekuivalen. Jika kita mewarnai titik sudut pertama dengan hitam dan titik-titik sudut lainnya dengan putih, hasilnya sama dengan mewarnai titik sudut kedua dengan hitam dan yang lainnya dengan putih, sebab pewarnaan kedua dapat diperoleh hanya dengan memutar persegi tersebut sebesar \(90^\circ\) (Gambar 14.3.1).
Teorema Pencacahan Burnside memberikan metode untuk menghitung banyaknya cara yang dapat dibedakan dalam melakukan sesuatu. Selain penerapan geometrisnya, teorema ini memiliki penerapan menarik dalam teori pensakelaran dan kimia. Pembuktian Teorema Pencacahan Burnside bergantung pada lema berikut.
Bukti.
Misalkan \(G\) beraksi pada \(X\) melalui \((g,x) \mapsto g \cdot x\text{.}\) Karena \(x \sim y\text{,}\) terdapat \(g \in G\) sedemikian sehingga \(g \cdot x=y\text{.}\) Misalkan \(a \in G_x\text{.}\) Karena
\begin{equation*}
gag^{-1} \cdot y = ga \cdot g^{-1}y = ga \cdot x = g \cdot x = y\text{,}
\end{equation*}
kita dapat mendefinisikan pemetaan \(\phi: G_x \rightarrow G_y\) dengan \(\phi(a) = gag^{-1}\text{.}\) Pemetaan \(\phi\) merupakan homomorfisma karena
\begin{equation*}
\phi(ab) = gabg^{-1} = gag^{-1} gbg^{-1} = \phi(a) \phi(b)\text{.}
\end{equation*}
Misalkan \(\phi(a) = \phi(b)\text{.}\) Maka \(gag^{-1}= gbg^{-1}\) atau \(a=b\text{;}\) jadi, pemetaan tersebut injektif. Untuk menunjukkan bahwa \(\phi\) surjektif, misalkan \(b\) berada dalam \(G_y\text{;}\) maka \(g^{-1}bg\) berada dalam \(G_x\) karena
\begin{equation*}
g^{-1}bg \cdot x = g^{-1}b \cdot gx = g^{-1}b \cdot y = g^{-1} \cdot y = x;
\end{equation*}
dan \(\phi(g^{-1}bg ) = b\text{.}\)
Teorema 14.3.3. Burnside.
Misalkan \(G\) adalah grup hingga yang beraksi pada suatu himpunan \(X\) dan misalkan \(k\) menyatakan banyaknya orbit \(X\text{.}\) Maka
\begin{equation*}
k = \frac{1}{|G|} \sum_{g \in G} |X_g|\text{.}
\end{equation*}
Bukti.
Kita meninjau semua titik tetap \(x\) dari semua unsur \(g \in G\text{;}\) artinya, kita meninjau semua \(g\) dan semua \(x\) sedemikian sehingga \(gx =x\text{.}\) Jika dipandang dari segi himpunan titik tetap, banyaknya semua \(g\) yang menetapkan \(x\) adalah
\begin{equation*}
\sum_{g \in G} |X_g|\text{.}
\end{equation*}
Namun, jika dipandang dari segi subgrup penstabil, bilangan ini adalah
\begin{equation*}
\sum_{x \in X} |G_x|;
\end{equation*}
jadi, \(\sum_{g \in G} |X_g| = \sum_{x \in X} |G_x|\text{.}\) Berdasarkan Lema 14.3.2,
\begin{equation*}
\sum_{y \in {\mathcal O}_x} |G_y| = | {\mathcal O}_x| \cdot |G_x|\text{.}
\end{equation*}
Berdasarkan Teorema 14.1.11 dan Teorema Lagrange, ekspresi ini sama dengan \(|G|\text{.}\) Dengan menjumlahkan atas semua \(k\) orbit yang berbeda, kita menyimpulkan bahwa
\begin{equation*}
\sum_{g \in G} |X_g| = \sum_{x \in X} |G_x| = k \cdot |G|\text{.}
\end{equation*}
Contoh 14.3.4.
Misalkan \(X = \{1, 2, 3, 4, 5 \}\) dan misalkan \(G\) adalah grup permutasi \(G= \{(1), (1 \, 3), (1 \, 3)(2 \, 5), (2 \, 5) \}\text{.}\) Orbit-orbit \(X\) adalah \(\{1, 3\}\text{,}\) \(\{2, 5\}\text{,}\) dan \(\{4\}\text{.}\) Himpunan-himpunan titik tetapnya adalah
\begin{align*}
X_{(1)} & = X\\
X_{(1 \, 3)} & = \{2, 4, 5 \}\\
X_{(1 \, 3)(2 \, 5)} & = \{4\}\\
X_{(2 \, 5)} & = \{1, 3, 4 \}\text{.}
\end{align*}
Teorema Burnside menyatakan bahwa
\begin{equation*}
k = \frac{1}{|G|} \sum_{g \in G} |X_g| = \frac{1}{4}(5 + 3 + 1 + 3) = 3\text{.}
\end{equation*}
Subbagian 14.3.1 Contoh Geometris
Sebelum kita menerapkan Teorema Burnside pada masalah teori pensakelaran, mari kita periksa banyaknya cara titik-titik sudut suatu persegi dapat diwarnai hitam atau putih. Perhatikan bahwa terkadang kita dapat memperoleh pewarnaan yang ekuivalen hanya dengan menerapkan gerak kaku pada persegi tersebut. Sebagai contoh, seperti telah kita tunjukkan, jika salah satu titik sudut kita warnai hitam dan tiga lainnya putih, titik sudut mana yang diwarnai hitam tidaklah penting karena suatu rotasi akan menghasilkan pewarnaan yang ekuivalen.
Grup simetri suatu persegi, \(D_4\text{,}\) diberikan oleh permutasi-permutasi berikut:
\begin{align*}
&(1) & &(1 \, 3) & & (2 \, 4) & & (1 \, 4 \, 3 \, 2)\\
&(1 \, 2 \, 3 \, 4) & &(1 \, 2)(3 \, 4) & & (1 \, 4)(2 \, 3) & & (1 \, 3)(2 \, 4)
\end{align*}
Grup \(G\) beraksi pada himpunan titik sudut \(\{ 1, 2, 3, 4\}\) dengan cara biasa. Kita dapat mendeskripsikan pewarnaan-pewarnaan yang berbeda melalui pemetaan dari \(X\) ke \(Y = \{ H, P \}\text{,}\) dengan \(H\) dan \(P\) masing-masing merepresentasikan warna hitam dan putih. Setiap pemetaan \(f : X \rightarrow Y\) mendeskripsikan suatu cara mewarnai sudut-sudut persegi. Setiap \(\sigma \in D_4\) menginduksi suatu permutasi \(\widetilde{ \sigma }\) pada semua pewarnaan yang mungkin, yang diberikan oleh \(\widetilde{\sigma}(f) = f \circ \sigma\) untuk \(f : X \rightarrow Y\text{.}\) Sebagai contoh, misalkan \(f\) didefinisikan oleh
\begin{align*}
f(1) & = B\\
f(2) & = W\\
f(3) & = W\\
f(4) & = W
\end{align*}
dan \(\sigma = (1 2)(3 4)\text{.}\) Maka \(\widetilde{\sigma}(f) = f \circ \sigma\) memetakan titik sudut \(2\) ke \(H\) dan titik-titik sudut lainnya ke \(P\text{.}\) Himpunan semua \(\widetilde{\sigma}\) semacam ini merupakan grup permutasi \(\widetilde{G}\) pada himpunan semua pewarnaan yang mungkin. Misalkan \(\widetilde{X}\) menyatakan himpunan semua pewarnaan yang mungkin; yaitu, \(\widetilde{X}\) adalah himpunan semua pemetaan yang mungkin dari \(X\) ke \(Y\text{.}\) Sekarang kita harus menghitung banyaknya kelas ekuivalensi-\(\widetilde{G}\text{.}\)
-
\(\widetilde{X}_{(1)} = \widetilde{X}\) karena identitas menetapkan setiap pewarnaan yang mungkin. \(|\widetilde{X}| = 2^4 =~16\text{.}\)
-
\(\widetilde{X}_{(1 \, 2 \, 3 \, 4)}\) terdiri atas semua \(f \in \widetilde{X}\) sedemikian sehingga \(f\) tidak berubah oleh permutasi \((1 \, 2 \, 3 \, 4)\text{.}\) Dalam kasus ini \(f(1) = f(2) = f(3) = f(4)\text{,}\) sehingga semua nilai \(f\) harus sama; yaitu, \(f(x)= B\) atau \(f(x)= W\) untuk setiap titik sudut \(x\) dari persegi tersebut. Jadi, \(|\widetilde{X}_{(1 \, 2 \, 3 \, 4)}| = 2\text{.}\)
-
\(|\widetilde{X}_{(1 \, 4 \, 3 \, 2)}| = 2\text{.}\)
-
Untuk \(\widetilde{X}_{(1 \, 3)(2 \, 4)}\text{,}\) \(f(1) = f(3)\) dan \(f(2) = f(4)\text{.}\) Jadi, \(|\widetilde{X}_{(1 \, 3)(2 \, 4)}| = 2^2 = 4\text{.}\)
-
\(|\widetilde{X}_{(1 \, 2)(3 \, 4)}| = 4\text{.}\)
-
\(|\widetilde{X}_{(1 \, 4)(2 \, 3)}| = 4\text{.}\)
-
Untuk \(\widetilde{X}_{(1 \, 3 )}\text{,}\) \(f(1) = f(3)\) dan sudut-sudut lainnya dapat memiliki warna sebarang; jadi, \(|\widetilde{X}_{(1 \, 3)}| = 2^3 = 8\text{.}\)
-
\(|\widetilde{X}_{(2 \, 4)}| = 8\text{.}\)
Berdasarkan Teorema Burnside, kita dapat menyimpulkan bahwa terdapat tepat
\begin{equation*}
\frac{1}{8} ( 2^4 + 2^1 + 2^2 + 2^1 + 2^2 + 2^2 +2^3 + 2^3) = 6
\end{equation*}
cara untuk mewarnai titik-titik sudut persegi tersebut.
Proposisi 14.3.5.
Misalkan \(G\) adalah grup permutasi dari \(X\) dan \(\widetilde{X}\) adalah himpunan fungsi dari \(X\) ke \(Y\text{.}\) Maka \(G\) menginduksi suatu grup \(\widetilde{G}\) yang mempermutasikan unsur-unsur \(\widetilde{X}\text{,}\) dengan \(\widetilde{\sigma} \in \widetilde{G}\) didefinisikan oleh \(\widetilde{\sigma}(f) = f \circ \sigma\) untuk \(\sigma \in G\) dan \(f \in \widetilde{X}\text{.}\) Lebih lanjut, jika \(n\) adalah banyaknya siklus dalam dekomposisi siklus \(\sigma\text{,}\) maka \(|\widetilde{X}_{\sigma}| = |Y|^n\text{.}\)
Bukti.
Misalkan \(\sigma \in G\) dan \(f \in \widetilde{X}\text{.}\) Karena \(\sigma\) mempermutasikan unsur-unsur \(X\text{,}\) \(f \circ \sigma\) juga harus berada dalam \(\widetilde{X}\text{.}\) Misalkan \(g\) adalah fungsi lain dari \(X\) ke \(Y\) sedemikian sehingga \(\widetilde{\sigma}(f) = \widetilde{\sigma}(g)\text{.}\) Maka untuk setiap \(x \in X\text{,}\)
\begin{equation*}
f( \sigma(x )) = \widetilde{\sigma}(f)(x) = \widetilde{\sigma}(g)(x) = g( \sigma(x ))\text{.}
\end{equation*}
Karena \(\sigma\) merupakan permutasi dari \(X\text{,}\) setiap unsur \(x'\) dalam \(X\) adalah citra suatu \(x\) dalam \(X\) di bawah \(\sigma\text{;}\) jadi, \(f\) dan \(g\) sama pada semua unsur \(X\text{.}\) Oleh karena itu, \(f=g\) dan \(\widetilde{\sigma}\) injektif. Pemetaan \(\sigma \mapsto \widetilde{\sigma}\) surjektif, karena kedua himpunan memiliki ukuran yang sama.
Misalkan \(\sigma\) adalah permutasi dari \(X\) dengan dekomposisi siklus \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_n\text{.}\) Setiap \(f\) dalam \({\widetilde{X}}_{\sigma}\) harus memiliki nilai yang sama pada setiap siklus \(\sigma\text{.}\) Karena terdapat \(n\) siklus dan \(|Y|\) nilai yang mungkin untuk setiap siklus, \(|{\widetilde{X}}_{\sigma}| = |Y|^n\text{.}\)
Contoh 14.3.6.
Misalkan \(X = \{1, 2, \ldots, 7\}\) dan misalkan \(Y = \{ A, B, C \}\text{.}\) Jika \(g\) adalah permutasi dari \(X\) yang diberikan oleh \((1 \, 3)(2 \, 4 \, 5) = (1 \, 3)(2 \, 4 \, 5)(6)(7)\text{,}\) maka \(n = 4\text{.}\) Setiap \(f \in \widetilde{X}_g\) harus memiliki nilai yang sama pada setiap siklus dalam \(g\text{.}\) Terdapat \(|Y|=3\) pilihan semacam itu untuk setiap nilai, sehingga \(|\widetilde{X}_g| = 3^4 = 81\text{.}\)
Contoh 14.3.7.
Misalkan kita ingin mewarnai titik-titik sudut suatu persegi dengan empat warna berbeda. Berdasarkan Proposisi 14.3.5, kita dapat segera menentukan bahwa terdapat
\begin{equation*}
\frac{1}{8} (4^4 + 4^1 + 4^2 + 4^1 + 4^2 + 4^ 2 + 4^3 + 4^3) = 55
\end{equation*}
cara yang mungkin.
Subbagian 14.3.2 Fungsi Pensakelaran
Dalam teori pensakelaran, kita membahas perancangan rangkaian elektronik dengan masukan dan keluaran biner. Rangkaian yang paling sederhana adalah fungsi pensakelaran yang memiliki \(n\) masukan dan satu keluaran (Gambar 14.3.8). Rangkaian elektronik besar sering kali dapat dikonstruksi dengan menggabungkan modul-modul kecil semacam ini. Masalah yang melekat di sini adalah bahwa bahkan untuk rangkaian sederhana, sejumlah besar fungsi pensakelaran yang berbeda dapat dikonstruksi. Hanya dengan empat masukan dan satu keluaran, kita dapat mengonstruksi \(65{,}536\) fungsi pensakelaran yang berbeda. Namun, kita sering dapat mengganti suatu fungsi pensakelaran dengan fungsi lainnya hanya dengan mempermutasikan kabel masukan ke rangkaian tersebut (Gambar 14.3.9).
Kita mendefinisikan fungsi pensakelaran atau fungsi Boolean dengan \(n\) variabel sebagai fungsi dari \({\mathbb Z}_2^n\) ke \({\mathbb Z}_2\text{.}\) Karena setiap fungsi pensakelaran dapat memiliki dua nilai yang mungkin untuk setiap tupel-\(n\) biner dan terdapat \(2^n\) tupel-\(n\) biner, terdapat \(2^{2^n}\) fungsi pensakelaran yang mungkin untuk \(n\) variabel. Secara umum, mengizinkan permutasi masukan sangat mengurangi banyaknya jenis modul berbeda yang diperlukan untuk membangun rangkaian besar.
Fungsi pensakelaran yang mungkin dengan dua variabel masukan \(a\) dan \(b\) tercantum dalam Tabel 14.3.10. Dua fungsi pensakelaran \(f\) dan \(g\) ekuivalen jika \(g\) dapat diperoleh dari \(f\) melalui permutasi variabel masukan. Sebagai contoh, \(g(a, b, c) = f(b, c, a)\text{.}\) Dalam kasus ini \(g \sim f\) melalui permutasi \((a,c,b)\text{.}\) Dalam kasus fungsi pensakelaran dua variabel, permutasi \((a,b)\) mereduksi 16 fungsi pensakelaran yang mungkin menjadi 12 fungsi ekuivalen karena
\begin{align*}
f_2 & \sim f_4\\
f_3 & \sim f_5\\
f_{10} & \sim f_{12}\\
f_{11} & \sim f_{13}\text{.}
\end{align*}
| Masukan | Keluaran | ||||||||
| \(f_0\) | \(f_1\) | \(f_2\) | \(f_3\) | \(f_4\) | \(f_5\) | \(f_6\) | \(f_7\) | ||
| \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) |
| Masukan | Keluaran | ||||||||
| \(f_8\) | \(f_9\) | \(f_{10}\) | \(f_{11}\) | \(f_{12}\) | \(f_{13}\) | \(f_{14}\) | \(f_{15}\) | ||
| \(0\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) |
Untuk tiga variabel masukan terdapat \(2^{2^3} = 256\) fungsi pensakelaran yang mungkin; dalam kasus empat variabel terdapat \(2^{2^4} =65{,}536\text{.}\) Banyaknya kelas ekuivalensi terlalu besar untuk dihitung secara langsung dengan wajar. Kita perlu menggunakan Teorema Burnside.
Tinjau suatu fungsi pensakelaran dengan tiga masukan yang mungkin, \(a\text{,}\) \(b\text{,}\) dan \(c\text{.}\) Seperti telah disebutkan, dua fungsi pensakelaran \(f\) dan \(g\) ekuivalen jika suatu permutasi variabel masukan \(f\) menghasilkan \(g\text{.}\) Penting untuk diperhatikan bahwa permutasi fungsi pensakelaran bukan sekadar permutasi nilai masukan \(\{a, b, c\}\text{.}\) Suatu fungsi pensakelaran merupakan himpunan nilai keluaran untuk masukan \(a\text{,}\) \(b\text{,}\) dan \(c\text{,}\) sehingga ketika kita meninjau fungsi-fungsi pensakelaran yang ekuivalen, kita mempermutasikan \(2^3\) keluaran yang mungkin, bukan hanya tiga nilai masukan. Sebagai contoh, setiap tripel biner \((a, b, c)\) memiliki keluaran tertentu yang terkait dengannya. Permutasi \((acb)\) mengubah keluaran sebagai berikut:
\begin{align*}
(0, 0, 0) & \mapsto (0, 0, 0)\\
(0, 0, 1) & \mapsto (0, 1, 0)\\
(0, 1, 0) & \mapsto (1, 0, 0)\\
& \aatavdots{\mapsto}\\
(1, 1, 0) & \mapsto (1, 0, 1)\\
(1, 1, 1) & \mapsto (1, 1, 1)\text{.}
\end{align*}
Misalkan \(X\) adalah himpunan nilai keluaran bagi fungsi pensakelaran dalam \(n\) variabel. Maka \(|X|=2^n\text{.}\) Kita dapat mengenumerasi nilai-nilai tersebut sebagai berikut:
\begin{align*}
(0, \ldots, 0, 1) & \mapsto 0\\
(0, \ldots, 1, 0) & \mapsto 1\\
(0, \ldots, 1, 1) & \mapsto 2\\
& \aatavdots{\mapsto}\\
(1, \ldots, 1, 1) & \mapsto 2^n-1\text{.}
\end{align*}
Sekarang, mari kita tinjau suatu rangkaian dengan empat variabel masukan dan satu keluaran. Misalkan kita dapat mempermutasikan kabel pada sebarang rangkaian menurut grup permutasi berikut:
\begin{gather*}
(a), \quad (a,c), \quad (b,d), \quad (a,d,c,b),\\
(a,b,c,d), \quad (a,b)(c,d), \quad (a,d)(b,c), \quad (a,c)(b,d)\text{.}
\end{gather*}
Permutasi empat variabel masukan yang mungkin menginduksi permutasi nilai keluaran dalam Tabel 14.3.11.
Jadi, terdapat
\begin{equation*}
\frac{1}{8} (2^{16} + 2 \cdot 2^{12} + 2 \cdot 2^6 + 3 \cdot 2^{10}) = 9616
\end{equation*}
fungsi pensakelaran empat variabel yang mungkin di bawah grup permutasi ini. Bilangan ini akan lebih kecil lagi jika kita meninjau grup simetris penuh pada empat huruf.
| Grup | Banyaknya | |
| Permutasi | Permutasi Fungsi Pensakelaran | Siklus |
| \((a)\) | \((0)\) | \(16\) |
| \((a, c)\) | \((2,8)(3,9)(6,12)(7,13)\) | \(12\) |
| \((b, d)\) | \((1,4)(3,6)(9,12)(11,14)\) | \(12\) |
| \((a, d, c, b)\) | \((1,2,4,8)(3,6.12,9)(5,10)(7,14,13,11)\) | \(6\) |
| \((a, b, c, d)\) | \((1,8,4,2)(3,9,12,6)(5,10)(7,11,13,14)\) | \(6\) |
| \((a, b)(c, d)\) | \((1,2)(4,8)(5,10)(6,9)(7,11)(13,14)\) | \(10\) |
| \((a, d)(b, c)\) | \((1,8)(2,4)(3,12)(5,10)(7,14)(11,13)\) | \(10\) |
| \((a, c)(b, d)\) | \((1,4)(2,8)(3,12)(6,9)(7,13)(11,14)\) | \(10\) |
Subbagian 14.3.3 Catatan Sejarah
William Burnside lahir di London pada tahun 1852. Ia menempuh pendidikan di Universitas Cambridge dari tahun 1871 hingga 1875 dan memenangkan Smith’s Prize pada tahun terakhirnya. Setelah lulus, ia mengajar di Cambridge. Ia diangkat menjadi anggota Royal Society pada tahun 1893. Burnside menulis sekitar 150 makalah tentang matematika terapan, geometri diferensial, dan probabilitas, tetapi sumbangannya yang paling terkenal adalah dalam teori grup. Beberapa konjektur Burnside telah mendorong penelitian hingga kini. Salah satu konjektur tersebut menyatakan bahwa setiap grup berorde ganjil dapat dipecahkan; yaitu, untuk suatu grup \(G\) berorde ganjil, terdapat suatu barisan subgrup
\begin{equation*}
G = H_n \supset H_{n-1} \supset \cdots \supset H_1 \supset H_0 = \{ e \}
\end{equation*}
sedemikian sehingga \(H_i\) normal dalam \(H_{i+1}\) dan \(H_{i+1} / H_i\) abelian. Konjektur ini akhirnya dibuktikan oleh W. Feit dan J. Thompson pada tahun 1963. Burnside’s The Theory of Groups of Finite Order, yang diterbitkan pada tahun 1897, merupakan salah satu buku pertama yang membahas grup dalam konteks modern, bukan hanya sebagai grup permutasi. Edisi keduanya, yang diterbitkan pada tahun 1911, tetap menjadi karya klasik.
