4. KOMBINATORIKA 4.1 Aturan Untuk Suatu Peristiwa Event sesuatu yang terjadi. Jika peristiwa A dapat terjadi dalam m cara dan peristiwa B dapat terjadi dalam N cara, maka terdapat (m, n) cara kedua peristiwa terjadi bersama-sama. 4.1.1 Aturan Penjumlahan Misalkan himpunan A adalah gabungan dari himpunan-himpunan bagian tidak kosong yang saling asing S1, S2, …, Sn. Maka A | S1 | | S2 | .... | Sn |
S1
... Sn S2 Gambar 4.1
Dengan kata lain, jumlah anggota himpunan A sama dengan jumlah anggota semua himpunan bagiannya. Perhatikan bahwa dalam aturan penjumlahan, disyaratkan bahwa himpunanhimpunan bagian (S1, S2, …, Sn) semuanya saling asing (irisannya = Ø). Contoh : Dalam suatu kartu bridge lengkap, berapa macam cara untuk mengambil : a. Sebuah jantung (heart) atau sebuah daun (spade) ? b. Sebuah jantung atau kartu As c. Sebuah As atau sebuah King d. Sebuah kartu bernomor 2 hingga 10 ? Penyelesaian : a. Dalam kartu bridge, kartu-kartu jantung dan daun merupakan himpunanhimpunan yang saling asing sehingga sebanyak cara untuk mendapatkan salah satunya adalah jumlah cara yang mendapatkan masing-masing bagian. Dalam kartu bridge, ada 13 buah kartu jantung dan 13 buah kartu daun sehingga banyak cara untuk mendapatkan sebuah kartu jantung atau daun adalah 13 + 13 = 16. b. Ada 13 buah kartu jantung (termasuk As jantung), dan ada 3 kartu As selain As jantung, sehingga banyak kemungkinan : 13 + 3 = 16 cara. c. Ada 4 buah As dan 4 buah King sehingga kemungkinannya ada 4 + 4 = 8 cara. d. Untuk masing-masing gambar, ada 9 kartu bernomor 2 hingga 10 sehingga kemungkinannya adalah 9 + 9 + 9 + 9 = 36 cara.
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 1
4.1.2 Aturan Perkalian Aturan perkalian untuk menghitung banyak cara yang dapat dilakukan adalah sebagai berikut : Misalkan suatu pekerjaan melibatkan k buah langkah. Langkah ke-1 dapat dilakukan dalam n1 cara. Langkah ke-2 dapat dilakukan dalam n2 cara. …………….. Langkah ke-k dapat dilakukan dalam nk cara. Maka keseluruhan pekerjaan dapat dilakukan dalam (n1)(n2)….(nk) cara. Aturan perkalian untuk 2 langkah dapat diilustrasikan dalam gambar 4.2. (Ci, Cj) adalah proses yang langkah pertama memakai cara -i dan langkah kedua dilakukan dengan cara ke-j. Langkah ke-2 1 (C1, C1) Langkah ke-1 1
2 (C1, C2) : n2 (C1, Cn2) 1 (C2, C1) 2 (C2, C2)
2
: n2 (C2, Cn2)
: 1 (Cn1,C1)
:
2 (Cn1,C2) n1
: n2 (Cn1,Cn2) Gambar 4.2
Contoh 1 : Jika dua dadu yang berbeda dilontarkan, ada berapa banyak kemungkinan angka yang muncul ? Bagaimana jika 5 buah dadu ?. Bagaimana jika n buah dadu ?
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 2
Penyelesaian : Sebuah dadu mempunyai 6 kemungkinan munculnya angka-angka sehingga kalau 2 dadu berbeda akan mempunyai 6 x 6 = 62 = 36 kemungkinan. Jika 5 buah dadu, maka banyaknya kemungkinan adalah 6 x 6 x 6 x 6 x 6 = 65 cara. Jika ada n dadu, maka ada 6n kemungkinan. Contoh 2 : Hitunglah jumlah kata yang dapat dibentuk dengan pola KVKVK . Penyelesaian : Jumlah seluruh alfabet konsonan adalah 21 dan jumlah seluruh alfabet vokal adalah 5. Maka jumlah kata yang dapat dibentuk dengan pola KVKVK adalah : 21 x 5 x 20 x 4 x 19 = 159600. 4.2 Permutasi 4.2.1 Definisi Permutasi adalah banyaknya cara untuk menyusun k elemen dari n elemen (k n) dengan urutan diperhatikan. n! P(n, k ) Pkn (n k )! Dengan : 0! = 1
P(n, n)
n! n! n! (n n)! 0!
Permutasi P(n, n) sering disebut permutasi n objek karena permutasi tersebut menyusun keseluruhan objek yang ada. Contoh 1: Tulislah semua permutasi 3 objek {a, b, c} ! Penyelesaian : Permutasi yang mungkin dari 3 objek {a, b, c} ada 3! = 6 kemungkinan yaitu : abc, acb, bac, bca, cba, cab. Contoh 2: Suatu undian dilakukan s\dengan menggunakan angka yang terdiri dari 7 digit. Jika digit-digit dalam suatu angka diharuskan berbeda satu dengan yang lain, ada beberapa kemungkinan nomor undian ? Penyelesaian : Dalam undian tersebut, jelas urutan kemunculan angka-angka diperhatikan. Undian dengan nomor 1234567 akan berbeda dengan nomor 7654321. Karena digit-digitnya diharuskan selalu berbeda, maka banyaknya kemungkinan nomor undian adalah 10! P(10,7) 10 x 9 x 8 x 7 x 6 x 5 x 4 = 604800 macam kemungkinan. 3!
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 3
4.2.2 Lexicographic Order (Urutan Kamus) Misalkan terdapat permutasi atas n elemen Pa dan Pb dengan: Pa = a1, a2, a3, … an dan Pb = b1, b2, b3, …bn Pa dikatakan mendahului Pb pada urutan kamus (LO) jika terdapat k (1 < k < n) sedemikian sehingga ai = bi, i = 1, 2, …., k-1 dan ak < bk. Contoh 1 : Diketahui 8 buah permutasi atas 6 elemen : P1 = 542361 P2 = 213465 P3 = 234651 P5 = 213645 P6 = 315624 P7 = 214635 Tentukan urutan dari 8 permutasi tersebut dalam LO ! Penyelesaian :
K1 = {P2, P3, P5, P7}
K11 = {P2, P5, P7} K12 = {P3}
P4 = 356214 P8 = 421365
K111 = {P2, P5}
K1111 = {P2} K1112 = {P5}
K112 = {P7}
K11 = {P2, P5, P7} K2 = {P4, P6} K12 = {P3} K3 = {P8} K4 = {P1} Maka urutan kamus = P2 P5 P7 P3 P6 P4 P8 P1 Jika diketahui permutasi atas n elemen a1, a2, …., an maka permutasi berikutnya dalam LO adalah b1, b2, …, bn akan memenuhi syarat sebagai berikut : i. ai = bi, 1 < i < k dengan mengambil k sebesar mungkin. ii. bk = minimum dari ak+1, ak+2, …, an yang lebih besar dari ak. iii. bk+1 < bk+2 < …. < bn. Contoh 2 : Tentukan urutan semua permutasi atas 4 elemen (1, 2, 3, 4) ! Penyelesaian : 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3241 3214 3412 3421 4123 4132 4213 4231 4312 4321 4.2.3 Permutasi dengan Ada Elemen yang Sama Secara umum, jika suatu himpunan terdiri dari n objek yang tersusun dari : n1 buah objek sama jenis-1 n2 buah objek sama jenis-2 .... Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 4
.... nk buah objek sama jenis-k. dengan n1 + n2 + n3 +…+ nk = n
n n1
Maka banyaknya permutasi berbeda yang mungkin dari n objek tersebut adalah : n n1 n2 ... nk 1 n n1 n n1 n 2 n! ........... n3 nk n2 n1!n2!...nk !
Contoh 1 : Ada berapa banyak cara yang mungkin dari kata MATEMATIKA ? Penyelesaian : Kata MATEMATIKA terdiri dari 10 karakter huruf, yang tersusun dari : 2 buah huruf M 3 buah huruf A 2 buah huruf T 1 buah huruf E 1 buah huruf I 1 buah huruf K Sehingga banyaknya kemungkinan untuk membuat permutasi adalah :
10 ! 10.9.8.7.6.5.4 604800 151200 banyaknya cara menyusun elemen2 ! 3 ! 2 !1!1!11 1.2.1.2.1.1.1.1 4 elemen tersebut. 4.3 Kombinasi 4.3.1 Definisi Misalkan himpunan S mempunyai | S | = n elemen. Banyaknya himpunan bagian S yang terdiri dari k (k n) disebut kombinasi n objek yang diambil sebanyak k objek n sekaligus. Simbolnya adalah atau C(n, k) atau nCk. Banyaknya kombinasi yang k n! dimaksud dapat dinyatakan dalam persamaan C(n, k) Cnk (n - k)! k! Dalam himpunan bagian yang dipilih, urutan kemunculan anggotanya tidaklah diperhatikan. Yang diperhatikan adalah objek-objek yang muncul. Contoh 1 : Seorang pelatih bola basket akan memilih komposisi pemain yang akan diturunkan dalam suatu pertandingan. Ada 12 orang pemain yang dapat dipilihnya. Berapa macam tim yang dapat ia bentuk ? Penyelesaian : Dalam memilih pemain yang akan diturunkan, urutan pemilihan tidaklah diperhatikan. Jadi, yang menjadi masalah hanyalah siapa yang dipilih. Tidak menjadi masalah apakah seorang pemain (katakanlah A) terpilih pertama ataupun terakhir. Hal ini berbeda dengan pemilihan ketua dan wakil ketua. Komposisi yang dibuat apabila Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 5
seseorang (misalnya B) yang terpilih pertama (menjadi ketua) akan berbeda apabila B terpilih kedua (menjadi wakil ketua). Jadi banyaknya tim yang dapat dibentuk oleh pelatih tersebut adalah kombinasi 12 objek yang diambil 5 sekaligus adalah sebagai berikut: 12 12 ! 792 tim. 5 7 !5 ! 4.3.2 Teorema Binomial Pangkat suku dua : Untuk n = 0, (a + b)0 = 1 Untuk n = 1, (a + b)1 = a + b Untuk n = 2, (a + b)2 = a2 + 2ab + b2 Untuk n = 3, (a + b)3 = a3 + 3a2b + 3ab2 + b3 …………….. Untuk (a + b)10 = ? Untuk (a + b)n = ? Maka berlaku rumus Binumium Newton :
( a b) n
n
C(n, r ) a
nr
br
r 10
(a + b )5 = C(5, 0) a5 b0 + C(5, 1) a4 b1 + C(5, 2) a3 b2 + C(5, 3) a2 b3 + C(5, 4) a1 b4 + C(5, 5) a0 b5 = a5 + 5 a4b + 10 a3 b2 + 10 a2 a3 + 5 ab4 + b5 4.3.3 Teorema Polinomial Misalkan diberikan n = n1 + n2 + …. + nr Maka banyaknya cara mengelompokkan n elemen tersebut adalah :
n! n1! n 2!...n r !
Teorema :
(a1 a2 .... ar ) n
n n1 n 2 ... n r
n! a1n1 a2n2 ...arnr n1!n2!...nr !
Contoh : Hitung (a + b + c)4 ! Penyelesaian : dalam hal ini n = 4 ; r = 3, sehingga:
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 6
3! 4 0 0 1!2! 3 3 1 0 3! 6 1!1!1! 4 2 2 0 3! 3 2!1! 3! 2 11 3 1!2!
N
n1
n2
n3
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
0 0 4 0 0 1 1 3 3 0 2 2 1 1 2
0 4 0 1 3 0 3 0 1 2 0 2 1 2 1
4 0 0 3 1 3 0 1 0 2 2 0 2 1 1
n! n1!n2!n3! 1 1 1 4 4 4 4 4 4 6 6 6 12 12 12
suku c4 b4 a4 bc3 b3c ac3 ab3 a3c a3b b2c2 a2c2 a2b2 abc2 ab2c a2bc
Tabel 4.1
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 7
