Teorema Enumerasi Polya #6: Operasi Komposisi Permutasi
Kita tahu bahwa komposisi 2 pemetaan adalah suatu hal yang memungkinkan dan menarik untuk dikaji.
#1. Komposisi Pemetaan Secara Umum
Misalkan kita punya pemetaan $\phi$ yang memetakan objek di himpunan $A$ ke himpunan $B$.
Misalkan pula kita punya pemetaan $\sigma$ yang memetakan objek di himpunan $B$ ke himpunan $C$.
Jika $\text{Range}(\phi) = \text{Domain}(\sigma) = B$, maka kita dapat membuat pemetaan $\tau$ dari himpunan $A$ ke $C$ yang terdefinisi dengan baik dan dinyatakan sebagai:
$\begin{equation*} \begin{split} \tau~(a) &= \sigma \circ\phi ~(a) \\ &= \sigma(\phi(a)) \\ \end{split} \end{equation*}$
untuk setiap $a \in A$.
#2. Komposisi Permutasi sebagai Pemetaan Bijektif
Sekarang, mari kita telaah apabila $\phi$ dan $\sigma$ adalah permutasi pada himpunan $X$.
Jika $\phi$ dan $\sigma$ adalah permutasi pada himpunan $X$, maka jelas bahwa:
- $\phi$ dan $\sigma$ adalah pemetaan bijektif dari himpunan $X$ ke dirinya sendiri.
- $X = \text{Domain}(\phi) = \text{Range}(\phi) = \text{Domain}(\sigma) = \text{Range}(\sigma)$.
Kita tahu bahwa komposisi dari 2 pemetaan bijektif akan berupa pemetaan bijektif.
Karena $\phi$ dan $\sigma$ adalah pemetaan bijektif dari himpunan $X$ ke dirinya sendiri, maka komposisi dari $\phi$ dan $\sigma$ juga merupakan pemetaan bijektif dari $X$ ke dirinya sendiri.
Dengan kata lain komposisi dari permutasi $\phi$ dan permutasi $\sigma$ juga merupakan suatu permutasi.
Dengan kata lain, jika $S_X$ merupakan himpunan semua permutasi yang mungkin terjadi dari himpunan objek $X$, maka $\phi_1 ~\circ~ \phi_2 \in S_X$, untuk sebarang permutasi $\phi_1, \phi_2 \in S_X$.
Ingat bahwa notasi $\circ$ menandakan operasi biner untuk komposisi pemetaan.
Operasi biner $\circ$ ini yang untuk seterusnya akan disebut sebagai operasi komposisi permutasi (permutation composition).
#3. Mengkonstruksi Komposisi 2 Permutasi
Harap perhatikan hal ini ketika menyatakan hasil komposisi dari 2 permutasi! Perhatikan contoh berikut!
Contoh
Misalkan kita punya $X = \{1, 2, 3\}$.
Misalkan pula $\phi, \sigma \in S_X$ dengan $\phi = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$ dan $\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$.
Misalkan kita ingin mengkonstruksi permutasi yang merupakan hasil komposisi dari $\phi$ dan $\sigma$, yaitu:
- $\phi \circ \sigma$, dan
- $\sigma \circ \phi$.
Bagaimanakah cara kita mengkonstruksi komposisi permutasi tersebut?
Kita coba untuk menyelidiki $\phi \circ \sigma$ terlebih dahulu ya! :)
Perhatikan bahwa $\phi \circ \sigma$ tidak lain adalah $\phi(\sigma(x))$ untuk setiap $x \in X$.
Karena $X = \{1, 2, 3\}$, maka:
- Jika $x = 1$, maka $\sigma(1) = 3$. Oleh karena $\phi(3) = 2$, maka $\phi(\sigma(1)) = 2$.
- Jika $x = 2$, maka $\sigma(2) = 2$. Oleh karena $\phi(2) = 1$, maka $\phi(\sigma(2)) = 1$.
- Jika $x = 3$, maka $\sigma(3) = 1$. Oleh karena $\phi(1) = 3$, maka $\phi(\sigma(3)) = 3$.
Jadi, dari penjabaran di atas, kita akan memperoleh:
$\begin{equation*} \begin{split} \phi \circ \sigma &= \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \\ \end{split} \end{equation*}$
Dengan cara yang serupa, kita dapat mengkonstruksi $\sigma \circ \phi$ sebagai berikut.
$\begin{equation*} \begin{split} \sigma \circ \phi &= \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} ~\circ~ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} \\ \end{split} \end{equation*}$
Dari contoh ini terlihat bahwa operasi perkalian permutasi tidak komutatif, karena $\sigma \circ \phi \neq \phi \circ \sigma$.
Kita juga dapat menggunakan trik berikut untuk mengkonstruksi $\sigma \circ \phi$. Caranya:
- Misalkan untuk $x = 1$.
- Pada permutasi yang berada di sisi kanan (pada contoh adalah $\sigma$), cari angka $1$ di baris paling atas. Kemudian, lihat angka yang berada tepat di bawah angka $1$ tersebut. Ditemukan angka $3$.
- Pada permutasi yang berada di sisi kiri (pada contoh adalah $\phi$), cari angka $3$ di baris paling atas. Kemudian, lihat angka yang berada tepat di bawah angka $3$ tersebut. Ditemukan angka $1$.
- Tulis permutasi baru, dengan angka $1$ pada baris atas dan angka $1$ pada baris tepat di bawahnya.