NARASOMA NOTEBOOK: Kombinatorika (paling) Dasar

Kombinatorika (paling) Dasar

0 komentar
Posted in Label: Kombinatorika

Aturan Jumlahan (Sum Rule)
Jika sebuah peristiwa dapat terjadi dalam m cara dan peristiwa lain dalam n cara, serta kedua kejadian tersebut tidak dapat terjadi secara serempak, maka salah satu kejadian dapat terjadi dalam m + n cara. Secara lebih umum, jika $E_i$ (i = 1, 2, 3..., k) adalah k kejadian sedemikian rupa sehingga tidak ada dua kejadian (atau lebih) darinya yang terjadi secara serempak, dan $E_i$ dapat terjadi dalam $n_i$ cara, maka salah satu dari kejadian - kejadian tersebut dapat terjadi dalam $n_1+n_2+n_3+...+ n_k$ cara.

contoh :
Jika ada 18 laki - laki dan 12 perempuan, maka ada 18 + 12 = 30 cara memilih satu orang baik laki - laki maupun perempuan.
Andaikan E adalah cara pemilihan bilangan prima kurang dari 10, F adalah pemilihan bilangan genap kurang dari 10. Maka E dan F dapat terjadi dalam 4 cara. Namun karena 2 adalah bilangan prima yang genap, maka E atau F dapat terjadi dalam 4 + 4 - 1 = 7 cara.

Aturan Hasilkali (Product Rule)
Jika sebuah peristiwa dapat terjadi dalam m cara, peristiwa kedua n cara serta cara peristiwa kedua terjadi tidak terpengaruh oleh peristiwa pertama maka kedua peristiwa dapat terjadi secara simultan dalam mn cara. Secara lebih umum, jika $E_i$ adalah k peristiwa dan $E_1$ dapat terjadi dalam $n_1$ cara, $E_2$ dapat terjadi dalam $n_2$ cara (tidak peduli bagaimana $E_1$ terjadi), dan seterusnya. Maka k peristiwa dapat terjadi dalam $n_1\times n_2\times n_3 \times ... \times n_k$ cara.

contoh:
Jika dalam sebuah rak buku terdapat 6 buah buku bahasa Indonesia, 8 buah buku bahasa Perancil dan 10 buah buku bahasa Jerman. Maka terdapat 6.8.10 = 480 cara untuk memilih tiga buku yang masing - masing satu buku bahasa yang berbeda. Juga terdapat 6 + 8 + 10 = 24 cara untuk memilih satu buku bahasa sebarang dari rak tersebut.

Permutasi dan Kombinasi
Andaikan X adalah kumpulan n objek yang berbeda dan r adalah bilangan bulat tak negatif yang sama dengan atau lebih kecil dari n. permutasi-r dari X adalah pemilihan sejumlah r objek dari n objek. Pemilihan tersebut 'diurutkan'. Misalnya jika X={1, 2, 3, 4, 5}, maka {2, 3, 4} dan {2, 4, 3} adalah permutasi-3 yang berbeda, dari kumpulan objek - objek X. Permutasi-n dari X biasa disebut sebagai permutasi X saja.

Sejumlah permutasi-r dari sekumpulan n objek yang berbeda ditulis P(n,r). Sebuah anggota X dapat dipilih untuk menempati posisi pertama dari r dalam n cara. Setelah itu, n-1 objek dapat dipilih untuk menempati posisi kedua dalam n-1 cara, n-3 menempati posisi ketiga dalam n-3, dan seterusnya.

Jadi,
$\! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! P(n,r) = n\times (n-1)\times(n-2)\times(n-3)\times...\times(n-r) \\ \\ = \frac{n!}{(n-r)!}$

dan jelas bahwa $P(n,n)=n!$ .

Pemilihan r 'tak terurut' objek dari n objek anggota X disebut kompinasi-r dari X. Dengan kata lain, sebarang himpunan bagian dari X yang beranggotakan r buah anggota, adalah kombinasi-3 dari X.

Kombinasi-r dari n objek ditulis C(n,r). Untuk setiap r buah anggota X, ada himpunan bagian beranggota n-r buah, yang 'unik', sedemikian rupa sehingga C(n,r) = C(n,n-r)

Untuk menghitung C(n,r), tinjau ulang konsep permutasi di atas. P(n,r) haruslah merupakan jumlah dari permutasi dari himpunan - himpunan bagian X yang beranggota sejumlah r buah anggota; r-himpunan bagian yang berbeda membangkitkan permutasi yang berbeda.

Jadi,
$\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! P(n,r)=P(r,r)+ P(r,r)+P(r,r)+...+P(r,r) \\ \; \;\;\;\;\;\; \;\;\;\;(sebanyak \; C(n,r)\; suku)$

$\! \! \! \! \! \! \! \! \! P(n,r)=P(r,r)\times C(n,r) \\ \\ C(n,r)=\frac{P(n,r)}{P(r,r) }=\frac{n!}{(n-r)!.r!}$

contoh soal kombinasi yang 'jelas' :
Dalam sebuah kelas, terdapat 5 siswa yang mahir matematika, 4 siswa mahir fisika dan 6 siswa mahir kimia. Hendak dibentuk sebuah tim olimpiade beranggotakan 2 siswa mahir matematika, 2 mahir fisika dan 2 mahir kimia. Berapa tim yang mungkin dibentuk dari kelima belas siswa mahir tersebut? Jika Andi adalah salah satu siswa pandai matematika, Budi salah satu siswa mahir fisika dan Catur salah satu siswa mahir kimia, berapa peluang Catur masuk dalam tim? Berapa peluang Andi dan Budi berada pada satu tim?

Jawab
Soal ini dapat diselesaikan dengan cara manual, yakni dengan melabeli semua siswa dengan huruf (nama) yang berbeda, dan kemudian mencatat seluruh tim yang mungkin dibentuk. Misalnya siswa mahir matematika {Andi, D, E, F, G}, siswa mahir fisika {Budi, H, I, J}, siswa mahir kimia {Catur, K, L, M, N, O}.
Kemungkinan pertama : tim [{Andi, D},{Budi, H},{Catur, K}]
Kemungkinan kedua : tim [{Andi, D},{Budi, H},{Catur, K}]
dan seterusnya. Lalu peluang dapat dihitung dengan membagi frekuensi kemunculan nama yang diminta dengan jumlah seluruh tim yang mungkin dibentuk. Namun perlu dicatat bahwa cara ini sangat tidak praktis untuk himpunan - himpunan dengan banyak anggota!

Dengan menggunakan konsep kombinasi, cara yang lebih cepat bisa ditempuh.
Cara memilih 2 siswa dari 5 siswa mahir matematika : C(5,2) = 5!/(5-2)!2! = 10 cara
Cara memilih 2 siswa dari 4 siswa mahir fisika : C(4,2) = 6 cara
Cara memilih 2 siswa dari 6 siswa mahir kimia : C(6,2) = 15 cara
Jadi tim yang mungkin dibentuk ada 10.3.15= 450 kemungkinan

Peluang Andi masuk dalam tim = 1/2, peluang Budi masuk dalam tim = 1/2, peluang Catur masuk dalam tim = 1/3. Maka peluang Andi dan Budi berada dalam satu tim adalah 1/2 . 1/2 = 1/4

[Sumber : Buku "Shaum's Easy Outlines ; Combinatorics"]