Permutasi dengan Perulangan

Baca juga:
-Permutasi Linear tanpa perulangan
- Kombinasi tanpa perulangan

Permutasi dan kombinasi yang kita diskusikan pada bagian terdahulu tidak melibatkan adanya perulangan objek. Bila objek dapat diulang, maka perhitungan akan menjadi sedikit lebih rumit. Sebagai contoh perhatikan kata MATEMATIKA, bila kita pertukarkan huruf A pada posisi kedua dengan posisi keenam, maka kita tidak akan menemukan kata baru. Pada bagian ini kita diskusikan cara untuk menentukan banyaknya permutasi bila terjadi perulangan objek seperti pada kata MATEMATIKA. Kita mulai diskusi kita dengan memperkenalkan multiset. Sebuah multiset adalah sebuah himpunan dengan objek yang berulang. Sebagai contoh: S = {a, b, a, c, c, a, c} adalah sebuah multiset. Multiset S biasanya ditulis dengan S = {3.a, 1.b, 3.c} yang pada dasarnya menyatakan bahwa S terdiri dari tiga objek a, b dan c dengan a berulang 3 kali, b berulang 1 kali dan c berulang 3 kali.
Andaikan S adalah sebuah multiset, sebuah r-permutasi atas S adalah sebuah susunan dengan urutan dari r objek di S. Bila total banyaknya objek di S adalah n (termasuk pengulangan), maka n-permutasi atas S disebut sebagai sebuah permutasi. Bila S = {3.a, 1.b, 3.c}, maka acbc, cbcc adalah 4-permutasi atas S, sementara abaccca adalah sebuah permutasi atas S.
Teorema berikut ini memperlihatkan banyaknya permutasi atas multiset S yang terdiri dari k tipe objek yang berbeda dengan banyak perulangan tak hingga.

Andaikan S adalah sebuah mutiset dengan objek dari k tipe yang berbeda, dengan masing-masing tipe mempunyai tak hingga perulangan. Maka banyaknya $r$-permutasi atas S adalah sebanyak $k^r$.

Contoh-1
Tentukan banyaknya permutasi berbeda yang dapat dibentuk dari kata MATEMATIKA.
Solusi. Kata MATEMATIKA terdiri dari 10 huruf dengan komposisi dua huruf M, tiga huruf A, dua huruf T dan sisanya masing-masing satu huruf E, I dan K. Kalaulah kesepeuluh huruf itu semuanya berbeda, maka terdapat 10! permutasi. Tetapi karena adanya duplikasi pada huruf M, A dan T, maka banyaknya permutasi akan lebih sedikit dari 10!.
Misalkan banyaknya permutasi atas kata MATEMATIKA adalah N buah. Anggap kedua huruf M adalah dua huruf yang berbeda, katakan saja M1 dan M2. Lakukan hal yang sama untuk huruf T dan A. Permutasi atas M1 dan M2 dapat dilakukan dalam 2! cara, permutasi atas T1 dan T2 dapat dilakukan dalam 2! cara, dan permutasi atas A1, A2 dan A3 dapat dilakukan dalam 3! cara. Oleh prinsip perkalian, bila semua huruf dianggap berbeda diperoleh sebanyak 2! × 3! × 2! × N = 10!. Sehingga banyaknya permutasi atas kata MATEMATIKA adalah N = $\displaystyle \frac{10!}{2! \times 3! \times 2!}$ = 151.200
Perhatikan teorema berikut:

Andaikan $S$ adalah mutiset yang terdiri dari $k$ tipe objek yang berbeda dengan masing-masing pengulangan $n_1, ~n_2, . . . , ~n_k$. Misalkan $|S| = n = n_1 + n_2 + · · · + n_k$, maka banyaknya permutasi atas $S$ adalah $$\frac{n!}{n_1!.n_2!...n_k!}$$

Contoh-2
Tentukan banyaknya cara menyusun huruf-huruf MATEMATIKA dengan kedua huruf T tidak berdekatan.
Solusi. Kita gunakan prinsip pengurangan. Andaikan S = {2.M, 3.A, 2.T, 1.E, 1.I, 1.K} maka banyaknya permutasi atas S adalah $$\frac{10!}{2!.3!.2!.1!.1!.1!}$$ Andaikan S$_1$ = {2.M, 3.A, 1.T, 1.E, 1.I, 1.K}, maka banyaknya permutasi atas S$_1$ adalah sama dengan banyaknya cara penyusunan huruf-huruf MATEMATIKA dengan kedua huruf T berdekatan, yakni $$\frac{9!}{2!.3!.1!.1!.1!.1!}$$ Sehingga oleh prinsip pengurangan banyaknya cara menyusun huruf- huruf MATEMATIKA dengan kedua huruf T tidak berdekatan adalah sebanyak $\displaystyle \frac{10!}{2!.3!.2!.1!.1!.1!}$$-$$\displaystyle \frac{9!}{2!.3!.1!.1!.1!.1!}$ = 120.960
Demikianlah postingan materi permutasi dengan perulangan. Sampai jumpa dan semoga bermanfaat.