Himpunan objek $X$ yang memuat Objek-1, Objek-2, Objek-3, hingga Objek-$n$ didefinisikan sebagai:
$X = \{O_1, O_2, O_3, ..., O_n \}$
dengan $O_1$ menyatakan Objek-1, $O_2$ menyatakan Objek-2, $O_3$ menyatakan Objek-3, dst.
Supaya penulisannya lebih ringkas, himpunan objek $X$ seringkali dinyatakan sebagai:
$X = \{ 1, 2, 3, ..., n \}$
dengan 1,2,3, dst secara berurutan merepresentasikan objek $O_1$, $O_2$, $O_3$, dst.
Kemudian, notasi $X[n]$ menyatakan himpunan objek $X$ yang memuat $n$ objek. Dengan kata lain:
$X[n] = \{ 1, 2, 3, ..., n \}$
Permutasi pada himpunan objek $X$ adalah pemetaan bijektif dari suatu himpunan objek $X$ ke dirinya sendiri.
Jika, $\rho$ adalah suatu permutasi pada himpunan objek $X = \{ 1, 2, 3, ..., n \}$, maka kaidah permutasi adalah menyatakan permutasi $\rho$ sebagai senarai persamaan:
$\rho(1) = x_1$, $\rho(2) = x_2$, $\rho(3) = x_3$, ..., $\rho(n) = x_n$
dengan $x_1,x_2,x_3,...,x_n \in X$.
Ingat!Kaidah permutasi ini harus memenuhi syarat sebagai pemetaan bijektif!
Diketahui $\rho$ adalah suatu permutasi pada himpunan objek $X[4] = \{ 1, 2, 3, 4 \}$ dengan kaidah permutasi $\rho(1) = 3$, $\rho(2) = 1$, $\rho(3) = 2$, dan $\rho(4) = 4$.
Jika, $\rho$ adalah suatu permutasi pada himpunan objek $X[n]$, maka permutasi $\rho$ bisa dinyatakan dalam notasi matriks, yaitu:
$\rho = \begin{pmatrix} 1 & 2 & 3 & ... & n \\ x_1 & x_2 & x_3 & ... & x_n \end{pmatrix}$
dengan $x_1 = \rho(1)$, $x_2 = \rho(2)$, $x_3 = \rho(3)$, ..., $x_n = \rho(n)$ dan $x_1,x_2,x_3,...,x_n \in X$.
Diketahui $\rho$ adalah suatu permutasi pada himpunan objek $X[n]$.
Objek $a \in X[n]$ disebut sebagai objek varian terhadap permutasi $\rho$ jika dan hanya jika $\rho(a) \neq a$.
Objek $b \in X[n]$ disebut sebagai objek invarian terhadap permutasi $\rho$ jika dan hanya jika $\rho(b) = b$.
Diketahui permutasi $\rho = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}$. Berdasarkan notasi matriks tersebut, diketahui bahwa $\rho$ adalah suatu permutasi pada himpunan objek $X[4] =\{ 1,2,3,4 \}$ dan berlaku kaidah $\rho(1) = 3$, $\rho(2) = 1$, $\rho(3) = 2$, dan $\rho(4) = 4$. Dengan demikian kita bisa menyimpulkan bahwa 1, 2, dan 3 adalah objek-objek varian sementara 4 adalah objek invarian.
Diketahui $\rho$ adalah suatu permutasi pada himpunan objek $X[n]$. Diketahui juga objek $a \in X[n]$.
Himpunan $P[\rho][a]$ yang didefinisikan sebagai:
$P[\rho][a] = \{ x \in X ~|~ \rho^z(a) = a, \text{ untuk suatu } z \in \mathbb{Z} \}$
disebut sebagai partisi atas permutasi $\rho$ pada himpunan objek $X[n]$ yang memuat objek $a$.
Jika objek tidak diketahui secara spesifik, maka notasi $P[\rho]$ menyatakan sebarang partisi atas permutasi $\rho$ pada himpunan objek $X[n]$.
Diketahui permutasi $\rho = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}$. Diketahui juga objek $2 \in X$.
Partisi permutasi $\rho$ pada himpunan objek $X[4]$ yang memuat objek $2$ (dinotasikan $P[\rho][2]$) didefinisikan sebagai berikut.
$P[\rho][2] = \{ x \in X ~|~ \rho^z(2) = x, \text{ untuk suatu } z \in \mathbb{Z} \}$.
Karena $\rho(2) = 1$, $3 = \rho(1) = \rho(\rho(2)) = \rho^2(2)$, dan $2 = \rho^3(2)$, maka $P[\rho][2] = \{1,2,3 \}$.
Diketahui $\rho$ adalah suatu permutasi pada himpunan objek $X$.
Relasi $\sim$ pada himpunan objek $X$ yang didefinisikan dengan $a \sim b \iff b = \rho^z(a), \text{ untuk suatu } z \in \mathbb{Z}$ adalah relasi ekuivalensi.
Diketahui $\rho$ adalah suatu permutasi pada himpunan objek $X[n]$. Orbit dari $\rho$ (dinotasikan $O(\rho)$) adalah himpunan yang memuat semua partisi atas permutasi $\rho$ pada himpunan objek $X[n]$. Dengan kata lain:
$O(\rho) = \{ P[\rho][a] ~|~ \forall a \in X[n] \} = \{ P[\rho][1],\;P[\rho][2],\;P[\rho][3],\;...,\;P[\rho][n]\} $.
Diketahui permutasi $\rho_1 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}$. Partisi-partisi atas permutasi $\rho_1$ pada himpunan objek $X[4]$ adalah sebagai berikut.
Dengan demikian, orbit dari $\rho_1$ adalah $O(\rho_1) = \{ P{[\rho_1]}[1], P{[\rho_1]}[4] \} = \{ \{ 1, 2, 3\},\; \{ 4\} \}$.
Dengan demikian, orbit dari $\rho_2$ adalah $O(\rho_2) = \{ P{[\rho_2]}[1], P{[\rho_2]}[2], P{[\rho_2]}[3] \} = \{ \{ 1, 4\}, \{2\}, \{3\} \}$.
Diketahui $\rho$ dan $\tau$ adalah permutasi-permutasi pada himpunan objek $X[n]$. Permutasi $\tau$ disebut cycle dari permutasi $\rho$ jika dan hanya jika terdapat partisi $P[\rho]$ sedemikian sehingga:
Jika $\tau$ adalah cycle dari permutasi $\rho$, maka panjang cycle $\tau$ didefinisikan sebagai jumlah objek yang termuat di dalam partisi yang bersesuaian dengan cycle $\tau$.
Diketahui permutasi $\rho_1 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}$. Orbit dari $\rho_1$ adalah $O(\rho_1) = \{ P{[\rho_1]}[1], P{[\rho_1]}[4] \} = \{ \{ 1, 2, 3\},\; \{ 4\} \}$.
Karena partisi $P{[\rho_1]}[1]$ memuat lebih dari satu objek, maka akan ada cycle $\tau$ yang bersesuaian dengan partisi tersebut. Berdasarkan definisi permutasi $\rho_1 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}$, akan berlaku kaidah $\rho_1(1) = 3$, $\rho_1(3) = \rho^2_1(1) = 2$, dan $\rho_1(2) = \rho^3_1(1) = 1$. Dengan demikian, cycle $\tau$ dari permutasi $\rho_1$ dan bersesuaian dengan partisi $P{[\rho_1]}[1]$ adalah $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}$ yang tidak lain adalah permutasi $\rho_1$ itu sendiri.
Karena cycle $\tau$ bersesuaian dengan partisi $P{[\rho_1]}[1]$ yang memuat 3 objek, maka panjang cycle $\tau$ adalah 3.
Suatu permutasi dapat menjadi cycle untuk dirinya sendiri.
Diketahui permutasi $\rho_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 2 & 1 \end{pmatrix}$. Orbit dari $\rho_2$ adalah $O(\rho_2) = \{ P{[\rho_2]}[1], P{[\rho_2]}[2] \} = \{ \{ 1, 3, 5\},\; \{ 2, 4\} \}$.
Karena partisi $P{[\rho_2]}[1]$ memuat lebih dari satu objek, maka akan ada cycle $\tau_1$ yang bersesuaian dengan partisi tersebut. Berdasarkan definisi permutasi $\rho_2 = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 2 & 1 \end{pmatrix}$, akan berlaku kaidah $\rho_2(1) = 3$, $\rho_2(3) = \rho^2_2(1) = 5$, dan $\rho_2(5) = \rho^3_1(1) = 1$. Dengan demikian, cycle $\tau_1$ dari permutasi $\rho_1$ dan bersesuaian dengan partisi $P{[\rho_2]}[1]$ adalah $\tau_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 4 & 1 \end{pmatrix}$. Karena cycle $\tau_1$ bersesuaian dengan partisi $P{[\rho_2]}[1]$ yang memuat 3 objek, maka panjang cycle $\tau_1$ adalah 3.
Selain itu, karena partisi $P{[\rho_2]}[2]$ juga memuat lebih dari satu objek, maka akan ada cycle $\tau_2$ yang bersesuaian dengan partisi tersebut. Berdasarkan definisi permutasi $\rho_2 = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 2 & 1 \end{pmatrix}$, akan berlaku kaidah $\rho_2(2) = 4$ dan $\rho_2(4) = \rho^2_2(2) = 2$. Dengan demikian, cycle $\tau_2$ dari permutasi $\rho_2$ dan bersesuaian dengan partisi $P{[\rho_2]}[2]$ adalah $\tau_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{pmatrix}$. Karena cycle $\tau_2$ bersesuaian dengan partisi $P{[\rho_2]}[2]$ yang memuat 2 objek, maka panjang cycle $\tau_2$ adalah 2.
Perhatikan bahwa tidak ada objek varian yang sama yang termuat di dalam cycle $\tau_1$ dan $\tau_2$ (contoh, objek varian 5 yang termuat di dalam cycle $\tau_1$ tidak termuat di dalam cycle $\tau_2$). Dengan demikian, cycle $\tau_1$ dan $\tau_2$ disebut sebagai cycle yang saling asing (disjoint cycle).
Perhatikan bahwa akan berlaku persamaan $\rho = \tau_1 \circ \tau_2 = \tau_2 \circ \tau_1$.
Setiap permutasi dapat dinyatakan sebagai komposisi atas cycle-cycle yang saling asing.
Selain dalam notasi matriks, suatu cycle dapat dinyatakan dalam notasi cycle. Berikut akan dijelaskan menggunakan contoh.
Diketahui permutasi $\rho = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 2 & 1 \end{pmatrix}$ yang memiliki 2 cycle, yaitu $\tau_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 4 & 1 \end{pmatrix}$ dan $\tau_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 4 & 5 \end{pmatrix}$ sedemikian sehingga berlaku persamaan $\rho = \tau_1 \circ \tau_2 = \tau_2 \circ \tau_1$.
Untuk cycle $\tau_1$ yang bersesuaian dengan partisi $\{1,3,5\}$ akan berlaku kaidah $\tau_1(1) = 3$, $\tau_1(3) = {\tau^2_1}(1) = 5$, dan $\tau_1(5) = {\tau^3_1}(1) = 1$. Dengan demikian, kita bisa menyatakan cycle $\tau_1$ dalam notasi cycle $(1 \to 3 \to 5)$.
Untuk cycle $\tau_2$ yang bersesuaian dengan partisi $\{2, 4\}$ akan berlaku kaidah $\tau_2(2) = 4$ dan $\tau_2(4) = {\tau^2_2}(2) = 2$. Dengan demikian, kita bisa menyatakan cycle $\tau_2$ dalam notasi cycle $(2 \to 4)$.
Dengan demikian, permutasi $\rho$ bisa dinyatakan sebagai komposisi notasi cycle berikut.
$\rho ~=~ (1 \to 3 \to 5) \circ (2 \to 4) ~=~ (2 \to 4) \circ (1 \to 3 \to 5)$.
Diketahui suatu permutasi $\rho$ pada himpunan objek $X[n]$. Berikut adalah langkah-langkah untuk menentukan cycle dari permutasi $\rho$.
Diketahui $\tau$ adalah cycle dari permutasi $\rho$ pada himpunan objek $X[n]$. Cycle $\tau$ disebut transposisi jika dan hanya jika cycle $\tau$ berukuran 2.
Diketahui permutasi $\rho = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 2 & 1 \end{pmatrix}$ yang memiliki 2 cycle, yaitu $\tau_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 4 & 1 \end{pmatrix} = (1 \to 3 \to 5)$ dan $\tau_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 4 & 5 \end{pmatrix} = (2 \to 4)$.
Cycle $\tau_1$ bukan transposisi karena berukuran 3. Sementara itu, cycle $\tau_2$ adalah transposisi karena berukuran 2.
Setiap cycle berukuran 3 atau lebih dapat dinyatakan sebagai produk komposisi atas sejumlah transposisi. Jika cycle memiliki bentuk $(a_1 \to a_2 \to a_3 \to ... \to a_k)$, maka akan berlaku persamaan $(a_1 \to a_2 \to a_3 \to ... \to a_k) = (a_1 \to a_k) \circ (a_1 \to a_{k-1}) \circ ... \circ (a_1 \to a_3) \circ (a_1 \to a_2)$.
Setiap permutasi dapat dinyatakan sebagai produk komposisi atas sejumlah transposisi.
Diketahui $\rho$ adalah permutasi pada himpunan objek $X[n]$ dan memiliki bentuk dekomposisi transposisi $\rho = ({\text{transposisi}_1}) \circ ({\text{transposisi}_2}) \circ ... \circ ({\text{transposisi}_k})$.
Permutasi $\rho$ disebut sebagai permutasi genap jika dan hanya jika jumlah transposisi penyusun bentuk dekomposisi transposisi dari permutasi $\rho$ (yaitu nilai $k$) adalah bilangan genap.
Permutasi $\rho$ disebut sebagai permutasi ganjil jika dan hanya jika jumlah transposisi penyusun bentuk dekomposisi transposisi dari permutasi $\rho$ (yaitu nilai $k$) adalah bilangan ganjil.
Diketahui permutasi $\rho = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 2 & 1 \end{pmatrix} = (1 \to 5) \circ (1 \to 3) \circ (2 \to 4)$. Karena ada 3 transposisi penyusun bentuk dekomposisi transposisi dari permutasi $\rho$, yaitu $(1 \to 5)$, $(1 \to 3)$, dan $(2 \to 4)$, maka permutasi $\rho$ adalah permutasi ganjil.