My first Magazine pemrograman-kompetitif-dasar | Page 32

2 Matematika Diskret Dasar
2.5.3
Kombinasi
Contoh Soal 2.7: Seleksi
Terdapat 5 anak (sebut saja A, B, C, D, dan E) yang mana akan dipilih 3 anak untuk mengikuti
kompetisi. Berapa banyak susunan tim berbeda yang dapat dibentuk?
Soal ini berbeda dengan permutasi, karena susunan ABC dan BAC merupakan susunan yang
sama, yaitu 1 tim terdiri dari A, B, dan C. Apabila kita anggap bahwa mereka merupakan susunan
yang berbeda, maka banyaknya susunan tim adalah P 2 5 = 120
2 = 60. Untuk setiap susunan yang
terdiri dari anggota yang sama akan terhitung 6 susunan berbeda yang mana seharusnya hanya
dihitung sebagai 1 susunan yang sama, contohnya: ABC, ACB, BAC, BCA, CAB, CBA merupakan
1 susunan yang sama. Oleh karena itu dengan aturan pembagian, banyaknya susunan tim yang
berbeda adalah 60
6 = 10 susunan berbeda.
Untuk secara umumnya, misalkan terdapat N anak dan akan kita ambil R anak untuk dibentuk
sebagai 1 tim. Apabila urutan susunan diperhitungkan, maka banyaknya susunan tim adalah
P R N . Setiap susunan yang terdiri dari anggota yang sama akan terhitung R! susunan berbeda
yang mana seharusnya hanya dihitung sebagai 1 susunan yang sama. Dengan aturan pembagian,
banyaknya susunan tim yang berbeda adalah:
P R N
N!
=
R!
(N − R)! × R!
Inilah yang kita kenal dengan istilah kombinasi. Secara formal, jika terdapat n objek dan
kita akan mengambil r objek dari n objek tersebut dengan r < n dan urutan pengambilan tidak
diperhitungkan, maka banyaknya cara pengambilan yang berbeda adalah kombinasi r terhadap n:
C(n, r) = n C r = C r n =
n!
(n − r)! × r!
Kombinasi dengan Perulangan
Contoh Soal 2.8: Beli Kue
Pak Dengklek ingin membeli kue pada toko kue yang menjual 3 jenis kue, yaitu rasa coklat,
stroberi, dan kopi. Apabila Pak Dengklek ingin membeli 4 buah kue, maka berapa banyak
kombinasi kue berbeda yang Pak Dengklek dapat beli?
Perhatikan bahwa membeli coklat-stroberi dengan stroberi-coklat akan menghasilkan kom-
binasi yang sama. Kita dapat membeli suatu jenis kue beberapa kali atau bahkan tidak membeli
sama sekali. Contoh soal ini dapat dimodelkan secara matematis menjadi mencari banyaknya
kemungkinan nilai A, B, dan C yang memenuhi A + B +C = 4 dan A, B,C ≥ 0.
Untuk penyelesaiannya, kita dapat membagi 4 kue tersebut menjadi 3 bagian. Untuk
mempermudah ilustrasi tersebut, kita gunakan lambang o yang berarti kue, dan | yang berarti
pembatas. Bagian kiri merupakan kue A, bagian tengah merupakan kue B, dan bagian kanan
merupakan kue C. Sebagai contoh:
22