Prinsip Inklusi-Eksklusi dan Prinsip Sarang Merpati

1. Prinsip Inklusi-Eksklusi

A. Untuk 2 himpunan, lalu 3 himpunan

Untuk sebarang dua himpunan A dan B, untuk mendapatkan banyaknya anggota gabungan kedua himpunan, setiap anggota gabungan dihitung satu kali.

Ketika menghitung banyaknya anggota A dan menghitung banyaknya anggota B ada kemungkinan ada anggota kedua himpunan yang dihitung dua kali. Sehingga untuk menghindari hal tersebut dalam menghitung banyaknya anggota gabungan dua himpunan A dan B kita lakukan dengan menghitung jumlah dari banyaknya anggota A dan banyaknya anggota B dan dikurangi dengan banyaknya anggota irisan dari kedua himpunan.

|A ∪ B| = |𝐴| + |B| − |𝐴 ∩ B|

Contoh:

Berapa banyak string biner dengan panjang 8 dimulai dengan bit 1 atau diakhiri dengan bit 00.

Ingat, bahwa string biner pada setiap digitnya dapat diisi dengan 0 atau 1.

|A| = Banyak string biner 8 digit dimulai dengan bit 1 = 1 × 2⁷ = 128

|B| = Banyak string biner 8 digit diakhiri dengan bit 00 = 2⁶ × 1² = 64

|𝐴 ∩ B| = 1 × 2⁵ × 1² = 32

|A ∪ B| = |𝐴| + |B| − |𝐴 ∩ B| = 128 + 64 − 32 = 160.

Sekarang kita akan coba mengembangkan rumus untuk menghitung banyaknya anggota gabungan dari berhingga himpunan. Rumus yang kita kembangkan itu disebut prinsip inklusi-ekslusi.

|A| + |B| + |C|

Kita coba pada tiga himpunan terlebih dahulu. Untuk sebarang tiga himpunan A, B, dan C, ketika menghitung banyaknya anggota A, menghitung banyaknya anggota B dan menghitung banyaknya anggota C ada kemungkinan ada anggota dari A, anggota dari B atau anggota dari C yang dihitung dua kali dan ada yang dihitung 3 kali.

|A| + |B| + |C| − |𝐴 ∩ B| − |𝐴 ∩ C| − |𝐴 ∩ C|

Untuk menghindari menghitung lebih dari satu kali anggota pada irisan himpunan, kita mengurangkan dengan banyaknya anggota irisan semua pasangan himpunan. Dengan cara ini anggota yang dihitung dua kali akan dihitung sekali, tetapi anggota yang dihitung 3 kali akan menjadi dihitung 0 kali.

|A ∪ B ∪ C| = |A| + |B| + |C| − |𝐴 ∩ B| − |𝐴 ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Untukmemperbaiki kekurangan menghitung, kita tambahkan dengan banyaknya anggota irisan dari ketiga himpunan. Dengan demikian sekarang setiap anggota sudah dihitung sekali.

B. Perluasan untuk lebih dari 3 himpunan

Apabila cara yang sama diterapkan pada himpunan yang lebih banyak, akan didapati irisan dari himpunan sebanyak ganjil akan bertanda positif dan irisan dari himpunan sebanyak genap akan bertanda negatif.

|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D| − |𝐴 ∩ B| − |A ∩ C| − |A ∩ D| − |B ∩ C| − |B ∩ D| − |C ∩ D| + |A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| − |A ∩ B ∩ C ∩ D|

dan seterusnya.

Contoh:

1. Berapa banyak solusi dari x₁ + x₂ + x₃ = 11 dimana x₁, x₂, dan x₃ adalah bilangan cacah dengan x₁ ≤ 3

x₂ ≤ 4, dan x₃ ≤ 6?

Pertama, tentukan banyak semua kemungkinan x₁ + x₂ + x₃ = 11 tanpa batasan, yaitu

C(11 + 3 − 1, 11) = C(13, 11) = 13!/(2!11!) = 78.

Kemudian, tentukan banyak kemungkinan solusi yang melanggar satu batasan.

* Banyak solusi dengan x₁ > 3

Kotak 1 dianggap sudah terisi 4, sehingga tersisa 7 kotak, banyak kemungkinannya adalah

C(7 + 3 − 1, 7) = C(9, 7) = 9!/(2!7!) = 36.

