GENARALISASI PERMUTASI

Generalisasi Permutasi
Kalau pada pembahasan permutasi sebelumnya unsur-unsur yang diurutkan
berbeda, pada bagian ini akan dibahas permutasi yang digeneralisasikan den-
gan membolehkan pengulangan unsur-unsur yang akan diurutkan, dengan
kata lain unsur-unsurnya boleh sama.
Misalkan kita akan mengurutkan huruf-huruf dari kata KAKIKUKAKU.
Karena huruf-huruf pada kata tersebut ada yang sama, maka banyaknya
permutasi bukan 10!, tetapi kurang dari 10!.
Untuk mengurutkan 10 huruf pada kata KAKIKUKAKU dapat dilakukan
dengan cara:
 Asumsikan masalah ini dengan tersedianya 10 posisi kosong yang akan
diisi dengan huruf-huruf pada kata KAKIKUKAKU.
 Pertama menempatkan 5 huruf K pada 10 posisi kosong, yang dapat
dilakukan dalam C(10; 5) cara.
 Setelah 5 huruf K ditempatkan, maka terdapat 105 = 5 posisi kosong.
Berikutnya adalah menempatkan 2 huruf A pada 5 posisi kosong, yang
dapat dilakukan dalam C(5; 2) cara.
 Begitu 2 huruf A ditempatkan, terdapat C(3; 2) cara untuk menem-
patkan 2 huruf U pada 3 posisi kosong yang ada.
 Akhirnya terdapat C(1; 1) cara untuk menempatkan 1 huruf I pada 1
posisi kosong yang tersisi.
6 Dengan menggunakan Prinsip Perkalian diperoleh
C(10; 5):C(5; 2):C(3; 2):C(1; 1) =
10!
5!:5!
:
5!
2!:3!
:
3!
2!:1!
:
1!
1!:0!
=
10!
5!:2!:2!:1!
=
10:9:8:7:6
2:2
= 7560
 Jadi banyaknya cara untuk mengurutkan huruf-huruf dari kata KAKIKUKAKU
adalah 7560.
Secara umum banyaknya permutasi dari obyek yang mempunyai beberapa
unsur sama dapat dijabarkan seperti pada teorema berikut ini.
Teorema 3.4
Misalkan X merupakan sebuah barisan yang mempunyai n unsur, dimana
terdapat n1 unsur yang sama untuk jenis 1, n2 unsur yang sama untuk jenis
2 dan seterusnya sampai nt unsur yang sama untuk jenis t. Banyaknya
permutasi dari barisan X adalah
n!
n1!:n2!:::nt
!
Bukti.
 Untuk menempatkan posisi n1 unsur yang sama untuk jenis 1 pada n
posisi yang tersedia dapat dilakukan dengan C(n; n1) cara.
 Setelah n1 unsur ditempatkan, maka terdapat n n1 posisi yang terse-
dia, sehingga untuk menempatkan posisi n2 unsur yang sama untuk
jenis 2 pada n n1 posisi yang tersedia dapat dilakukan dengan C(n
n1; n2) cara.
 Demikian seterusnya sampai pada nt unsur yang sama untuk jenis t
yang bisa dilakukan dengan C(n n1 n2 ::: nt1; nt) cara.
 Dengan menggunakan Prinsip Perkalian dapat diperoleh
C(n; n1):C(n n1; n2):C(n n1 n2; n3):::C(n n1 n2 ::: nt1; nt)
=
n!
n1!(n n1)!
:
(n n1)!
n2!(n n1 n2)!
:::
n n1 n2 ::: nt1
nt
!:0!
=
n!
n1!:n2!:::nt
!
72
Contoh 3.10
Gunakan Teorema 3.4 untuk menentukan banyaknya cara menyusun huruf-
huruf dari kata KAKIKUKAKU
Diketahui n = 10, n1 = 5, n2 = 2, n3 = 2 dan n4 = 1. Dengan menggunakan
Teorema 3.4, diperoleh
10!
5!:2!:2!:1!
=
10:9:8:7:6
2:2
= 7560