My first Magazine pemrograman-kompetitif-dasar | Page 33

2.5 Kombinatorika
• (o|o|oo) menyatakan 1 kue A, 1 kue B, dan 2 kue C.
• (oo|oo|) menyatakan 2 kue A, 2 kue B, dan 0 kue C.
Dengan kata lain, semua susunan yang mungkin adalah (oooo||), (ooo|o|), (oo|oo|), ...,
6!
= 15 susunan berbeda.
(||oooo) yang tidak lain merupakan C 2 6 = 4!×2!
Secara umum, kita ingin mencari banyaknya susunan nilai berbeda dari X 1 , X 2 , X 3 , ..., X r yang
mana X 1 + X 2 + X 3 + ... + X r = n. Untuk membagi n objek tersebut menjadi r bagian, maka akan
dibutuhkan r − 1 buah pembatas, sehingga akan terdapat n + r − 1 buah objek, yang mana kita
akan memilih r − 1 objek untuk menjadi simbol |. Dengan kata lain, banyaknya susunan nilai yang
n+r−1
berbeda adalah C r−1
. Inilah yang kita kenal dengan istilah kombinasi dengan perulangan.
Secara formal, jika terdapat r jenis objek dan kita akan mengambil n objek, dengan tiap
jenisnya dapat diambil 0 atau beberapa kali, maka banyaknya cara berbeda yang memenuhi syarat
tersebut adalah sebagai berikut:
n+r−1
C n n+r−1 = C r−1
=
2.5.4
(n + r − 1)!
n! × (r − 1)!
Segitiga Pascal
Segitiga Pascal merupakan susunan dari koefisien-koefisien binomial dalam bentuk segitiga.
Nilai dari baris ke-n suku ke-r adalah C r n .
Contoh Segitiga Pascal:
•
•
•
•
•
Baris ke-1:
Baris ke-2:
Baris ke-3:
Baris ke-4:
Baris ke-5:
1
11
121
1331
14641
Untuk memahami lebih dalam tentang Segitiga Pascal, simak contoh kasus berikut.
Contoh Soal 2.9: Kombinasi Subhimpunan
Diberikan suatu himpunan S = {X 1 , X 2 , ..., X n }. Berapa banyak cara untuk memilih r objek dari
S?
Terdapat 2 kasus:
• Kasus 1: X n dipilih.
Artinya, r − 1 objek harus dipilih dari himpunan {X 1 , X 2 , X 3 , ..., X n−1 }. Banyaknya cara berbeda
n−1
dari kasus ini adalah C r−1
.
• Kasus 2: X n tidak dipilih.
Artinya, r objek harus dipilih dari himpunan {X 1 , X 2 , X 3 , ..., X n }. Banyaknya cara berbeda dari
kasus ini adalah C r n−1 .
n−1
Dengan aturan penjumlahan dari kasus 1 dan kasus 2, kita dapatkan C r n = C r−1
+ C r n−1 .
Persamaan itulah yang sering kita gunakan dalam membuat Segitiga Pascal, karena C r n juga
menyatakan baris ke-n dan kolom ke-r pada Segitiga Pascal.
23