Perluasan permutasi dan kombinasiPermutasi dengan pengulanganKombinasi dengan pengulanganPermutasi dengan obyek yang tidak dapat dibedakanDistribusi obyek ke dalam kotakPermutasi dengan pengulanganContoh 1Berapa banyak string panjang n yang dapat dibentuk dari alfabet ? Karena ada 26 huruf dalam alfabet dan karena setiap huruf dapat digunakan berulang maka ada 26nstring panjang n.Teorema 3Jumlah permutasi-r dari himpunan dengan nanggota yang memperbolehkan pengulangan adalah nr.Kombinasi dengan pengulanganContoh 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.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 masing-masing 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 Memilih 5 uang kertas sama artinya dengan menempatkan 6 pemisah dalam 11 tempat (5* + 6|).| | | ** | | | ***:3 $1 + 2 $10*| * | ** | | * | | :$5 + 2 $20 + $50 + $100Jadi banyaknya cara memilih 5 uang kertas = banyaknya cara menempatkan 6 pemisah dalam 11 tempat = C(11,6) = 462.Contoh 3 (2) Kombinasi dengan pengulangan (2)Teorema 4Terdapat C(n+r-1,r) kombinasi-r dari himpunan dengan n anggota yang memperbolehkan pengulangan anggota.Contoh 4Ada berapa banyak solusi darix1 + x2 + x3=11, jika x1, x2, x3 bil bulat nonnegatif ?SolusiMenghitung solusi = menghitung cara memilih 11 bintangdari himpunan 13 elemen (11 bintang + 2 pemisah). Jadi terdapat C(13,11) macam solusi.Soal 1Apakah hubungan antara solusi x1 + x2 + x3 + x4 = 6, xi bilangan bulat nonnegatif, dengan lintasan terpendek antara A dan B pada grid ini?

a. Ada berapa banyak solusi darix1 + x2 + x3 > 11, bila x1, x2, x3 bilangan bulat nonnegatif?b. Ada berapa banyak solusi darix1 + x2 + x3= 11, bila x1, x2, x3 bilangan bulat dan x1K 1, x2K 2 dan x3K 3 ?Soal 2Solusi:a. Tambahkan variabel baru y yang bernilai bulat nonnegatif, sehingga didapat persamaanx1 + x2 + x3 +y = 11.Solusi pada persamaan diatas sama banyakdengan solusi pada pertaksamaan semula.b. Definisikan y1 = x1-1, y2 = x2-2, dan y3 = x3-3.Maka yi adalah bilangan bulat nonnegatif.x1 + x2 + x3= 11(y1+1) +(y2+2) + (y3+3) = 11 y1+ y2 + y3 = 5.

Permutasi dan kombinasi dengan pengulanganTipe Pengulangan? Rumusr-permutasi Tidakr-kombinasi Tidakr-permutasi Yar-kombinasi Ya)! (!7 33

)! 1 ( !)! 1 (

3 77 3)! ( !!7 3 73

73Contoh 5Ada berapa banyak string yang dapat dibuat dengan mengatur kembali huruf-huruf pada kata SUCCESS?SolusiKarena 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 tak dapat dibedakanTeorema 5Jumlah permutasi dari n obyek, di mana terdapat n1 obyek tipe 1, n2 obyek tipe 2, . , dan nk obyek k, adalah:! ! !!2 1 3 3 33

Permutasi dengan obyek yang tak dapat dibedakan (2)Distribusi obyek ke dalam kotakContoh 6Ada 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 adalahC(52,5) . C(47,5) . C(42,5) . C(37,5)! 32 ! 5 ! 5 ! 5 ! 5! 52! 5 ! 32! 37! 5 ! 37! 42! 5 ! 42! 47! 5 ! 47! 52 c c c Distribusi obyek ke dalam kotakTeorema 6Banyaknya cara untuk mendistribusikan nobyek yang dapat dibedakan ke dalam kkotak yang dapat dibedakan sehingga nibuah obyek ditempatkan dalam kotak i, i=1,2,.,k adalah! ! !!2 1 3 3 33

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. BuktiMenghitung 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 yjadalah C(n,n-j).Koefisien BinomialKoefisien Binomial (2)Akibat 1 1. C(n,j) = C(n,n-j).2. C(n,0) + C(n,1) + . + C(n,n) = 2n.33

3

3 3 3 ) , ( 2 . 40 ) , ( ) 1 ( . 300

Bukti1. 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.Koefisien Binomial (3) Perhatikan bahwa:ruas kanan Akibat 1 Bag. 2 menyatakan banyaknya subhimpunan dari himpunan dengan n anggota. Dari ruas kiri kita peroleh bahwa subhimpunan ini dapat dikelompokkan berdasarkan banyaknya anggota.Akibat 1 Bag. 3 menyatakan bahwa subhimpunan berukuran ganjil sama banyak dengan subhimpunan berukuran genap.

dentitas dan Segitiga Pascaldentitas PascalMisal n dan k bilangan bulat positif, nK k. Maka, C(n+1,k) = C(n,k-1) + C(n,k).Bukti Pandang T himpunan dengan n+1 elemen, aZT. Misal S = T-{ak>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

7

3 7 27 3 2 0) , ( ) , ( ) , (

7

3 7 2 0) , ( ) , (Soal 3BuktikanC(2n,n) = C(n,0)2+ C(n,1)2+ . + C(n,n)2dengan 3 cara:1. Menggunakan dentitas Vandermonde.2. Memandang pemilihan n orang dari 2norang yg terdiri dari n pria dan n wanitaSoal-soal1. Latihan 4.5.11Ada 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. (Solusi: 9)2. Latihan 4.5.17Ada berapa string dari 10 digit terner (0,1, atau 2) yang memuat tepat dua digit 0, tiga digit 1, dan lima digit 2? (Solusi: 2520)3. Latihan 4.5.25Ada berapa banyak bilangan bulat positif yang lebih kecil dari 1000000 dengan jumlah dari digit-digitnya adalah sama dengan 19?4. Latihan 4.5.13Suatu penerbit mempunyai 3000 buku Matematika Diskrit. Ada berapa cara menyimpan buku-buku tersebut ke dalam tiga gudang jika setiap buku tidak dapat dibedakan? (Solusi: 4504501)5. Latihan 4.5.39Ada 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.