$S_n$ adalah grup simetri derajat $n \in \mathbb{N}$, yaitu grup yang elemen-elemennya adalah permutasi atas $n$ objek dengan operasi binernya adalah komposisi permutasi.
Banyaknya cycle pada grup simetri $S_n$ yang berorder $k$ $(k \leq n)$ adalah $\displaystyle \frac{1}{k} \cdot \frac{n!}{(n-k)!}$
Himpunan Objek
Himpunan $X = \{ x_1, x_2, x_3, ..., x_{n-1}, x_n \}$ adalah himpunan yang memuat $n$ objek. Notasi untuk objek berindeks $i$ adalah $x_i$. Setiap objek adalah berbeda $(x_i \neq x_j \iff i \neq j)$.
Permutasi
Permutasi adalah pemetaan bijektif dari himpunan objek $X$ ke dirinya sendiri.
Contoh. Misalkan $X = \{ x_1, x_2, x_3, x_4, x_5 \}$. Suatu permutasi $\rho$ pada $X$ didefinisikan sebagai $\rho(x_1) = x_5$, $\rho(x_2) = x_4$, $\rho(x_3) = x_2$, $\rho(x_4) = x_3$, $\rho(x_5) = x_1$.
Notasi Permutasi dalam Bentuk Matriks
Jika $\rho$ adalah permutasi atas $X$, maka $\rho = \begin{pmatrix} x_1 & x_2 & x_3 & ... & x_n \\ \rho(x_1) & \rho(x_2) & \rho(x_3) & ... & \rho(x_n) \end{pmatrix}$ adalah notasi permutasi $\rho$ dalam bentuk matriks.
Contoh. Misalkan $X = \{ x_1, x_2, x_3, x_4, x_5 \}$ dan permutasi $\rho$ pada $X$ didefinisikan sebagai $\rho(x_1) = x_5$, $\rho(x_2) = x_4$, $\rho(x_3) = x_2$, $\rho(x_4) = x_3$, $\rho(x_5) = x_1$. Notasi permutasi $\rho$ dalam bentuk matriks adalah $\begin{pmatrix} x_1 & x_2 & x_3 & x_4 & x_5 \\ x_5 & x_4 & x_2 & x_3 & x_1 \end{pmatrix}$.
Bentuk notasi matriks dapat dijadikan lebih ringkas dengan hanya menampilkan nomor indeks (notasi $x$ tidak ditulis/omitted).
Contoh. Permutasi $\begin{pmatrix} x_1 & x_2 & x_3 & x_4 & x_5 \\ x_5 & x_4 & x_2 & x_3 & x_1 \end{pmatrix} \implies \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 2 & 3 & 1 \end{pmatrix}$.
Notasi Cycle dan Cycle Part
Jika $\rho = \begin{pmatrix} x_1 & x_2 & x_3 & ... & x_n \\ \rho(x_1) & \rho(x_2) & \rho(x_3) & ... & \rho(x_n) \end{pmatrix}$ adalah notasi permutasi $\rho$ dalam bentuk matriks, maka:
$\rho = (x_1~~ \rho(x_1)~~ \rho^2(x_1)~~ ...~ \rho^{k_1}(x_1))\;(x_2~~ \rho(x_2)~~ \rho^2(x_2)~~ ...~ \rho^{k_2}(x_2))\; ... \;(x_n~~ \rho(x_n)~~ \rho^2(x_n)~~ ...~ \rho^{k_n}(x_n))$
untuk suatu $k_1, k_2, ..., k_n \in \mathbb{N}$ adalah permutasi $\rho$ dalam notasi Cycle.
Notasi cycle juga memiliki bentuk ringkas sebagai berikut.
$\rho = (1~~ \rho(1)~~ \rho^2(1)~~ ...~ \rho^{k_1}(1))\;(2~~ \rho(2)~~ \rho^2(2)~~ ...~ \rho^{k_2}(2))\; ... \;(n~~ \rho(n)~~ \rho^2(n)~~ ...~ \rho^{k_n}(n))$
Contoh. Misalkan $\rho_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 2 & 3 & 1 \end{pmatrix}$ dan $\rho_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 3 & 4 & 2 \end{pmatrix}$, maka permutasi $\rho_1$ dan $\rho_2$ dalam bentuk notasi cycle adalah $\rho_1 = (1\;5)(2\;4\;3)$ dan $\rho_2 = (1)(2\;5)(3)(4)$.
Bagian dari notasi cycle suatu permutasi seperti $(1\;5)$, $(2\;4\;3)$, $(1)$, $(2\;5)$, $(3)$, dan $(4)$ disebut sebagai cycle part. Secara konvensi, cycle part yang hanya memuat satu objek saja tidak dianggap atau diabaikan karena dianggap sebagai permutasi identitas.
Contoh. Permutasi $\rho_1 = (1\;5)(2\;4\;3)$ terdiri dari 2 cycle part, yaitu $(1\;5)$ dan $(2\;4\;3)$. Permutasi $\rho_2 = (1)(2\;5)(3)(4)$ terdiri dari satu cycle part, yaitu $(2\;5)$ karena cycle part $(1)$, $(3)$, dan $(4)$ tidak dianggap karena hanya memuat satu objek saja. Dengan demikian, permutasi $\rho_2$ dapat dinyatakan lebih ringkas dalam notasi cycle sebagai $\rho_2 = (2\;5)$.
Cycle dan Panjang Cycle
Suatu permutasi disebut sebagai cycle jika dan hanya jika notasi cycle permutasi tersebut hanya terdiri dari tepat satu cycle part saja. Panjang cycle adalah banyaknya objek yang termuat di dalam cycle tersebut.
Contoh. Permutasi $\rho_1 = (1\;5)(2\;4\;3)$ bukan cycle karena notasi cycle permutasi $\rho_1$ terdiri dari 2 cycle part. Permutasi $\rho_2 = (2\;5)$ adalah cycle karena notasi cycle permutasi $\rho_2$ terdiri dari tepat satu cycle part saja. Panjang cycle $\rho_2 = (2\;5)$ adalah 2 karena cycle ini memuat objek $x_2$ dan $x_5$.
Step 1
Misalkan kita punya himpunan objek $X$ yang memuat sebanyak $n$ objek sebagai berikut.
$X = \{ x_1, x_2, x_3, ..., x_n \}$
Misalkan juga terdapat suatu cycle $\rho$ dengan panjang $k$ sebagai berikut.
$\rho = \{ i_1, i_2, i_3, ..., i_k \}$
untuk suatu $i_1, ..., i_n \in \{ 1,2,3,..., n \}$.
Step 2
Untuk mempermudah visualisasi, bayangkan kita punya himpunan objek $X$ yang memuat sebanyak 10 objek; $X = \{ 1, 2, 3, ..., 10 \}$. Misalkan juga $\rho$ adalah suatu cycle dengan panjang 6. Dengan demikian, $(1\;2\;3\;4\;5\;6)$, $(2\;4\;7\;8\;9\;10)$, dan $(1\;3\;5\;7\;9\;10)$ adalah beberapa kemungkinan bentuk $\rho$ yang mungkin terjadi.
Perhatikan bahwa cycle memuat objek-objek yang berbeda-beda. Dengan demikian, bentuk cycle seperti $(1\;2\;1\;3\;2\;6)$, $(4\;4\;4\;5\;5\;5)$, dan $(1\;2\;3\;1\;2\;3)$ tidak mungkin terjadi.
Perhatikan juga bahwa bentuk cycle $(i_1\;i_2\;i_3\;i_4\;i_5\;i_6)$, $(i_2\;i_3\;i_4\;i_5\;i_6\;i_1)$, $(i_3\;i_4\;i_5\;i_6\;i_1\;i_2)$, ..., $(i_6\;i_1\;i_2\;i_3\;i_4\;i_5)$ adalah ekuivalen. Sebagai contoh, cycle $(3\;7\;1\;4\;2\;10)$, $(7\;1\;4\;2\;10\;3)$, $(1\;4\;2\;10\;3\;7)$, ..., $(10\;3\;7\;1\;4\;2)$ adalah ekuivalen. Ini disebabkan karena sifat $\rho$ sebagai permutasi, yaitu pemetaan bijektif dari himpunan $X$ ke dirinya sendiri. Kita dapat membuat suatu "untaian pemetaan" atau cycle objek-objek terhadap permutasi $\rho$ yang tidak akan pernah berakhir, yaitu $... \overset{\rho}{\to} i_6 \overset{\rho}{\to} i_1 \overset{\rho}{\to} i_2 \overset{\rho}{\to} i_3 \overset{\rho}{\to} ... \overset{\rho}{\to} i_6 \overset{\rho}{\to} i_1 \overset{\rho}{\to} ...$. Dalam contoh untuk $\rho = (3\;7\;1\;4\;2\;10)$ adalah $... \overset{\rho}{\to} 10 \overset{\rho}{\to} 3 \overset{\rho}{\to} 7 \overset{\rho}{\to} 1 \overset{\rho}{\to} 4 \overset{\rho}{\to} 2 \overset{\rho}{\to} 10 \overset{\rho}{\to} 3 \overset{\rho}{\to} 7 \overset{\rho}{\to} ...$
Untuk cycle dengan panjang lebih dari 2, perbedaan urutan susunan objek seringkali akan membuat suatu cycle menjadi berbeda. Sebagai contoh, cycle $\rho_1 = (3\;7\;1\;4\;2\;10)$ dan $\rho_2 = (7\;1\;3\;4\;2\;10)$ adalah berbeda, karena pada cycle $\rho_1$ objek $x_3$ dipetakan ke $x_7$ sedangkan pada cycle $\rho_2$ objek $x_3$ dipetakan ke $x_4$.
Step 3
Oke! Kita akan menyinggung perkara kombinatorika.
Kita punya himpunan objek $X$ yang memuat sebanyak 10 objek; $X = \{ x_1, x_2, x_3, ..., x_{10} \}$ dan suatu cycle $\rho$ dengan panjang 6; $\rho = \{ i_1, i_2, i_3, i_4, i_5, i_6 \}$.
Pertama-tama, kita ingin tahu banyaknya cara/kombinasi untuk memilih objek-objek yang akan termuat di dalam cycle $\rho$ tersebut.
Contoh kasarnya seperti ini. Kita punya kotak spidol yang hanya bisa memuat 3 spidol saja. Sedangkan kita punya 6 spidol berbeda warna; hitam, merah, biru, kuning, hijau, dan oranye. Tentu kita bisa mengisi penuh kotak spidol itu dengan spidol warna merah, kuning, hijau, atau spidol warna hitam, oranya, merah, atau spidol warna kuning, hijau, biru, dan lain sebagainya. Nah, mencari cara/kombinasi untuk memilih spidol-spidol itu yang akan kita terapkan pada cycle.
Karena cycle $\rho$ memiliki panjang 6 dan ada 10 objek yang bisa ditempatkan di dalam cycle $\rho$ tersebut, maka banyaknya kombinasi objek-objek yang mungkin adalah sebagai berikut, kita notasikan dengan $P_1$.
$\displaystyle P_1 = \binom{10}{6} = \frac{10!}{(10-6)!6!} = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6!}{4! \cdot 6!} = 210$
Berdasarkan perhitungan di atas, ada 210 kombinasi dari 10 objek yang bisa ditempatkan di dalam cycle dengan panjang 6. Beberapa contoh dari 210 kombinasi tersebut adalah $\{x_1, x_2, x_3, x_4, x_5, x_6\}$, $\{x_1, x_2, x_3, x_4, x_5, x_7\}$, dan $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$.
Step 4
Nah, sekarang kita pilih salah satu dari 210 kombinasi objek, misalkan saja kita pilih $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$. Sekarang kita akan membuat suatu cycle $\rho$ menggunakan objek-objek pada himpunan $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$. Kira-kira kita bisa membuat berapa cycle $\rho$?
Sebagai contoh, menggunakan objek-objek pada himpunan $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$ kita bisa membuat:
Perhatikan!
Misalkan cycle $\rho = ([1]\;[2]\;[3]\;[4]\;[5]\;[6])$. Untuk objek di posisi $[1]$, kita akan memilih salah satu objek dari himpunan $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$. Katakanlah kita pilih objek $x_7$ untuk objek di posisi $[1]$, dengan demikian cycle $\rho$ akan menjadi $(7\;[2]\;[3]\;[4]\;[5]\;[6])$. Untuk objek di posisi $[2]$, kita akan memilih salah satu objek dari himpunan $\{x_5, x_6, x_8, x_9, x_{10}\}$ yang sudah kehilangan objek $x_7$ karena sudah menjadi objek di posisi $[1]$. Katakanlah kita pilih objek $x_{10}$ untuk objek di posisi $[2]$, dengan demikian cycle $\rho$ akan menjadi $(7\;10\;[3]\;[4]\;[5]\;[6])$. Selanjutnya, untuk objek di posisi $[3]$, kita akan memilih salah satu objek dari himpunan $\{x_5, x_6, x_8, x_9\}$ yang sudah kehilangan objek $x_7$ dan $x_{10}$ karena sudah menjadi objek di posisi $[1]$ dan $[2]$. Langkah-langkah yang serupa kita lakukan untuk menentukan objek yang akan berada di posisi $[3]$ hingga $[6]$.
Berdasarkan penalaran di atas, kita bisa menentukan banyaknya cycle yang kita buat dari himpunan $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$ adalah sebanyak $P_2$ yang bisa dinyatakan sebagai berikut.
$P_2 = 6 \cdot 5 \cdot 4 \cdot ... \cdot 1 = 6! = 720$
Berdasarkan perhitungan di atas, ada 720 cycle yang bisa kita bentuk dari himpunan objek $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$.
Step 5
Perhatikan!
Berdasarkan Step 4, dari 720 cycle yang bisa kita bentuk dari himpunan objek $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$ itu, sebetulnya ada beberapa cycle yang sama. Eh, kok bisa?
Nah, ingat penjelasan di Step 2 bahwasanya cycle $(i_1\;i_2\;i_3\;i_4\;i_5\;i_6)$, $(i_2\;i_3\;i_4\;i_5\;i_6\;i_1)$, $(i_3\;i_4\;i_5\;i_6\;i_1\;i_2)$, ..., $(i_6\;i_1\;i_2\;i_3\;i_4\;i_5)$ adalah ekuivalen. Sebagai contohnya, misalkan kita bentuk cycle $(5\;6\;7\;9\;10\;8)$ dari himpunan objek $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$, maka cycle ini akan ekuivalen dengan cycle-cycle berikut: $(6\;7\;9\;10\;8\;5)$, $(7\;9\;10\;8\;5\;6)$, $(9\;10\;8\;5\;6\;7)$, $(10\;8\;5\;6\;7\;9)$, dan $(8\;5\;6\;7\;9\;10)$.
Nah, berdasarkan sifat ini, dari 720 cycle yang bisa kita bentuk dari himpunan objek $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$ itu bisa kita kelompokkan dengan satu kelompok berisikan 6 cycle sedemikian sehingga tiap-tiap kelompok akan merepresentasikan cycle-cycle yang berbeda. Dengan demikian, jelas bahwa jumlah kelompok tersebut akan kurang dari 720. Ya kan? Kita akan notasikan jumlah kelompok ini sebagai $P_2'$ yang bisa diperoleh dengan rumus berikut.
$\displaystyle P_2' = \frac{P_2}{6} = \frac{720}{6} = 120$
Step 6
Berdasarkan proses di atas, terdapat 120 cycle yang memuat objek-objek dalam himpunan $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$ dan sesuai dengan kriteria yang kita inginkan. Akan tetapi, karena kita memiliki 210 himpunan objek yang sejenis dengan $\{x_5, x_6, x_7, x_8, x_9, x_{10}\}$, maka hasil total cycle yang akan kita dapatkan adalah sebagai berikut.
$\text{Hasil total cycle}=P_1 \cdot P_2' = 210 \cdot 120 = 25.200$ cycle
Final Step
Oke! Berdasarkan penjelasan di atas, Step 2 hingga Step 6 itu memberikan contoh gambaran tentang bagaimana kita akan menunjukkan sifat bahwa banyaknya cycle pada grup simetri $S_n$ yang berorder $k$ $(k \leq n)$ adalah $\displaystyle \frac{1}{k} \cdot \frac{n!}{(n-k)!}$. Dalam contoh yang digunakan pada Step 2 hingga Step 6, kita menggunakan nilai $n = 10$ dan $k = 6$. Akan tetapi, secara umum, kita bisa merumuskan Step 2 hingga Step 6 menjadi seperti berikut.
Persiapan
Kita punya himpunan objek $X$ yang memuat sebanyak $n$ objek; $X = \{ x_1, x_2, x_3, ..., x_{n} \}$. Kita ingin membuat cycle dengan panjang $k$, yang bentuknya adalah sebagai berikut $(x_{i_1}~ x_{i_2}~ ... ~ x_{i_k})$
Langkah 1
Kita akan menghitung banyaknya kombinasi $k$ objek dari keseluruhan $n$ objek, yaitu $P_1$, yang bisa dihitung sebagai berikut.
$\displaystyle P_1 = \binom{n}{k} = \frac{n!}{(n-k)!k!}$
Langkah 2
Kita akan menghitung banyaknya cycle yang bisa dibentuk dari suatu himpunan yang memuat $k$ objek, yaitu $P_2'$, yang bisa dihitung sebagai berikut.
$\displaystyle P_2' = k! \cdot \frac{1}{k}$
Langkah Terakhir
Jadi, banyaknya cycle pada grup simetri $S_n$ yang berorder $k$ $(k \leq n)$ adalah $P_1 \cdot P_2'$ yang hasilnya adalah sebagai berikut.
$\displaystyle P_1 \cdot P_2' = \frac{n!}{(n-k)!k!} \cdot k! \cdot \frac{1}{k} = \frac{n!}{(n-k)!} \cdot \frac{1}{k}$
$\blacksquare$