* Banyak solusi dengan x₂ > 4

Kotak 2 dianggap sudah terisi 5, sehingga tersisa 6 kotak, banyak kemungkinannya adalah

C(6 + 3 − 1, 6) = C(8, 6) = 8!/(2!6!) = 28.

* Banyak solusi dengan x₃ > 6

Kotak 3 dianggap sudah terisi 7, sehingga tersisa 4 kotak, banyak kemungkinannya adalah

C(4 + 3 − 1, 4) = C(6, 4) = 6!/(2!4!) = 15.

Tentukan banyak kemungkinan solusi yang melanggar dua batasan

* Banyak solusi dengan x₁ > 3 dan x₂ > 4

Kotak 1 dianggap sudah terisi 4 dan kotak 2 dianggap sudah terisi 5, sehingga tersisa 2 kotak, banyak kemungkinannya adalah

C(2 + 3 − 1, 2) = C(4, 2) = 4!/(2!2!) = 6.

* Banyak solusi dengan x₁ > 3 dan x₃ > 6

Kotak 1 dianggap sudah terisi 4 dan kotak 3 dianggap sudah terisi 7, sehingga dapat dipastikan kotak 2 kosong. Jadi, ada 1 kemungkinan.

* Banyak solusi dengan x₂ > 4 dan x₃ > 6

Kotak 2 dianggap sudah terisi 5 dan kotak 3 dianggap sudah terisi 7, ini mustahil terjadi, karena 5 + 7 = 12 > 11. Jadi, ini tidak mungkin.

Tidak mungkin ketiganya dilanggar bersamaan.

Banyak solusi adalah 78 − (36 + 28 + 15) + (6 + 1 + 0) = 78 − 79 + 7 = 6.

2. Tentukan banyak solusi yang memungkinkan dari x₁ + x₂ + x₃ + x₄ = 10 dengan masing-masing merupakan bilangan cacah tidak lebih dari 3.

* Banyak kemungkinan solusi tanpa batasan

C(10 + 4 − 1, 10) = C(13, 10) = 13!/(3!10!) = 286.

* Banyak kemungkinan solusi yang melanggar 1 batasan

C(4, 1) × C(10 − 4 + 4 − 1, 10 − 4) = 4 × C(9, 6) = 336.

* Banyak kemungkinan solusi yang melanggar 2 batasan

C(4, 2) × C(10 − 8 + 4 − 1, 10 − 8) = 6 × C(5, 2) = 60.

Mustahil ada yang melanggar 3 batasan atau lebih.

Banyak solusi adalah 286 − 336 + 60 = 10.

3. Berapa banyaknya bilangan prima yang tidak melebihi 100?

Untuk mencari banyaknya bilangan prima yang tidak lebih dari 100, kita perlu mencari bilangan komposit yang tidak melebihi 100. Karena √100 = 10, bilangan prima yang kurang dari 10 adalah 2, 3, 5, dan 7.

* Banyak kelipatan 2, 3, 5, dan 7 masing-masing ⌊100/2⌋ = 50, ⌊100/3⌋ = 33, ⌊100/5⌋ = 20, dan ⌊100/7⌋ = 14.

* Banyak kelipatan 2 bilangan prima sekaligus dari 2, 3, 5, dan 7.

Banyak kelipatan 2 dan 3 adalah ⌊100/(2.3)⌋ = 16

Banyak kelipatan 2 dan 5 adalah ⌊100/(2.5)⌋ = 10

Banyak kelipatan 2 dan 7 adalah ⌊100/(2.7)⌋ = 7

Banyak kelipatan 3 dan 5 adalah ⌊100/(3.5)⌋ = 6

Banyak kelipatan 3 dan 7 adalah ⌊100/(3.7)⌋ = 4

Banyak kelipatan 5 dan 7 adalah ⌊100/(5.7)⌋ = 2

* Banyak kelipatan 3 bilangan prima sekaligus

Banyak kelipatan 2, 3 dan 5 adalah ⌊100/(2.3.5)⌋ = 3

Banyak kelipatan 2, 3 dan 7 adalah ⌊100/(2.3.7)⌋ = 2

Banyak kelipatan 2, 5 dan 7 adalah ⌊100/(2.5.7)⌋ = 1

Tidak ada kelipatan 3, 5 dan 7 karena 3.5.7 = 105 > 100

