Maw Mumet!

- karena banyak hal yang tidak bisa diselesaikan sambil ngendog -

Teorema Enumerasi Polya #6: Operasi Komposisi Permutasi

{ 13.Jun.2021 } { matematika }

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:

  1. Misalkan untuk $x = 1$.
  2. 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$.
  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$.
  4. Tulis permutasi baru, dengan angka $1$ pada baris atas dan angka $1$ pada baris tepat di bawahnya.