Teorema Enumerasi Polya #7: Grup Permutasi

Grup adalah salah satu struktur aljabar yang umum dipelajari awal ketika kita mempelajari topik Pengantar Struktur Aljabar.

 

Jadi, apakah itu grup?

 

Grup adalah suatu struktur aljabar yang dibentuk oleh suatu himpunan $G$ dan suatu operasi biner $\ast$ yang memenuhi sejumlah kaidah berikut.

1. Operasi biner $\ast$ terdefinisi dengan baik (well defined), yaitu setiap 2 elemen di $G$ dapat dioperasikan terhadap $\ast$ dan hasil operasinya valid alias sah.
    
2. Operasi biner $\ast$ tertutup (closed) di $G$, yaitu hasil operasi setiap 2 elemen di $G$ terhadap $\ast$ tetap merupakan elemen di $G$.
    
3. Operasi biner $\ast$ pada $G$ bersifat asosiatif, yaitu untuk sebarang $a, b, c \in G$ berlaku $(a ~\ast~ b)~ \ast ~c = a~ \ast~(b ~\ast~ c)$.
    
4. $G$ memiliki elemen identitas $e$ sedemikian sehingga $e ~\ast~ a = a ~\ast~ e = a$ untuk setiap $a \in G$.
    
5. Setiap elemen pada $G$ memiliki invers, yaitu untuk setiap $a \in G$ selalu terdapat $a' \in G$ sedemikian sehingga $a ~\ast~ a' = a' ~\ast~ a = e$.

 

Salah satu contoh grup adalah himpunan bilangan bulat $\mathbb{Z}$ terhadap operasi penjumlahan $+$.

 

Tidak hanya bilangan bulat, himpunan permutasi pun dapat menjadi grup terhadap operasi komposisi permutasi.

Misalkan kita punya himpunan $G = \{e, a, b\}$.

Dengan $e = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}$, $a = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$, dan $b = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$.

 

Kita akan membuktikan bahwa $G$ merupakan grup terhadap operasi komposisi permutasi.

Perhatikan penjabaran hasil operasi komposisi antar sesama elemen $G$ di bawah ini.

1. $e ~\circ~ e = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = e$.
2. $e ~\circ~ a = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = a$.
3. $e ~\circ~ b = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = b$.
    
4. $a ~\circ~ e = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 &1 & 2 \end{pmatrix} = a$.
5. $b ~\circ~ e = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 &3 & 1 \end{pmatrix} = b$.
    
6. $a ~\circ~ a = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 &3 & 1 \end{pmatrix} = b$.
7. $b ~\circ~ b = \begin{pmatrix} 1 & 2 & 3 \\ 2 &3 & 1 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 2 &3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 &1 & 2 \end{pmatrix} = a$.
    
8. $a ~\circ~ b = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = e$.
9. $b ~\circ~ a = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = e$.

     

Bila disajikan pada tabel akan menjadi seperti ini.

$\circ$	$e$	$a$	$b$
$e$	$e$	$a$	$b$
$a$	$a$	$b$	$e$
$b$	$b$	$e$	$a$

Dari sini terlihat bahwa operasi komposisi permutasi pada $G$ terdefinisi dengan baik dan tertutup.

 

Apakah operasi komposisi permutasi $\circ$ bersifat asosiatif?

Ya! Secara umum komposisi suatu fungsi bersifat asosiatif. Karena permutasi adalah fungsi bijektif, maka komposisi permutasi juga bersifat asosiatif.

 

Dari tabel di atas kita dapat melihat bahwa $e$ merupakan elemen identitas.

Juga elemen $a$ dan $b$ saling invers satu sama lain.

 

Jadi, dengan demikian betul bahwa $G$ merupakan suatu grup terhadap operasi komposisi permutasi.

Jadi, grup permutasi, yaitu grup yang elemen-elemennya merupakan permutasi itu eksis.