Kombinasi dan Binomial (Matdis)
1. Kombinasi tanpa Perulangan
Kombinasi r dari n obyek berbeda adalah banyak cara mengambil r obyek dari n obyek di mana urutan tidak diperhatikan dan tidak boleh ada perulangan.
Karena tidak boleh ada perulangan, diharuskan r ≤ n. Kombinasi r obyek dari n obyek dinotasikan dengan
nCr atau Cn,r atau Crn atau C(n, r)
Ingat kembali bahwa
P(n, r) = [n × (n − 1) × (n − 2) × ... × (n − r + 1) × (n − r)!]/(n − r)! = n!/(n − r)!
Dan dikarenakan urutan tidak diperhatikan, maka susunan r obyek sebanyak r! dianggap sama, sehingga rumus kombinasi adalah rumus permutasi dibagi r!
C(n, r) = P(n, r)/r! = n!/[(n − r)!r!]
Dari rumus ini, kita mendapati bahwa kombinasi bersifat simetris, dimana C(n, r) = C(n, n − r).
contoh:
1. Berapa banyak cara memilih 3 orang dari 8 anggota OSIS untuk dikirim pelatihan kepemimpinan?
Banyak cara adalah 8!/[(8 − 3)!3!] = 8!/[5!3!] = (8 × 7 × 6)/(3 × 2 × 1) = 56
Ada sebanyak 56 cara.
2. Himpunan A memiliki 7 anggota. Berapa banyak himpunan bagian dari A yang memiliki 4 anggota?
Banyaknya adalah 7!/[(7 − 4)!4!] = 35.
2. Kombinasi dengan Perulangan (Multiset)
Kombinasi dengan perulangan adalah pengambilan obyek di mana urutan tidak diperhatikan dan boleh ada perulangan.
Misal terdapat n obyek, akan diambil sebanyak r obyek di mana urutan tidak diperhatikan dan boleh ada perulangan, akan terbentuk tabel 1 baris, dimana banyak kolom adalah n. Sehingga terdapat sebanyak n − 1 pembatas kolom.
Ada sebanyak r obyek yang masing-masing di kolom-kolom tersebut.
Penyusunan ini seperti menyusun pembatas kolom dan obyek-obyek yang diambil.
Sehingga total ada sebanyak r + n − 1 obyek yang disusun.
contoh:
1. Rombongan 6 orang mahasiswa pergi ke kantin untuk membeli makan. Terdapat 4 menu yaitu Bakso, Soto, Pecel, dan Mie. Jika masing-masing memesan 1 menu, ada berapa kemungkinan?
n = 4, r = 6, sehingga r + n − 1 = 4 + 6 − 1 = 9
Banyak kemungkinannya adalah C(r + n − 1, r) = C(9, 6) = 9!/(6!3!) = 84.
Jadi, ada 84 kemungkinan variasi pesanan.
2. Tentukan banyaknya solusi dari x₁ + x₂ + x₃ + x₄ = 10 dengan masing-masing bilangan cacah.
Ini seolah-olah menentukan banyak susunan dari 3 | dan 10 *, sehingga total ada 13 obyek.
Banyak kemungkinan solusinya adalah C(13, 10) = 13!/(3!10!) = 286.
3. Koefisien Suku-Suku dari (a + b)ⁿ dan Segitiga Pascal
A. Koefisien Suku
Perhatikan pola perpangkatan berikut:
(a + b)⁰ = 1
(a + b)¹ = 1a + 1b
(a + b)² = 1a² + 2ab + 1b²
(a + b)³ = 1a³ + 3a²b + 3ab² + 1b³
(a + b)⁴ = 1a⁴ + 4a³b + 6a²b² + 4ab³ + 1b⁴
(a + b)⁵ = ...???
Setiap suku dari (a + b)ⁿ berbentuk aⁿ⁻ᵏbᵏ, yang mana jumlah pangkat dari a dan b adalah n, dimulai dari k = 0 sampai k = n. Koefisiennya adalah banyak cara mengambil k objek dari n objek = C(n, k).
Sehingga rumus untuk (a + b)ⁿ adalah:
Kasus khusus untuk a = 1 dan b = 1:
Jumlah semua koefisien binomial C(n, 0) + C(n, 1) + C(n, 2) + ... + C(n, n) = 2n.
B. Segitiga Pascal
Perhatikan segitiga Pascal
Ketika diamati segitiga pascal, ternyata entri-entrinya merupakan hasil kombinasi. Ingat kembali suatu elemen dalam segitiga pascal merupakan penjumlahan dua elemen, sebagai berikut:
Berikut penguraian berdasarkan rumus kombinasi:
C. Perluasan untuk Multinomial
Misal ingin ditentukan koefisien dari a₁m₁a₂m₂...aₙmₙ dari (a₁ + a₂ + ... + aₙ)ᵐ, koefisiennya adalah
m!/(m₁!m₂!...mₙ!).
4. Deret Binomial
A. Deret Superset (Deret Hockey Stick)
C. Deret Produk Superset
Contoh Soal
1. Di Amerika, DPR terdiri dari 2 partai yaitu partai Republik dan partai Demokrat. Anggota komite terdiri dari 7 orang dari partai republik dan 5 orang dari partai demokrat. Akan dibuat satu delegasi yang mewakili komite tersebut. Tentukan banyaknya cara penyusunan delegasi jika:
A. Delegasi terdiri dari 4 orang.
Anggota komite terdiri dari 7 orang dari partai republik dan 5 orang dari partai demokrat, sehingga total ada sebanyak 12.
Delegasi dipilih 4 orang secara bebas, sehingga banyak cara adalah
C(12, 4) = 12!/[8!4!] = 495 cara.
B. Delegasi terdiri dari 5 orang dengan tiga orang dari partai republik.
Dari 7 orang partai republik dipilih tiga, sehingga ada sebanyak C(7, 3) = 35 cara.
Sisanya 2 orang dipilih dari 5 orang partai demokrat, sehingga ada sebanyak C(5, 2) = 10 cara.
Total ada sebanyak 35 × 10 = 350 cara.
2. Tentukan banyaknya solusi dari x₁ + x₂ + x₃ + x₄ = 10 dengan masing-masing bilangan cacah
A. Sembarang bilangan cacah
Ini seolah-olah membagikan 10 bola ke dalam 4 kotak, sehingga terdapat 3 bar (|) dan 10 star (*), total ada 13 objek.
Banyak kemungkinan solusinya adalah C(13, 10) = 13!/(3!10!) = 286.
B. Masing-masing tidak kurang dari 2
Pertama bagikan masing-masing kotak dengan 2 bola, dari 10 bola sudah dimasukkan ke kotak-kotak sebanyak 8 bola, sehingga tersisa 2 bola. Ini seolah-olah mengisikan 2 bola yang tersisa ke 4 kotak, sehingga terdapat 3 bar dan 2 star, total ada 5 objek.
Banyak kemungkinan solusinya adalah C(5, 2) = 5!/(3!2!) = 10.
C. x₁, x₂, x₃ sembarang bilangan cacah, dan x₄ tidak lebih dari 5.
Ingat kembali bahwa untuk x₄ juga sembarang terdapat 286 kemungkinan.
Sedangkan untuk x₄ > 5, artinya minimal terisi 6, sehingga tersisa 4 bola. Ini seolah-olah mengisikan 4 bola yang tersisa ke 4 kotak, sehingga terdapat 3 bar dan 4 star, total ada 7 objek.
Banyak kemungkinan kasus ini adalah C(7, 4) = 7!/(3!4!) = 35.
Sehingga banyak kemungkinan untuk x₁, x₂, x₃ sembarang bilangan cacah, dan x₄ tidak lebih dari 5 adalah 286 − 35 = 251 kemungkinan.
3. Tentukan banyak solusi pertidaksamaan x₁ + x₂ + x₃ + x₄ ≤ 10 dengan masing-masing bilangan cacah.
Ini seolah-olah membagikan sebanyak r bola ke 4 kotak sehingga terdapat 3 bar dan r star.
Dimulai dari r = 0 sampai r = 10.
C(3, 0) + C(4, 1) + C(5, 2) + ... + C(13, 10), ingat deret binomial.
= C(14, 10) = 14!/(4!10!) = 1001.
Komentar
Posting Komentar