My first Magazine pemrograman-kompetitif-dasar | Page 30

2 Matematika Diskret Dasar
Contoh Soal 2.4: Kompetisi
Terdapat 5 anak (sebut saja A, B, C, D, dan E) yang sedang mengikuti sebuah kompetisi.
Dalam kompetisi tersebut akan diambil 3 peserta sebagai pemenang. Berapa banyak
susunan pemenang yang berbeda dari kelima orang tersebut?
Anggap bahwa kita mengambil semua anak sebagai pemenang, sehingga terdapat 5! = 120
susunan pemenang yang berbeda (ABCDE, ABCED, ABDCE, ..., EDCBA). Apabila kita hanya
mengambil 3 peserta saja, perhatikan bahwa terdapat 2 cara berbeda yang kita anggap sama.
Contoh: (ABC)DE dan (ABC)ED merupakan cara yang sama, karena 3 peserta yang menang
adalah A, B, dan C. Dengan menggunakan aturan pembagian, maka banyak susunan pemenang
yang berbeda adalah:
5! 120
=
= 60
2!
2
Secara umum, apabila terdapat N anak dan kita mengambil semua anak sebagai pemenang,
maka terdapat N! susunan cara berbeda. Tetapi apabila kita hanya mengambil R anak saja, maka
akan terdapat (N − R)! susunan berbeda yang kita anggap sama. Dengan aturan pembagian,
banyak susunan berbeda adalah:
N!
(N − R)!
Inilah yang kita kenal dengan istilah permutasi. Secara formal, misalkan terdapat n objek
dan kita akan mengambil r objek dari n objek tersebut yang mana r < n dan urutan pengambilan
diperhitungkan. Banyak cara pengambilan yang berbeda adalah permutasi r terhadap n:
P(n, r) = n P r = P r n =
n!
.
(n − r)!
Permutasi Elemen Berulang
Contoh Soal 2.5: Megagiga
Berapa banyak kata berbeda yang disusun dari huruf-huruf penyusun kata "MEGAGIGA"?
Observasi:
• Terdapat 8 huruf, sehingga banyak kata yang dapat disusun adalah 8!.
• Terdapat 3 huruf ’G’ sehingga terdapat 6 kata berbeda yang kita anggap sama (G 1 G 2 G 3 ,
G 1 G 3 G 2 , ..., G 3 G 2 G 1 ).
Dengan aturan pembagian, maka banyak kata yang dapat disusun mengingat kesamaan kata
pada huruf G adalah 8!
3! . Perlu kita perhatikan pula bahwa terdapat 2 huruf A, sehingga dengan
cara yang sama akan didapatkan banyak kata yang berbeda adalah:
8!
3! × 2!
.
20