6.3 PERMUTATIONS AND COMBINATIONS
Pengaturan dengan urutan Sering kali kita perlu menghitung banyaknya cara pengaturan obyek tertentu dengan memperhatikan urutan maupun tanpa memperhatikan urutan. Contoh 1. • Ada berapa cara untuk memilih 3 mahasiswa dari kelompok beranggota 5 orang untuk berbaris dalam pengambilan foto? • Ada berapa panitia beranggotakan 3 orang yang dapat dibentuk dari kelompok beranggotakan 4 orang? 2
Contoh 2 Ada berapa cara kita dapat memilih 3 mahasiswa dari suatu kelompok beranggotakan 5 mahasiswa untuk berbaris dalam pembuatan foto? Ada berapa cara kita dapat mengatur ke-5 mahasiswa tersebut untuk berbaris dalam pembuatan foto? Solusi. Perhatikan bahwa urutan dalam pemilihan akan mempengaruhi pengaturan. Terdapat 5 cara untuk memilih mahasiswa pertama untuk berdiri di awal barisan. Setelah mahasiswa ini dipilih, ada 4 cara untuk memilih mahasiswa kedua di barisan. Setelah mahasiswa pertama dan kedua dipilih, terdapat 3 cara untuk memilih mahasiswa ketiga dalam barisan. Dengan menggunakan aturan perkalian, terdapat 5 · 4 · 3 = 60 cara untuk memilih 3 mahasiswa dari kelompok beranggotakan 5 mahasiswa untuk berbaris dalam pengambilan foto. Untuk mengatur 5 mahasiswa dalam barisan, kita memilih mahasiswa pertama dengan 5 cara, mahasiswa kedua dengan 4 cara, ketiga dengan 3 cara, keempat dengan 2 cara dan kelima dengan 1 cara. Akibatnya, terdapat 5 · 4 · 3 · 2 · 1 = 120 cara untuk mengatur 5 mahasiswa dalam pengambilan foto. 3
Permutasi Contoh 2 menggambarkan bagaimana pengaturan terurut dari obyek dapat dihitung. Permutasi dari suatu himpunan adalah pengaturan yang memperhatikan urutan dari anggota himpunan tersebut. Permutasi-r : pengaturan r buah anggota suatu himpunan secara terurut.
Contoh 3. Misal S = {1,2,3}. Maka 3,1,2 adalah suatu permutasi dan 1,3 adalah suatu permutasi-2 dari S. 4
P(n,r) P(n,r) = Banyaknya permutasi-r dari suatu elemen.
himpunan dengan n
Teorema 1. P(n,r) = n(n-1)(n-2) … (n-r+1) Bukti. • Ada n cara untuk memilih elemen pertama dari permutasi. • Untuk memilih elemen kedua ada (n-1) cara, karena tinggal n1 elemen dalam himpunan yang dapat digunakan sebagai elemen kedua. • Dengan cara yg sama, ada (n-2) cara untuk memilih elemen ketiga. • Ada tepat (n-r+1) cara utk memilih elemen ke-r. • Menurut aturan perkalian, P(n,r) = n(n-1)(n-2) … (n-r+1). P(n, r )
n! (n r )! 5
Contoh 4 Ada berapa banyak permutasi dari huruf-huruf ABCDEFGH yang memuat string ABG ? yang memuat string ABG dan EH? Solusi Karena ABG harus terjadi dalam satu blok maka masalahnya menjadi mencari banyaknya permutasi dari 6 objek, yaitu blok ABG dan huruf C,D,E,F,H. Karena keenam objek tsb dapat terjadi dengan sebarang urutan, maka ada 6! = 720 permutasi dari ABCDEFGH yang memuat ABG. 6
Pemilihan Tak Terurut Contoh 5. Ada berapa penitia beranggotakan 3 mahasiswa yang dapat dibentuk dari kelompok dengan 4 mahasiswa? Solusi. Untuk menjawab pertanyaan ini, hanya perlu dicari banyaknya subhimpunan dengan 3 anggota dari himpunan beranggotakan 4 mahasiswa. Dapat dilihat bahwa terdapat 4 subhimpunan yang demikian, 1 untuk setiap 4 mahasiswa, karena memilih 3 mahasiswa sama dengan memilih satu dari 4 mahasiswa untuk meninggalkan kelompok tersebut. Artinya, terdapat 4 cara memilih 3 mahasiswa untuk panitia, di mana urutan pemilihan mahasiswa tidak berpengaruh. 7
Kombinasi Kombinasi-r dari suatu himpunan adalah pengaturan r buah elemen tanpa memperhatikan urutan.
Contoh 6. Misal S = {1,4,5,6}. Maka, 1,5,6 suatu kombinasi-3 dari S. Sedangkan 4,5 adalah suatu kombinasi-2 dari S. Ada 4 macam kombinasi-2 dari S. C(n,r): banyaknya kombinasi-r dari himpunan dengan n elemen. n C (n, r ) Koefisien binomial r 8
C(n,r) Teorema 2 C(n,r) = n!/(n-r)!r!, bila 0 ≤ r ≤ n. Bukti. • Permutasi-r dari suatu himpunan dengan n elemen dapat diperoleh dengan cara membentuk kombinasi-r dan kemudian mengurutkan elemen pada setiap kombinasi-r tsb (dapat dilakukan dalam P(r,r) cara). • Jadi, P(n,r) = C(n,r).P(r,r) • Ini berarti bahwa C(n,r) = P(n,r)/P(r,r). Akibat 1. C(n,r) = C(n,n-r). 9
Bukti Kombinatorial Bukti kombinatorial dari suatu persamaan adalah • bukti yang menggunakan argumen counting untuk membuktikan bahwa kedua sisi persamaan menghitung obyek yang sama, tetapi dengan cara yang berbeda (bukti double counting) atau • bukti yang menunjukkan bahwa terdapat bijeksi antara dua himpunan obyek yang dihitung oleh kedua sisi persamaan (bukti bijektif)
10
Bukti Kombinatorial dari Teorema 2 Akan digunakan bukti bijektif untuk menunjukkan bahwa C(n, r) = C(n, n − r) untuk setiap bilangan bulat n dan r dengan 0 ≤ r ≤ n. Misalkan S adalah himpunan dengan n anggota. Fungsi yang memetakan subhimpunan A dari S ke A adalah bijeksi antara subhimpunan S dengan r anggota dan subhimpunan dengan n − r anggota. Maka persamaan C(n, r) = C(n, n − r) benar karena terdapat bijeksi antara dua himpunan hingga. Bukti bijektif ini dapat diformulasikan kembali sebagai bukti double counting. Dari definisi, banyaknya subhimpuan S dengan r anggota adalah C(n, r). Tetapi setiap subhimpunan A dari S juga ditentukan dengan menentukan elemen mana yang bukan merupakan anggota A. Karena komplemen dari suatu subhimpunan dengan r anggota memiliki n − r anggota, maka terdapat C(n, n − r) subhimpunan dari S dengan r anggota. Akibatnya C(n, r) = C(n, n − r).
11
Contoh 7 Ada berapa banyak string biner panjang n yang memuat tepat r buah angka 1? Solusi. Bila kita memperhatikan semua kemungkinan posisi r angka 1 dalam string, maka mereka akan membentuk suatu kombinasi-r dari {1,2,3, …,n}. Jadi terdapat C(n,r) string biner panjang n yang memuat tepat r buah angka 1. 12
Soal 1 a. Hitunglah banyaknya lintasan terpendek dari A ke B.
b. Ada berapa cara untuk 8 pria dan 5 wanita berdiri dalam suatu barisan sehingga tidak ada 2 wanita yang berdiri bersebelahan? 13
6.4 BINOMIAL COEFFICIENTS AND IDENTITIES 14
Ekspresi Binomial Ekspresi binomial adalah jumlahan dari 2 variabel, seperti x + y. Contoh 1. Ekspansi (x + y)3 dapat ditemukan dengan menggunakan penjelasan kombinatorik, selain dengan mengalikan tiga jumlahan x + y. Ketika (x + y)3 = (x + y)(x + y)(x + y) dijabarkan, semua suku merupakan hasil kali satu suku di jumlahan pertama, satu suku di jumlahan kedua, dan satu suku di jumlahan ketiga. Dengan demikian muncul suku dalam bentuk x3, x2y, xy2, dan y3. Untuk memperoleh suku dalam bentuk x3, x harus dipilih dari setiap jumlahan, dan ini dapat dilakukan hanya dengan 1 cara. Jadi, suku x3 memiliki koefisian 1. Untuk memperoleh suku dalam bentuk x2y, x harus dipilih dalam 2 dari 3 jumlahan (dan akibatnya y di jumlahan lainnya). Akibatnya banyaknya 3 suku dalam bentuk demikian adalah banyaknya 2-kombinasi dari 3 obyek, 2 . 15
Contoh 1 (2) Dengan cara serupa, banyaknya suku dalam bentuk xy2 adalah banyakanya cara untuk memilih 1 dari 3 jumlahan untuk memperoleh x (dan akibatnya memilih y 3dari 2 jumlahan lainnya). Ini dapat dilakukan dengan 1 cara. Akhirnya, satu-satunya cara untuk memperoleh bentuk y3 adalah dengan memilih y dari setiap jumlahan, dan ini dapat dilakukan dengan tepat 1 cara. Akibatnya, (x + y)3 = (x + y)(x + y)(x + y) = (xx + xy + yx + yy)(x + y) = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy = x3 + 3x2y + 3xy2 + y3. 16
Teorema Binomial Teorema Binomial (x+y)n = C(n,0)xn + C(n,1)xn-1y + C(n,2)xn-2y2 + … + C(n,n-1)xyn-1 + C(n,n)yn.
Bukti. Menghitung banyaknya xn-jyj , untuk suatu j=0,1,2,…,n, sama dengan memilih (n-j) buah x dari n suku (sehingga j suku lainnya dalam perkalian adalah y). Jadi koefisien xn-j yj adalah C(n,n-j).
Koefisien Binomial Akibat 1. 1. C(n,j) = C(n,n-j). 2. C(n,0) + C(n,1) + … + C(n,n) = 2n. n
3.
(1) C (n, k ) 0 k
k 0 n
4.
2 C (n, k ) 3 k
n
k 0
Bukti. 1. Banyaknya cara memilih j dari n elemen sama dengan banyaknya meninggalkan n-j dari n elemen. 2. Pilih x = y = 1. 3. Pilih x = -1 dan y = 1. 4. Pilih x = 1 dan y = 2.
Identitas dan Segitiga Pascal Identitas Pascal Misal n dan k bilangan bulat positif, n k. Maka, C(n+1,k) = C(n,k-1) + C(n,k). Bukti. • Pandang T himpunan dengan n+1 elemen, aT. • Misal S = T-{a}. • Ada C(n+1,k) buah subhimpunan dari T yang mempunyai k elemen. • Suatu subhimpunan dari T dgn k elemen dapat memuat a dan (k-1) elemen S atau memuat k elemen S tanpa memuat a. • Jadi, C(n+1,k) = C(n,k-1)+C(n,k).
Identitas Vandermonde Misal m, n dan r bilangan bulat positif, m r dan n r. r Maka, C (m n, r ) C (m, r k )C (n, k ) k 0
Bukti. • Pandang dua himpunan A dengan m elemen dan B dengan n elemen. • Maka banyaknya cara untuk memilih r elemen dari AUB adalah C(m+n,r). • Cara lain untuk memilih r elemen dari AUB adalah dengan memilih k elemen dari B dan kemudian r-k elemen dari A, dengan k bilangan bulat, 0≤k≤r. • Banyaknya cara untuk melakukan pemilihan tersebut adalah C(m,r-k)C(n,k). • Jadi banyaknya cara untuk memilih r elemen dari AUB adalah r
C (m, r k )C (n, k ) k 0
Soal 1 Buktikan C(2n,n) = C(n,0)2 + C(n,1)2 + … + C(n,n)2
dengan 2 cara: 1. Menggunakan Identitas Vandermonde. 2. Memandang pemilihan n orang dari 2n orang yg terdiri dari n pria dan n wanita
6.5 GENERALIZED PERMUTATIONS AND COMBINATIONS 22
Perluasan permutasi dan kombinasi • Permutasi dengan pengulangan • Kombinasi dengan pengulangan • Permutasi dengan obyek yang tidak dapat dibedakan • Distribusi obyek ke dalam kotak
Permutasi dengan Pengulangan Contoh 1. Berapa banyak string panjang n yang dapat dibentuk dari alfabet ? Karena ada 26 huruf dalam alfabet dan karena setiap huruf dapat digunakan berulang maka ada 26n string panjang n. Teorema 1. Jumlah permutasi-r dari himpunan dengan n anggota yang memperbolehkan pengulangan adalah nr.
Kombinasi dengan Pengulangan Contoh 2. Ada berapa cara untuk memilih 3 buah dari wadah yang berisi rambutan, duku, pisang, dan manggis, jika urutan pengambilan tidak penting, dan setidaknya ada 4 buah dalam setiap jenis buah.
Contoh 3 Ada berapa cara untuk memilih 5 lembar uang kertas dari kotak yg memuat lembaran $1, $2, $5, $10, $20, $50 dan $100? Asumsikan bahwa urutan pengambilan tidak penting dan ada sedikitnya 5 lembar uang kertas utk masingmasing pecahan. Solusi. • Karena urutan tidak penting dan ke-7 macam uang kertas tersebut dapat dipilih hingga 5 kali, maka problem ini sama dengan menghitung kombinasi-5 dengan pengulangan dari himpunan dengan 7 elemen. • Misal kotak mempunyai 7 bagian dan setiap bagian menyimpan 1 macam uang, maka bagian-bagian tersebut dipisahkan oleh 6 pemisah.
Contoh 3 (2) • Memilih 5 uang kertas sama artinya dengan menempatkan 6 pemisah dalam 11 tempat (5* + 6|). | | | ** | | | ***
: 3 $1 + 2 $10
*| * | ** | | * | |
: $5 + 2 $20 + $50 + $100
Jadi banyaknya cara memilih 5 uang kertas = banyaknya cara menempatkan 6 pemisah dalam 11 tempat = C(11,6) = 462.
Kombinasi dengan Pengulangan (2) Teorema 4. Terdapat C(n+r-1,r) kombinasi-r dari himpunan dengan n anggota yang memperbolehkan pengulangan anggota. Contoh 4. Ada berapa banyak solusi dari x1 + x2 + x3=11, jika x1, x2, x3 bil bulat nonnegatif ? Solusi. Menghitung solusi = menghitung cara memilih 11 bintang dari himpunan 13 elemen (11 bintang + 2 pemisah). Jadi terdapat C(13,11) macam solusi.
Soal 2 a. Ada berapa banyak solusi dari x1 + x2 + x3 ≤ 11, bila x1, x2, x3 bilangan bulat nonnegatif? b. Ada berapa banyak solusi dari x1 + x2 + x3= 11, bila x1, x2, x3 bilangan bulat dan x1 1, x2 2 dan x3 3 ?
Permutasi dan Kombinasi dengan Pengulangan Tipe
Pengulangan?
Rumus
r-permutasi
Tidak
n! (n r )!
r-kombinasi
Tidak
n! r!(n r )!
r-permutasi
Ya
n
r-kombinasi
Ya
(n r 1)! r!(n 1)!
r
Permutasi dengan Obyek yang Tidak dapat Dibedakan Contoh 5. Ada berapa banyak string yang dapat dibuat dengan mengatur kembali huruf-huruf pada kata SUCCESS ? Solusi. Karena ada beberapa huruf yg sama, maka jawabannya tidaklah sama dengan permutasi 7 huruf. Tapi, banyaknya adalah: C(7,3) utk menempatkan 3 S dalam 7 tempat; C(4,2) utk menempatkan 2 C dalam 4 tempat sisanya; C(2,1) utk menempatkan 1 U dalam 2 tempat sisanya; C(1,1) utk menempatkan 1 E dalam 1 tempat sisanya; Jadi banyak string ada: C(7,3).C(4,2).C(2,1).C(1,1) = 420.
Permutasi dengan Obyek yang Tidak dapat Dibedakan (2) Teorema 5. Jumlah permutasi dari n obyek, di mana terdapat n1 obyek tipe 1, n2 obyek tipe 2, … , dan nk obyek k, adalah: n!
n1!n2! nk !
Distribusi Obyek ke dalam Kotak Contoh 6. Ada berapa banyak cara untuk mendistribusikan satu set kartu pada 4 orang pemain sehingga setiap pemain mendapatkan 5 kartu? Solusi. • Pemain pertama memperoleh 5 kartu dalam C(52,5) cara • Pemain kedua memperoleh 5 kartu dalam C(47,5) cara • Pemain ketiga memperoleh 5 kartu dalam C(42,5) cara • Pemain keempat memperoleh 5 kartu dalam C(37,5) cara • Jadi, secara keseluruhan banyaknya cara adalah C(52,5) . C(47,5) . C(42,5) . C(37,5)
52! 47! 42! 37! 52! 47!5! 42!5! 37!5! 32!5! 5!5!5!5!32!
Distribusi Obyek ke dalam Kotak (2) Teorema 6. Banyaknya cara untuk mendistribusikan n obyek yang dapat dibedakan ke dalam k kotak yang dapat dibedakan sehingga ni buah obyek ditempatkan dalam kotak i, i=1,2,…,k adalah n! n1!n2! nk !
Soal 1. Latihan 6.5.11 Ada berapa cara untuk memilih 8 uang logam dari sebuah celengan yang berisi 100 uang logam Rp. 500 yang identik dan 80 uang logam Rp. 1000 yang identik. (Kombinasi dengan pengulangan - Solusi: 9) 2. Latihan 6.5.17 Ada berapa string dari 10 digit terner (0,1, atau 2) yang memuat tepat dua digit 0, tiga digit 1, dan lima digit 2? (Permutasi dengan obyek yang tidak dapat dibedakan Solusi: 2520)
Soal 3. Latihan 6.5.5 Ada berapa cara untuk memberi 3 pekerjaan kepada 5 pegawai, jika setiap pegawai dapat diberikan lebih dari satu pekerjaan? (Permutasi dengan pengulangan - Solusi: 125) 4. Latihan 6.5.25 Ada berapa banyak bilangan bulat positif yang lebih kecil dari 1000000 dengan jumlah dari digit-digitnya adalah sama dengan 19? (Kombinasi dengan pengulangan - Solusi: 30492)
Soal 5. Latihan 6.5.13 Suatu penerbit mempunyai 3000 buku Matematika Diskrit. Ada berapa cara menyimpan buku-buku tersebut ke dalam tiga gudang jika setiap buku tidak dapat dibedakan? (Kombinasi dengan pengulangan - Solusi: 4504501) 6. Latihan 6.5.39 Ada berapa cara untuk berjalan dari titik (0,0,0) ke (4,3,5) di ruang xyz dengan melangkah sebesar 1 satuan ke arah x positif, 1 satuan ke arah y positif, dan 1 satuan ke arah z positif.
(Permutasi dengan obyek yang tidak dapat dibedakan Solusi: 27720)
Soal 7. Latihan 6.5.9 Suatu toko donat menjual donat polos, donat rasa keju, coklat, stroberi, bluberi, mint, kopi, dan kacang. Ada berapa cara untuk memilih: a) b) c) d)
6 donat? selusin donat? dua lusin donat? Selusin donat dengan paling tidak satu untuk setiap jenisnya? e) Selusin donat dengan paling tidak tiga donat keju dan tidak lebih dari 2 donat kacang?
(Kombinasi dengan pengulangan)