Tidak ada kelipatan 2, 3, 5, dan 7 sekaligus karena 2.3.5.7 = 210 > 100

Banyaknya kelipatan 2, 3, 5 atau 7 adalah (50 + 33 + 20 + 14) − (16 + 10 + 7 + 6 + 4 + 2) + (3 + 2 + 1)

= 117 − 45 + 6 = 78

Sehingga banyaknya bilangan bulat 1 - 100 yang bukan kelipatan 2, 3, 5, atau 7 adalah

100 − 78 = 22.

Pertimbangkan bahwa 2, 3, 5, dan 7 merupakan bilangan prima. Sedangkan 1 bukan bilangan prima.

Banyak bilangan prima dari 1 - 100 adalah 22 + 4 − 1 = 25.

4. Berapa banyak bilangan asli dari 1 s/d 1000 yang tidak habis dibagi 4, 5, atau 6?

* Banyak bilangan habis dibagi oleh 1 dari ketiganya

Banyak bilangan habis dibagi oleh 4 adalah ⌊1000/4⌋ = 250

Banyak bilangan habis dibagi oleh 5 adalah ⌊1000/5⌋ = 200

Banyak bilangan habis dibagi oleh 6 adalah ⌊1000/6⌋ = 166

* Banyak bilangan habis dibagi oleh 2 dari ketiganya

Banyak bilangan habis dibagi oleh 4 dan 5 adalah ⌊1000/KPK(4, 5)⌋ = ⌊1000/20⌋ = 50

Banyak bilangan habis dibagi oleh 4 dan 6 adalah ⌊1000/KPK(4, 6)⌋ = ⌊1000/12⌋ = 83

Banyak bilangan habis dibagi oleh 5 dan 6 adalah ⌊1000/KPK(5, 6)⌋ = ⌊1000/30⌋ = 33

* Banyak bilangan habis dibagi oleh tiga-tiganya

Banyak bilangan habis dibagi oleh 4, 5, dan 6 adalah ⌊1000/KPK(4, 5, 6)⌋ = ⌊1000/60⌋ = 16

* Banyak bilangan habis dibagi oleh 4, 5, atau 6

Banyaknya adalah (250 + 200 + 166) − (50 + 83 + 33) + 16 = 616 − 166 + 16 = 466.

* Banyak bilangan tidak habis dibagi oleh 4, 5, atau 6

Ada sebanyak 1000 − 466 = 534.

2. Prinsip Sarang Merpati (Pigeon-hole Principe)

A. Prinsip sarang merpati dasar

"Jika n + 1 atau lebih objek ditempatkan di dalam n buah kotak, maka maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek."

Kalimat ini mungkin masih ada yang belum faham, tetapi kontraposisinya lebih mudah difahami, yaitu "Jika diantara n kotak tidak ada yang berisi lebih dari satu objek, maka banyak seluruh objek tidak lebih dari n.", dimana most case dari kontraposisi ini adalah setiap kotak berisi satu objek, maka banyak seluruh objek adalah sama dengan banyak kotak.

Secara lebih formal, dapat dikatakan bahwa tidak ada fungsi injektif pada himpunan berhingga yang memiliki kodomain lebih kecil daripada domain. Prinsip ini pertama kali dinyatakan oleh Dirichlet pada 1834 dan diberi nama Schubfachprintsip (prinsip rak). Dalam beberapa bahasa, prinsip ini disebut prinsip Dirichlet.

B. Prinsip sarang merpati yang diperluas

"Jika M objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi ⌈M/n⌉ atau lebih objek."

Most case: Misal terdapat sebanyak n buah kotak dengan masing-masing kotak berisi k objek, maka banyak seluruh objek adalah nk.

Contoh:

1. Diantara 100 orang dapat dipastikan ada paling sedikit satu bulan dimana 9 orang atau lebih lahir di bulan tersebut, karena ⌈100/12⌉ = 9.

2. Misal dipilih 51 bilangan berbeda dari 1 sampai 100, akan ada 2 bilangan dijumlahkan menghasilkan 101.

Ini berlaku karena dari 1 sampai 100 terdapat 50 pasangan bilangan yang jumlahnya 101.

1 + 100 = 2 + 99 = ... = 50 + 51 = 101

Dikarenakan dipilih 51 bilangan berbeda, dipastikan paling sedikit ada satu pasangan (berjumlah 101) yang dipilih dua-duanya.