CHAPTER 6
COUNTING
Combinatorics dan Counting • Kombinatorik – Ilmu yang mempelajari pengaturan obyek – Bagian penting dari Matematika Diskrit – Mulai dipelajari di abad 17
• Enumerasi – Penghitungan obyek dengan sifat tertentu – Bagian penting dari Kombinatorik 2
Contoh Permasalahan dalam Counting “Password dalam suatu sistem komputer terdiri dari 6, 7, atau 8 karakter. Setiap karakter adalah digit bilangan desimal atau huruf dalam alfabet. Setiap pasword harus memuat paling sedikit satu digit bilangan desimal. Ada berapa banyak password yang berbeda?” “Berapa banyak cara yang mungkin dilakukan dalam memilih 11 pemain dalam suatu tim sepak bola yang memiliki 20 pemain?” Selain itu, counting adalah dasar dalam perhitungan peluang kejadian diskrit. (“Berapakah peluang untuk dapat memenangkan suatu lotere?”) 3
6.1 THE BASICS OF COUNTING
4
Dasar-dasar Counting • Aturan perkalian • Aturan penjumlahan • Aturan pengurangan (Prinsip inklusieksklusi) • Aturan pembagian • Diagram pohon 5
Aturan Perkalian Aturan perkalian dipergunakan untuk suatu prosedur yang terbagi menjadi beberapa pekerjaan yang terpisah.
Misalkan suatu prosedur dapat dibagi menjadi dua pekerjaan yang berurutan. Jika terdapat n1 cara untuk melakukan tugas pertama dan n2 cara untuk melakukan tugas kedua setelah tugas pertama selesai dilakukan, maka terdapat n1 n2 cara untuk melakukan prosedur tersebut. 6
Contoh 1 Kursi dalam suatu auditorium dilabeli dengan satu huruf kapital diikuti dengan bilangan bulat positif yang tidak melebihi 100. Berapa banyak kursi yang dapat dilabeli secara berbeda? Solusi. Prosedur pelabelan dapat dibagi menjadi 2 pekerjaan: melabeli dengan salah satu dari 26 huruf kapital, dan kemudian melabeli dengan salah satu dari 100 bilangan bulat positif yang mungkin. Menurut Aturan Perkalian, terdapat 26 · 100 = 2600 cara yang berbeda untuk melabeli. Jadi, banyak kursi yang dapat dilabeli secara berbeda paling banyak adalah 2600. 7
Generalisasi Aturan Perkalian Jika suatu prosedur terdiri dari barisan pekerjaan T1, T2, …, Tm yang dapat dilakukan dalam n1, n2, …, nm cara, secara berurutan, maka terdapat n1 n2 … nm cara untuk melaksanakan prosedur tersebut.
8
Contoh 2 Ada berapa banyak plat nomor kendaraan berbeda yang memuat tepat satu huruf, tiga digit desimal, dan dua huruf? Solusi. Terdapat 26 kemungkinan untuk memilih huruf pertama, 10 untuk memilih digit pertama, 10 untuk digit kedua, dan 10 untuk digit ketiga, kemudian 26 kemungkinan untuk memilih huruf kedua dan 26 untuk huruf ketiga. Jadi, terdapat paling banyak 26 10 10 10 26 26 = 17576000 plat nomor kendaraan yang berbeda. 9
Soal 1 1. Ada berapa fungsi dari himpunan dengan m anggota ke himpunan dengan n anggota? 2. Ada berapa fungsi satu-satu dari himpunan dengan m anggota ke himpunan dengan n anggota? 3. Gunakan aturan perkalian untuk menunjukkan bahwa banyaknya subhimpunan yang berbeda dari suatu himpunan hingga S adalah 2|S|.
10
Soal 2 4. Berapa nilai k setelah program berikut dieksekusi?
11
Aturan Penjumlahan Jika suatu pekerjaan dapat dilaksanakan dengan n1 cara dan pekerjaan kedua dengan n2 cara; serta jika kedua pekerjaan ini tidak dapat dilakukan dalam waktu yang bersamaan, maka terdapat n1 + n2 cara untuk melakukan salah satu pekerjaan tersebut. Contoh 3. Prodi Matematika akan menghadiahkan sebuah komputer kepada seorang mahasiswa atau seorang dosen. Ada berapa cara memberi hadiah, jika terdapat 532 mahasiswa dan 54 dosen? Solusi. Terdapat 532 + 54 = 586 cara. 12
Generalisasi Aturan Penjumlahan Jika terdapat pekerjaan T1, T2, …, Tm yang dapat dilakukan dalam n1, n2, …, nm cara, dan tidak ada dua di antara pekerjaan tersebut yang dapat dilakukan dalam waktu yang bersamaan, maka terdapat n1 + n2 + … + nm cara untuk melakukan salah satu pekerjaan tersebut.
Soal 3. Seorang mahasiswa dapat memilih satu tugas Matematika Diskrit dari tiga buah daftar, yang masingmasing berisikan 9, 21, dan 17 tugas. Ada berapa tugas yang dapat dipilih mahasiswa tersebut? 13
Soal 4 Berapa nilai k setelah program berikut dieksekusi?
14
Aturan dalam Notasi Himpunan Aturan penjumlahan dan perkalian juga dapat direpresentasikan dalam notasi himpunan. Aturan perkalian Misalkan A1, A2, …, Am himpunan hingga. Maka banyaknya cara untuk memilih satu anggota dari hasil kali Cartesian A1 A2 … Am sama dengan banyaknya cara memilih satu anggota dari A1, satu anggota dari A2, …, dan satu anggota dari Am. |A1 A2 … Am | = |A1| |A2| … |Am|. Aturan penjumlahan Misalkan A1, A2, …, Am himpunan yang saling lepas. Banyaknya cara untuk memilih anggota dari gabungan A1 A2 … Am adalah jumlah dari banyaknya anggota setiap himpunan. |A1 A2 … Am | = |A1| + |A2| + … + |Am|. 15
Soal 4 Setiap pengguna suatu sistem komputer memiliki sebuah password, yang terdiri dari 6 sampai 8 karakter, dengan setiap karakter adalah huruf kapital atau digit bilangan desimal. Jika setiap password harus memuat minimal satu digit bilangan desimal, ada berapa banyak password yang mungkin?
16
Aturan Pengurangan (Prinsip Inklusi-Eksklusi) Contoh 4. Berapa banyak string biner dengan panjang 8 yang dimulai dengan 1 atau berakhir dengan 00? Solusi. Pekerjaan 1: Konstruksi string biner dengan panjang 8 yang dimulai dengan 1. Terdapat satu cara untuk memilih bit pertama (1), dua cara untuk memilih bit kedua (0 or 1), dua cara untuk memilih bit ketiga (0 or 1), . . . dua cara untuk memilih bit kedelapan (0 or 1). Aturan perkalian: Pekerjaan 1 dapat dilakukan dengan 127 = 128 cara. 17
Prinsip Inklusi-Eksklusi (2) Pekerjaan 2: Konstruksi string biner dengan panjang 8 yang berakhir dengan 00. Terdapat dua cara untuk memilih bit pertama (0 or 1), dua cara untuk memilih bit kedua (0 or 1),
. . .
dua cara untuk memilih bit keenam (0 or 1), satu cara untuk memilih bit ketujuh (0), dan satu cara untuk memilih bit kedelapan(0).
Aturan perkalian: Pekerjaan 2 dapat dilakukan dalam 26.1.1 = 64 cara. 18
Prinsip Inklusi-Eksklusi (3) Karena terdapat 128 cara untuk melakukan Pekerjaan 1 dan 64 cara untuk melakukan Pekerjaan 2, apakah ini berarti bahwa terdapat 192 string biner dengan yang dimulai dengan 1 atau berakhir dengan 00?
Tidak, karena di sini Pekerjaan 1 dan Pekerjaan 2 dapat dilakukan pada waktu yang bersamaan. Ketika kita melaksanakan Pekerjaan 1 dan membuat string yang dimulai dengan 1, beberapa dari string tersebut diakhiri dengan 00. Jadi, kita kadangkala melakukan Pekerjaan 1 dan 2 pada saat yang bersamaan, sehingga aturan penjumlahan tidak berlaku.
19
Prinsip Inklusi-Eksklusi (4) Jika kita ingin menggunakan aturan penjumlahan dalam kasus ini, kita harus mengurangkan kasus-kasus di mana Pekerjaan 1 dan 2 dilaksanakan pada saat yang bersamaan. Ada berapa kasus, yaitu, ada berapa banyak string yang dimulai dengan 1 dan diakhiri dengan 00? Terdapat satu cara untuk memilih bit pertama (1), dua cara untuk memilih bit kedua, …, bit keenam (0 atau 1), dan satu cara untuk bit ketujuh dan kedelapan (0). Aturan perkalian: Dalam 25 = 32 kasus, Pekerjaan 1 dan 2 dilaksanakan pada saat yang sama.
20
Prinsip Inklusi-Eksklusi (5) Karena terdapat 128 cara untuk menyelesaikan Pekerjaan 1 dan 64 cara untuk menyelesaikan Pekerjaan 2, dan dalam 32 dari kasus-kasus tersebut Pekerjaan 1 dan 2 diselesaikan pada saat yang bersamaan, maka terdapat 128 + 64 – 32 = 160 cara untuk melakukan salah satu di antara kedua pekerjaan tersebut. Dalam teori himpunan, ini berkorespondensi dengan himpunan A1 dan A2 yang tidak saling lepas. Maka: |A1 A2| = |A1| + |A2| - |A1 A2| Ini disebut prinsip inklusi-eksklusi.
21
Aturan Pembagian Terdapat n/d cara untuk melakukan suatu pekerjaan jika pekerjaan tersebut dapat dilakukan dengan menggunakan prosedur yang dapat dikerjakan dengan n cara, dan untuk setiap cara w, terdapat tepat d cara yang berkorespondensi dengan w. Dalam bahasa himpunan: Jika himpunan hingga A merupakan gabungan dari subhimpunan saling lepas yang masing-masing memiliki d anggota, maka n = |A|/d.” 22
Contoh 5 Ada berapa cara berbeda untuk menempatkan 4 orang dalam suatu meja bundar, di mana 2 pengaturan tempat duduk dianggap sama jika setiap orang memiliki tetangga kiri dan tetangga kanan yang sama? Solusi. Ambil satu kursi secara sebarang dan labeli dengan 1, kemudian kursi yang lain dilabeli secara urut searah jarum jam. Jelas terdapat 4 cara memilih orang untuk duduk di kursi 1, 3 cara di kursi 2, 2 cara di kursi 3, dan 1 cara di kursi 4. Sehingga, terdapat 4! = 24 cara untuk menempatkan 4 orang dalam kursi tersebut. Namun demikian, setiap pilihan dari 4 cara penempatan dalam kursi 1 akan memberikan pengatudan yang sama, sehingga menurut aturan pembagian, terdapat 24/4 = 6 penempatan yang 23 berbeda.
Diagram Pohon Soal 4. Ada berapa string biner dengan panjang empat yang tidak memiliki dua 1 secara berurutan? bit ke-1
bit ke-2
bit ke-3
0
0 1
0 1
0
bit ke-4
0 1
0 0 1
1
0
0 1
0 1 0
Jadi, terdapat 8 string. 24
6.2 THE PIGEONHOLE PRINCIPLE
25
Ada Lebih Banyak Merpati Dibanding Sarangnya
13 merpati dan 12 sarang 26
Prinsip Sarang Merpati Jika (k + 1) atau lebih obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat dua atau lebih obyek tersebut. Bukti. Akan dibuktikan dengan menggunakan kontradiksi. Andaikan tidak ada kotak yang memuat lebih dari 1 obyek. Karena terdapat k kotak, banyaknya obyek paling banyak adalah k. Suatu kontradiksi karena terdapat paling sedikit (k+1) obyek.
Contoh 1 1. Jika terdapat 11 pemain dalam sebuah tim sepakbola yang menang dengan angka 12-0, maka terdapat paling sedikit satu pemain yang membuat minimal dua gol. 2. Jika Anda menghadiri 6 kuliah dalam selang waktu Senin sampai Jumat, maka terdapat paling sedikit satu hari ketika Anda menghadiri paling sedikit dua kuliah. 3. Dalam suatu kelompok beranggotakan 367 orang, paling tidak ada 2 orang yang memiliki tanggal dan bulan kelahiran yang sama. 28
Soal 1
Tunjukkan bahwa untuk setiap bilangan bulat n terdapat kelipatan dari n yang hanya terdiri dari digit 0 atau digit 1 saja.
Generalisasi Prinsip Sarang Merpati Jika N obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat sedikitnya N/k obyek. Bukti. ? Contoh 2. Di dalam kelas dengan 60 mahasiswa, terdapat paling sedikit 12 mahasiswa akan mendapat nilai yang sama (A, B, C, D, atau E).
Contoh 3. Di dalam kelas dengan 61 mahasiswa, paling sedikit 13 mahasiswa akan memperoleh nilai yang sama.
Soal 2 1. Berapa jumlah minimum mahasiswa di dalam kelas Matematika Diskrit agar sedikitnya 6 orang memperoleh nilai yang sama? 2. Berapa jumlah minimum kode area yang dibutuhkan agar terdapat 25 juta nomor telepon dengan 10 digit yang berbeda? (Asumsikan bahwa nomor telepon dalam bentuk NXX-NXX-XXXX, di mana 3 digit pertama adalah kode area, N merepresentasikan digit dari 2 sampai 9 dan X merepresentasikan digit sebarang)
Contoh 4 Misalkan ada laci yang berisi selusin kaus kaki coklat dan selusin kaus kaki hitam yang didistribusikan secara acak. Pada saat listrik padam, berapa kaus kaki yang harus Anda ambil untuk memastikan bahwa di antaranya terdapat sepasang kaus yang sewarna? Solusi. Terdapat dua tipe kaus kaki, jadi jika anda memilih paling sedikit 3 kaus kaki, haruslah terdapat paling sedikit dua kaus kaki coklat atau paling sedikit dua kaus kaki hitam . Generalisasi Prinsip Sarang Merpati : 3/2 = 2.
Aplikasi Prinsip Sarang Merpati 1. Tunjukkan bahwa di antara n+1 bilangan bulat positif yang tidak melebihi 2n, haruslah terdapat suatu bilangan yang membagi salah satu bilangan lainnya. 2. Tunjukkan bahwa setiap barisan n2+1 bilangan real yang berbeda selalu memuat suatu subbarisan dengan panjang n+1 yang monoton naik atau monoton turun.
Teori Ramsey Asumsikan bahwa di dalam suatu kelompok yang terdiri dari 6 orang, setiap pasang terdiri dari dua sahabat atau dua musuh. Tunjukkan bahwa terdapat tiga orang yang saling bersahabat atau tiga orang yang saling bermusuhan dalam kelompok tersebut.
Bilangan Ramsey Bilangan Ramsey R(m,n), dengan m dan n bilangan bulat positif lebih besar atau sama dengan 2, adalah jumlah minimum orang dalam suatu pesta sehingga terdapat m orang yang saling bersahabat atau n orang yang saling bermusuhan, dengan mengasumsikan setiap pasang orang di pesta tersebut adalah sahabat atau musuh.
Bilangan Ramsey (2) Secara umum, sangat sulit menemukan nilai eksak bilangan Ramsey. Untuk setiap bilangan bulat positif n ≥ 2, R(2, n) = n Untuk 3 ≤ m ≤ n, nilai eksak hanya diketahui untuk 9 bilangan Ramsey, termasuk R(4, 4) = 18. Untuk bilangan Ramsey lainnya, hanya diketahui batas atas dan batas bawah. Misalkan 43 ≤ R(5, 5) ≤ 49. 36
