Pertemuan 6 Kombinatorik [PDF]

Citation preview

Matematika Diskrit …………………………………………………………………………………Wamiliana



BAB II KOMBINATORIK: TEKNIK PENCACAHAN DAN PENGATURAN OBJEK Kombinatorik adalah salah satu cabang dalam matematika diskrit yang mempelajari tentang pengaturan objek-objek. Matematika diskrit mulai dipelajari pada abad ke-17. pada waktu itu pertanyaan-pertanyaan timbul berhubungan dengan permainan, misal rolet, lempar dadu dan lain lain. Teknik penghitungan dan pengaturan objek (enumerasi) merupakan hal yang paling penting dalam matematika diskrit. Kita harus menentukan dan menghitung objek untuk menyelesaikan permasalahan. Sebagai contoh : teknik penghitungan dibutuhkan untuk menentukan apakah jumlah interface protocol pada komputer dalam suatu sistem internet dapat memenuhi kebutuhan. Selain itu, teknik ini juga dapat digunakan untuk menentukan jumlah jabat tangan yang terjadi dalam suatu pesta jika setiap tamu yang datang harus berjabat tangan dengan tamu yang lain, kecuali isterinya sendiri. Masalah lain yang muncul dalam kombinatorik adalah masalah pengaturan dari suatu objek sebagai contoh: berapa cara dapat dilakukan untuk mengatur 7 orang (A,B,C,D,E,F dan G) duduk dalam suatu meja perundingan jika A dan B harus duduk bersebelahan? Contoh lain dari masalah kombinatorik ini adalah masalah penentuan plat kendaraan disuatu daerah atau negara. Misalkan nomor plat kendaraan di Provinsi Lampung dimulai dengan BE dan kemudian diikuti oleh maksimal empat buah angka dan dua buah huruf setelah diberi jarak antara angka dan huruf. Ada berapa kemungkinan yang mungkin untuk memberikan nomor kendaraan jika pengulangan (baik angka maupun huruf diperbolehkan?



PRINSIP PRINSIP DASAR PENGHITUNGAN Dalam kombinatorik, kita harus melakukan penghitungan terhadap semua kemungkinan pengaturan objek. Berikut ini akan diberika dua prinsip dasar penghitungan yang akan banyak digunakan dalam penyelesaikan persoalan penghitungan.



1.



Hukum penjumlahan ( The Sum Rule)



Jika sebuah tugas dapat diselesaikan dalam n1 cara dan tugas lainnya dalam n2 cara dan jika kedua tugas tersebut tidak dapat dilakukan pada saat yang sama maka ada n1 + n2 cara untuk melakukan tugas tersebut. Contoh 1 : Misalkan seorang mahasiswi atau seorang mahasiswa di Jurusan Matematika dipilih untuk menjadi pengurus badan eksekutif mahasiswa. Berapa banyak pilihan yang dapat dilakukan jika ada 137 mahasiswi dan 153 mahasiswa di Jurusan matemartika? Jawab: Tugas pertama memilih seorang mahasiswi dapat dilakukan dengan 137 cara dan tugas lainnya memilih seorang mahasiswa dapat dilakukan dengan 153 cara sehingga total cara yang dapat dilakukan adalah sebanyak 137 + 153 = 290 cara. Hukum penjumlahan dapat diperoleh untuk diaplikasikan pada lebih dari 2 tugas. Misalkan tugas-tugas t1, T2,…Tm dapat diselesaikan dengan n1,n2,…nm cara, dan tidak ada dua tugas yang dapat diselesaikan dalam waktu yang sama, maka jumlah cara untuk menyelesaikan satu dari tugas ini adalah n1 + n2 +…+ nm cara.



Matematika Diskrit …………………………………………………………………………………Wamiliana Contoh 2 :Seorang pelajar dapat memilih satu tugas komputer dari 3 daftar tugas yang masing masing tugas memuat 25, 15 dan 19 soal yang mungkin. Berapa banyak soal yang dapat dipilih? Jawab: Pelajar tersebut dapat memilih sebuah soal daridaftar pertama sebanyak 25 cara, dari daftar kedua sebanyak 15 cara dan dari daftar ketiga sebanyak 19 cara sehingga total soal yang dapat ia pilih adalah sebanyak 25 + 15 + 19 = 59 buah soal.



2. Hukum Perkalian (The Product Rule) Misalkan sebuah prosedur dapat dibagi dalam dua kegiatan. Jika ada n1 cara untuk melakukan kegiatan pertama dan ada n2 cxara untuk melakukan kegiatan kedua setelah kegiatan pertama selesai maka ada n1. n2 cara untuk melakukan prosedur tersebut. Contoh 1 :Di perumahan “ Aman Damai” terdapat 20 keluarga yang masing-masing keluarga mempunyai 2 orang anak. Ada berapakah jumlah anak yang terdapat di perumahan tersebut? Jawab: Karena ada 20 keluarga di perumahan tersebut dan masing masing keluarga mempunyai 2 orang anak, maka jumlah anak yang ada di perumahan tersebut adalah sebanyak 20 x 2 = 40 orang anak.



Contoh 2: Ada berapa buah bilangan biner yang terdiri dari 3 digit? Jawab:Bilangan biner terdiri atas 0 dan 1, sedangkan jumlah digit yang diinginkan ada 3, maka jumlah bilangan biner yang berbeda yang terdiri dari 3 digit ada sebanyak 23 = 8 buah. Adapaun bilanganbilangan tersebut adalah: 0 = 000 0



0



1



= 001



0



= 010



1 1 0 0



1



= 011 = 100



1



= 101



0



= 110



1 1



= 111



Matematika Diskrit …………………………………………………………………………………Wamiliana Contoh 3 :Terdapat 32 buah komputer mikro pada suatu laboratorium komputer. Setiap komputer mempunyai 18 ports. Ada berapa ports yang berbeda pada laboratorium komputer tersebut? Jawab : Prosedur untuk memilih ports terdiri dari dua bagian, pertama memilih komputer mikro dan kemudian memilih portnya. Total ports yang berbeda adalah sebanyak 32 x 18 = 576 ports.



3. PERMUTASI Permutasi adalah himpunan dari objek-objek yang berbeda yang disusun berdasarkan urutan dari objekobjek tersebut. Suatu pengaturan terurut dari r anggota disebut dengan r- permutasi.



TEOREMA Jumlah r- permutasi dari sebuah himpunan dengan n elemen yang berbeda adalah



𝑛!



P(n,r)=(𝑛−𝑟)! = n



(n-1)(n-2)…(n-r+1) Contoh 1: Misalkan ada 8 orang mengikuti lomba lari. Pemenang pertama mendapat medali emas, kedua medali perak dan ketiga perunggu. Ada berapa cara yang berbeda untuk mendapatkan semua medali ini jika semua orang mempunyai hak yang sama untuk mendapatkan medali tersebut? Jawab:Jumlah cara cara adalah jumlah 3-permutasi dari sebuah himpunan dengan 8 angggota sehingga P(8,3) = 8 x 7 x 6 = 336 cara. Contoh 2 : Ada berapa banyak cara untuk memiih 4 pemain dari 10 pemain untuk bertanding dalam suatu lomba? Jawab : n = 10, dan r = 4. Banyak cara untuk memilih 4 pemain dari 10 pemain yang ada adalah P(10,4) = 10. 9 . 8. 7 = 5040 Contoh 3 : Dua belas ekor kuda sedang berlomba lari. Pemenang lomba hanya 3 ekor kuda, yang akan mendapatkan medali emas, perak, dan perungggu. Ada berapa carakah untuk membagikan medali tersebut? Jawab : n = 12, dan r = 3. Jadi, banyak cara untuk membagikan medali tersebut adalah sebanyak P(8,3) = 8 . 7 . 6 = 336 cara. Contoh 4 :Ada 5 orang Zaire, 4 orang Jepang, dan 3 orang Indonesia duduk berdampingan pada bangku yang memanjang. Ada berapa carakah mereka duduk jika orang yang berkewarganegaraan sama harus duduk berdekatan? Jawab : Cara orang Zaire duduk berdekatan satu sama lain ada 5! cara, orang Jepang 4! Cara, dan orang Indonesia 3! cara. Selain itu, ada 3! cara untuk mengelompokkan mereka berdasarkan kewarganegaraan. Sehingga, total banyaknya cara mereka duduk adalah sebanyak 5! 4! 3! 3! = 103680 cara.



Matematika Diskrit …………………………………………………………………………………Wamiliana



Permutasi Siklis Pada kenyataannya, mungkin saja terjadi suatu permutasi yang melingkar. Misalnya, pada contoh terakhir (contoh 4), orang orang tersebut duduk melingkari suatu meja bundar. Jika ketentuan yang diberikan sama, yaitu mereka yang berkewarganegaraan sama harus duduk berdekatan, maka banyaknya cara mereka duduk adalah sebanyak 5! 4! 3! 2!. Perbedaan pada permutasi siklis ini terletak pada posisi yang melingkar. Sebagai contoh, pada permutasi biasa ABCD dan DABC adalah dua yang berbeda karena A berdampingan dengan D pada DABC, tetapi tidak pada ABCD; akan tetapi pada permutasi siklis ABCD dan DABC adalah sama karena A dan D berdampingan, baik pada ABCD maupun DABC. Jadi, jika terdapat n komponen dan dilakukan permutasi siklis pada n elemen tersebut, banyaknya cara adalah sebanyak ( n – 1) !



Permutasi dengan elemen yang identik. Selain permutasi siklis, terdapat suatu jenis permutasi dimana elemen elemen yang akan dipermutasikan tersebut ada yang identik. Misal, kita ingin melakukan permutasi terhadap kata MAMA. Permutasi dari kata tersebut antara lain adalah AMAM, AAMM, AMMA,MAAM, MAMA, dan MMAA. Perhatikan bahwa A ada sebanyak 2 dan M juga 2 pada kata tersebut. Untuk permutasi yang identik, banyaknya cara diberikan pada teorema berikut : TEOREMA : Banyaknya permutasi dari n objek, dimana ada n1 objek yg identik untuk tipe 1, n2 objek untuk tipe 2, …, dan nk objek untuk tipe k adalah 𝑛 𝑛! 𝑃 (𝑛 𝑛 𝑛 … 𝑛 ) = 𝑛 !𝑛 !𝑛 !…𝑛 ! 1 2 3 𝑘 1 2 3 𝑘 Contoh 1:Berapa banyak string yang dapat dibuat dari kata SUCCESS? Jawab:Banyaknya huruf S ada 3, C ada 2, U dan E masing masing 1, dan total huruf adalah 7, sehingga 7! banyak string yang mungkin adalah = 420 cara. 3!2!1!1!



Contoh 2 : Ada berapa banyak string yang dapat dibuat dari kata SIRRABBAASAKKU Jawab: Banyaknya huruf S ada 2, R ada 2,B ada 2, A ada 4, K ada 2, U dan I masing masing ada 1, 14! dan total ada 14 huruf. Banyaknya string yang mungkin adalah : 2!2!2!2!4!1!1 4. KOMBINASI Suatu r-kombinasi dari anggota-anggota sebuah himpunan adalah penyelesaian secara tidak terurut dari anggota-anggota himpunan tersebut. TEOREMA Jumlah r-kombinasi dari sebuah himpunan dengan n anggota dengan n adalah bilangan bulat positif dan n! 𝑛 r adalah bilangan bulat, 0  r  n adalah: ( ) = C(n,r) = 𝑟 r!(n - r)!



Matematika Diskrit …………………………………………………………………………………Wamiliana Contoh 1:Ada berapa cara untuk menyeleksi 5 pemain dari 10 orang anggota tim olahraga tennis untuk membentuk tim dalam rangka pertandingan persahabatan dengan sekolah yang lain? Jawab:Masalah ini adalah 5-kombinasi dari suatu himpunan dengan 10 anggota. Berdasarkan teorema 10! di atas, maka jumlah cara adalah sebanyak : C (10,5) = = 252 5!(5)! Contoh 2: Ada berapa banyak cara untuk membentuk suatu tim yang terdiri dari 4 dosen matematika dan 3 dosen ilmu komputer jika banyaknya dosen matematika ada 11 orang dan banyaknya dosen ilmu komputer ada 9 orang? Jawab : Karena memilih 4 dosen dari 11 dosen matematika dan 3 dosen dari komputer, maka banyaknya cara untuk 11! 9! membentuk tim tersebut adalah : C(11,4) . C(9,3) = = 27720 7!4! 3!6!



Persoalan Gabungan Sebagaimana telah dijelaskan sebelumnya bahwa sebuah persoalan terkadang bisa diselesaikan dengan hanya menggunakan salah satu cara dari aturan pengisian tempat, permutasi atau kombinasi saja. Tetapi kadang-kadang sebuah persoalan hanya dapat diselesaikan dengan menggunakan gabungan dari beberapa cara tersebut. Berikut beberapa contoh persoalan. Contoh : Ada berapa banyak cara memilih 2 orang wanita dari 5 orang wanita dan 2 orang laki-laki dari 6 orang laki-laki sebagai ketua, wakil ketua dan 2 orang kepala seksi dari suatu organisasi dengan syarat bahwa ketua dan wakil ketua harus laki-laki dan 2 orang kepala seksi harus wanita ? Solusi: 2 orang laki-laki dipilih dari 6 orang laki-laki sebagai ketua dan wakil ketua yang berarti urutan diperhatikan. Maka banyaknya cara memilih ada 6P2 = 30 cara. 2 orang wanita dipilih dari 5 orang wanita sebagai kepala seksi yang berarti urutan tidak diperhatikan. Maka banyaknya cara memilih ada 5C2 = 10 cara. Jadi, banyaknya cara memilih ada 30 x 10 = 300 cara. Kombinasi dengan Pengulangan Misalkan ada n obyek yang akan diletakkan pada r tempat tanpa urutan dengan r ≤ n. Jika disyaratkan bahwa satu tempat hanya bisa menampung paling banyak 1 obyek maka banyaknya cara adalah nCr yang telah kita bahas sebelumnya. Misalkan terdapat n obyek identik dan disyaratkan bahwa seluruh obyek akan dibagikan ke r buah tempat dengan masing-masing tempat dapat tidak ditempati maupun ditempati satu atau lebih obyek. Pertanyaannya adalah ada berapa banyak cara menyusunnya ? Karena identik maka urutan dalam persoalan ini tidak diperhatikan. Taruh n obyek tersebut dalam satu baris. Tambahkan r − 1 batas di antara bola-bola tersebut sehingga kini seolah-olah ada n + r − 1 ’tempat’. Akibat penambahan r − 1 batas tersebut maka n bola tersebut akan terbagi dalam r bagian, yaitu di sebelah kiri batas ke-1, di antara batas ke-1 dan ke-2 sampai dengan di sebelah kanan batas ke-(r − 1). Masing-masing bagian tersebut melambangkan banyaknya bola pada masing-masing



Matematika Diskrit …………………………………………………………………………………Wamiliana tempat. Sehingga persoalannya sekarang adalah memilih (r − 1) tempat dari n + r − 1 tempat yang tersedia. Banyaknya cara adalah 𝑛+𝑟−1 𝑛+𝑟−1 ( )=( ) 𝑟−1 𝑛 Contoh : 4 buah bola akan dibagikan seluruhnya ke dalam 3 buah kantong. Ada berapa banyak cara menyusunnya ? Solusi : Sebagaimana penjelasan sebelumnya, banyaknya cara = 4+3-1C4 = 6C4 = 15 cara. Yang kalau dijabarkan susunannya adalah (4,0,0), (3,1,0), (3,0,1), (2,2,0), (2,0,2), (2,1,1), (1,3,0), (1,2,1), (1,1,2), (1,0,3), (0,4,0), (0,3,1), (0,2,2), (0,1,3) dan (0,0,4) dengan (a,b,c) menyatakan kantong pertama berisi a bola, kantong ke-2 berisi b bola dan kantong ke-3 berisi c bola. Kombinasi dengan pengulangan juga dapat menyelesaikan persoalan mengenai perhitungan banyaknya penyelesaian persamaan linier. Misalkan saja terdapat persamaan x1 + x2 + ⋅⋅⋅ + xr = n. Jika xi merupakan bilangan bulat tak negatif, maka ada berapa banyak penyelesaian yang memenuhi. Persoalan ini sama saja dengan membagi n obyek identik ke dalam r buah tempat. Banyaknya penyelesaian adalah n+r-1Cn.



Soal soal : 1. Ada berapa cara untuk menyusun huruf huruf abcdef jika penyusunan itu harus diakhiri oleh huruf a? 2. Berapa banyak bit string yang panjangnya 10 dan memuat : a. Tepat empat 1? b. Paling banyak empat 1? c. Paling sedikit empat 1? d. 0 dan 1 yang sama banyaknya? 3. Ada berapa banyak untai (string) biner yang panjangnya 7? 4. A adalah suatu himpunan dengan 100 anggota. Ada berapa banyak himpunan bagian dari A yang terdiri dari paling sedikit dua anggota ? 5. Sekelompok orang terdiri dari n perempuan dan n laki laki. Ada berapa cara untuk mengatur mereka duduk berjajar jika: a. Perempuan dan laki laki duduk berselang seling? b. Perempuan harus duduk berdekatan? 6. Ada berapa banyak plat nomor kendaraan yang mungkin dikeluarkan oleh pemerintah negeri Dongeng jika plat tersebut dimulai dengan huruf DO dan kemudian diikuti oleh maksimal 4 angka dan diakhiri dengan dua huruf. 7. Sebuah keranjang berisi 12 kelereng hitam dan 15 hijau. Tentukanlah ada berapa cara 5 kelereng dapat diambil dari keranjang jika