Permutasi Siklis (Permutasi Melingkar)

Rumus:

Andaikan $r$ adalah bilangan bulat tak negatif sehingga $r \le n$. Banyaknya $r$-permutasi atas $n$ objek memenuhi sifat rekursif
$P(n,~r) =$ $P(n − 1,~r) + rP(n − 1,~r − 1)$.

Baca juga: Permutasi Linear

Bukti. Andaikan $S$ adalah sebuah himpunan dengan n unsur dan misalkan $a \in S$. Kita partisi himpunan semua $r$-permutasi atas $S$ menjadi dua bagian, yakni:
- Himpunan $X$ adalah himpunan semua $r$-permutasi yang tidak memuat unsur $a$. Banyaknya $r$-permutasi yang demikian adalah sebanyak $P(n − 1,~r)$.
- Himpunan $Y$ adalah himpunan semua $r$-permutasi yang memuat unsur $a$. Perhatikan bahwa $a$ dapat menempati $r$ posisi, sisanya adalah $(r−1)$-permutasi atas $(n−1)$ unsur. Sehingga oleh prinsip perkalian banyaknya $r$-permutasi di $Y$ adalah $r$×$P(n−1,~r−1)$ buah. Dengan menggunakan prinsip penjumlahan kita peroleh $P(n,~r) =$ $P(n − 1,~r) + r P(n − 1,~r − 1)$. Permutasi yang telah kita diskusikan di atas biasa disebut sebagai permutasi linier. Kita beranggapan bahwa objek disusun sepanjang garis. Bila objek disusun pada suatu lingkaran, banyaknya permu- tasi akan lebih sedikit. Permutasi yang demikian disebut sebagai permutasi melingkar. Perhatikan gambar berikut ini.

Sebagai permutasi melingkar kedua objek di atas menggambarkan dua permutasi melingkar yang sama. Permutasi di atas dapat berasal dari permutasi linier 1234, 2341, 3412, 4123 Secara umum setiap sebuah $r$-permutasi melingkar akan menghasilkan $r$ buah $r$-permutasi linier.

Rumus permutasi siklis atau permutasi melingkar:
Banyaknya $r$-permutasi melingkar dari suatu him punan dengan $n$ objek adalah $$\frac{P(n,~r)}{r} = \frac{n!}{r(n − r)!}$$ Secara khusus banyaknya $n$-permutasi melingkar atas $n$ objek adalah $(n − 1)!$.

Contoh:
Sepuluh orang, termasuk dua orang yang tidak ingin duduk berdekatan, akan didudukan pada sebuah meja bundar. Tentukan banyaknya susunan melingkar yang mungkin.
Solusi 1. Andaikan ke sepuluh orang tersebut adalah O1, O2, . . . , O10 dan misalkan O1 dan O2 adalah dua orang yang tidak ingin duduk berdekatan. Perhatikan persoalan susunan melingkar dari 9 orang $X$, O3, O4, . . . , O10. Terdapat 8! susunan yang demikian. Bila $X$ di ganti dengan O1, O2 atau O2, O1 maka diperoleh susunan melingkar dari 10 orang dengan O1 duduk berdekatan dengan O2. Sehingga dengan prinsip pengurangan banyaknya susunan melingkar dari 10 orang dengan O1 tidak berdekatan dengan O2 adalah 9! − 2 × 8! = 7 × 8!.
Solusi 2. Pertama kita dudukan O1, maka O2 tidak boleh duduk di kanan atau di kiri dari O1. Sehingga ada 8 pilihan orang yang duduk di kanan O1 dan 7 pilihan orang yang duduk di kiri O1. Sisanya dapat diisi dengan 7-permutasi linier dari 7 orang. Sehingga total cara yang mungkin adalah 8 × 7 × 7! = 7 × 8!.

Demikianlah materi tentang permutasi siklis atau permutasi melingkar. Sampai jumpa dan semoga bermanfaat.