Setelah sebelumnya kita membahas tentang pengantar kombinatorik maka kali ini kita akan membahas tentang permutasi. Permutasi adalah materi yang diajarkan di SMA kelas XI.
PERMUTASI. Definisi : Suatu urutan dari k objek yang diambil dari n objek yang berbeda, disebut dengan permutasi n objek setiap kali diambil k objek dengan k < n. Permutasi kadang dinotasikan dengan P (n,k) atau atau atau nPk (dibaca permutasi k objek dari n objek).
Contoh :
Tentukan banyaknya permutasi dari 4 objek yaitu a, b, c, dan d setiap kali diambil 3 objek.
Penyelesaian :
Misalkan ketiga objek itu dimisalkan dengan 3 buah kotak.
I | II | III |
Kotak I dapat diisi dengan 4 cara, yaitu a atau b atau c atau d. Kotak II dapat diisi dengan 3 cara (karena 1 objek sudah mengisi kotak I), sedangkan kotak III dapat diisi dengan 2 cara.
4 | 3 | 2 |
Sehingga berdasarkan kaidah perkalian terdapat 4 . 3 . 2 = 24 banyak permutasi dari 4 objek setiap kali diambil 3 objek.
Teorema 1
Banyak permutasi dari n objek setiap kali diambil k objek adalah :
P (n,k) =
Bukti
P (n,k) = n . (n-1)(n-2) … (n-k+1)
= (n . (n-1)(n-2) … (n-k+1)(n-k)!)/(n-k)!
= n!/ (n-k)!
Apabila k = n maka diperoleh teorema berikut :
Teorema 2
Banyak permutasi dari n objek yang berbeda setiap kali diambil seluruhnya adalah
P (n,n) = n!
Bukti :
P (n,n) = n . (n-1)(n-2) … 3.2.1
= n!
Contoh :
Berapakah banyak permutasi dari 3 objek yaitu a, b, dan c setiap kali diambil ketiganya?
Jawab :
Berdasarkan teorema di atas terdapat 3! = 1 x 2 x 3 = 6 permutasi, yaitu :
abc, acb, bac, bca, cab, dan cba.
Contoh lagi :
Dalam berapa carakah 5 huruf yang berbeda dalam kata KORUPSI dapat diatur dalam suatu urutan?
Jawab :
Banyak cara yang dapat dilakukan mengurutkan 5 huruf yang berbeda dari huruf-huruf dalam kata KORUPSI adalah P (7, 5).
P (7, 5) = 7! / (7-5)!
= 7! / 2!
= 7 x 6 x 5 x 4 x 3
= 2.520 cara
Permutasi Melingkar
Definisi
Suatu urutan objek yang membentuk sebuah lingkaran disebut permutasi melingkar (keliling atau siklis).
Teorema 1
Jika n objek yang berbeda, maka dapat dibentuk (n-1)! Permutasi melingkar, dengan n > 2.
Contoh :
Dalam berapa carakah 7 orang mahasiswa dapat duduk mengelilingi suatu meja bundar?
Jawab :
Berdasarkan teorema maka terdapat (7-1)! = 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720 cara.
Permutasi dengan Pengulangan
Seringkali dalam suatu himpunan objek terdapat beberapa objek yang sama sedangkan kita ingin mengetahui berapa banyak permutasi yang mungkin dibentuk. Maka di bawah ini dikemukakan teorema tentang permutasi dari himpunan objek dimana terdapat beberapa objek yang sama.
Teorema 4
Banyak permutasi dari n objek dimana terdapat n1 objek yang sama, n2 objek yang sama, nk objek yang sama adalah n! / (n1!n2!nk!) dengan n1 + n2 + n3 = k.
Jadi, banyaknya permutasi dapat dihitung dengan n! / (n1!n2!nk!)
Contoh :
Dalam berapa carakah kata MATEMATIKA dapat dipermutasikan?
Jawab :
Kata MATEMATIKA terdiri dari 10 huruf, yakni
2 huruf M
3 huruf A
2 huruf T
1 huruf E
1 huruf I
1 huruf K
Jadi kata MATEMATIKA dapat dipermutasikan dengan 10! / 2! 3! 2! 1! 1! 1! = 151.200 cara.
Contoh lagi :
Seorang petani memiliki 4 jenis bibit tumbuhan yang masing-masing diberi kode A, B, C, dan D yang berturut-turut terdiri dari 3 batang, 4 batang, 2 batang, dan 5 batang. Ia akan menanamnya pada satu deretan. Ada berapa cara pelaksanaannya bila penanaman dilakukan :
a. Tanpa ada syarat
b. Dengan syarat bibit jenis D tidak boleh diselingin oleh yang lain
c. Dengan syarat setiap jenis bibit ditanam berdampingan
Jawab :
a. Bila penanaman dilakukan tanpa syarat, maka 14 batang bibit tanaman dapat diatur
14! / 3! 4! 2! 5! = 2.522.520 cara (Perhitungan diserahkan pada pembaca)
b. Bila bibit jenis D harus berdekatan, maka kita anggap D sebagai 1 saja sehingga banyak bibit tanaman tersebut dalam ditanam dalam :
10!/ 3! 4! 2! = 12.600 cara
Namun 5 batang jenis D dapat diatur dalam 5! = 120 cara
Jadi agar 5 batang jenis D tidak diselingi oleh yang lain, keempat jenis bibir tanaman itu dapat ditanam pada suatu deretan (120)(12.600) = 1.562.000 cara
c. Bila semua jenis bibit harus ditanam secara berdampingan sesuai jenisnya, maka kita anggap 1 jenis adalah 1 batang. Kemungkinan ditanam adalah 4! = 4 x 3 x 2 x 1 = 24 cara.
Namun, setiap jenis tersebut dapat diatur sedemikian sehingga :
Jenis A ditanam dalam susunan 3! = 3 x 2 x 1 = 6 cara
Jenis B ditanam dalam susunan 4! = 4 x 3 x 2 x 1 = 24 cara
Jenis C ditanam dalam susunan 2! = 2 cara
Jenis D ditanam dalam susunan 5! = 5 x 4 x 3 x 2 x 1 = 120 cara
Sehingga secara keseluruhan dapat disusun
= 24 cara x Jenis A x Jenis B x Jenis C x Jenis D
= 24 x 6 x 24 x 2 x 120
= 829.440 cara