Inklusi dan Ekslusi dalam Kombinatorika

martha yunanda kombinatorika

Berapa banyak anggota gabungan dua himpunan (asumsikan banyak anggota ke-2 himpunan berhingga)? Banyak anggota gabungan 2 himpunan adalah jumlah ke-2 anggota himpunan dikurangi dengan banyak irisan 2 himpunan itu sendiri. Bisa dibuat rumusan, misal terdapat himpunan A dan himpunan B, maka gabungan 2 himpunan tersebut,

|A U B|=|A|+|B|-|A ∩ B|

Contoh Soal 1:
Dalam sebuah kelas terdapat mahasiswa yang mengambil mata kuliah kalkulus atau kombinatorika atau ke-duanya. Bila 25 mahasiswa mengambil kelas Kalkulus dan 13 orang mengambil kelas Kombinatorika, sementara 8 mahasiswa mengambil 2 mata kuliah tersebut. Berapa banyak mahasiswa dalam kelas tersebut?

Jawab:
Bisa dimisalkan,
|A |= Kalkulus = 25
|B|= Kombinatorika = 13
|A∩B| = Kalkulus dan Kombinatorika = 8
|A U B|=|A|+|B|-|A ∩ B|
|A U B|= 25+13-8 =30

Contoh soal 2:
Berapa banyak bilangan bulat positif tidak melebihi 1000 yang dapat dibagi oleh 7 atau 11?

Jawab:
|A| = habis dibagi 7 = 1000/7
|B| = habis dibagi 11 = 1000/11
|A∩B| = habis dibagi 7 dan 11 = 1000/(7x11)
Karena 7 dan 11 relatif prima
Dengan rumus di atas didapat |A U B|=220.

Ini yang akan dikembangkan menjadi prinsip inklusi-ekslusi. Sebelumnya untuk banyak anggota gabungan 3 himpunan, misalkan A,B dan C digunakan rumus

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

Kenapa demikian?

Anggota A, B dan C dihitung sekali. |A|+|B|+|C|
Anggota A dan juga anggota B terhitung 2x dari langkah 1, sebab terhitung di A dan terhitung di B. Oleh sebab itu maka harus dikurangi sekali. −|A∩B|
Sama dengan kasus langkah 2 untuk anggota A dan C. −|A∩C|
Juga untuk B dan C. −|B∩C|
Sementara anggota A, B, C belum terhitung sehingga harus dihitung lagi, maka ditambahkan +|A∩B∩C|

Contoh Soal:

Sebuah lembaga pendidikan menyediakan tiga jurusan bahasa yaitu bahasa Inggris, Jepang, dan mandarin. Setiap pelajar dalam lembaga tersebut boleh memilih lebih dari satu jurusan. Misalkan ada 1232 pelajar yang mengambil jurusan bahasa Inggris, 879 orang mengambil jurusan bahasa Jepang, 114 orang mengambil jurusan bahasa Mandarin, 103 orang mengambil jurusan bahasa Inggris dan Jepang, 23 orang mengambil jurusan bahasa Inggris dan mandarin, dan 14 orang mengambil jurusan bahasa Jepang dan Mandarin. Jika jumlah pelajar dalam lembaga itu ada 2092 orang, berapakah banyaknya pelajar yangmengambil jurusan bahasa Inggris, Jepang, dan Mandarin?

Jawab: Misalkan I adalah himpunan pelajar yang mengambil jurusan bahasa Inggris, J adalah himpunan pelajar yang mengambil jurusan bahasa jepang, dan M adalah himpunan pelajar yang mengambil jurusan bahasa mandarin, maka

|S|=1231, |I∩J|=103,|F|=879, |R|=114,|I∩M|=23,|J∩M|=14

dan

|I∪J∪M|=2092

Jika kita mensubstitusikan nilai di atas pada persamaan

|I∪J∪M|=|I|+|J|+|M|−|I∩J|−|I∩M|−|J∩M|+|I∩J∩M|

akan diperoleh

2092=1232+879+114−103−23−14+|I∩J∩M|

Dengan menyelesaikan |I∩J∩M|, diperoleh |I∩J∩M|=7. Jadi, ada 7 pelajar yang mengambil jurusan bahasa Inggris, Jepang, dan Mandarin.

Teorema I:Prinsip Inklusi dan Ekslusi

Bagaimana jika terdapat 4 atau lebih himpunan? Misalkan terdapat n himpunan, bagaimana menentukan banyak gabungan semua himpunan tersebut. Di sini terdapat teorema yang memudahkan anda menentukan gabungan n himpunan.

Misal terdapat $A_1, A_2, A_3,...,A_n$ Himpunan, maka banyak anggota gabungan himpunan tersebut adalah:

$|A_1 \cup A_2 \cup \ldots \cup A_n|=\sum_{1 \leq i \leq n}|A_i| - \sum_{1 \leq i < j \leq n}|A_i \cap A_j| \\ + \sum_{1 \leq i < j < k \leq n}|A_i \cap A_j \cap A_k| - \ldots + (-1)^n |A_1 \cap A_2 \cap \ldots \cap A_n| $

Contoh sederhana ambil untuk 4 himpunan. A1, A2, A3, A4

Jadi, n= 4. maka bisa ditulis,

|A1∪A2∪A3∩A4|=|A1|+|A2|+|A3|+|A4|−|A1∩A2|−|A1∩A3|−|A1∩A4|−|A2∩A3|−|A2∩A4|−|A3∩A4|+|A1∩A2∩A3|+|A1∩A2∩A4|+|A1∩A3∩A4|+|A2∩A3∩A4|−|A1∩A2∩A3∩A4|

Aplikasi Inklusi dan Ekslusi

Terdapat alternatif inklusi-ekslusi yang bisa digunakan dalam penyelesaia masalah mengenai penentuan banyaknya anggota dalam sebuah himpunan yang tak memiliki sifat $P_1, P_2,..., P_n$. Bentuk yang dimaksud adalah:

Misal $A_i$ adalah himpunan bagian yang memuat anggota dengan sifat $P_i$ Banyak anggota dengan semua sifat:

$P_{i1}, P_{i2},..., P_{ik}$ dilambangkan dengan

$N(P_{i1}, P_{i2},..., P_{ik})$

Banyak suku himpunan dengan sifat tersebut bisa ditulis,

$\begin{align*} |A_{i1} \cap A_{i2} \cap \ldots \cap A_{ik}|=N(P_{i1}P_{i2}\dots P_{ik}) \end{align*}$

Jika banyaknya anggota yang tidak memiliki sifat $ P_1,P_2,…,P_n$ dinotasikan dengan $N(P′_1P′_2…P′_n) $dan banyaknya anggota dalam himpunan dinotasikan dengan N, maka

$\begin{align*} N(P'_1P'_2\dots P'_n)=N - |A_1 \cup A_2 \cup \ldots \cup A_n| \end{align*}$

Dengan dasar prinsip inklusi-ekslusi di atas, akan diperoleh,

$\begin{align*} N(P'_1P'_2\dots P'_n)&=N - \sum_{1 \leq i \leq n}N(P_i) + \sum_{1 \leq i < j \leq n}N(P_iP_j) \\ &- \sum_{1 \leq i < j < k \leq n}N(P_iP_jP_k)+ \ldots +(-1)^nN(P_1P_2 \ldots P_n) \end{align*}$

Contoh Soal:

Berapa banyak solusi $x_1+x_2+x_3 =11$ jika semua nilai x positif dengan $x_1≤3$, $x_2≤4$, dan $x_3≤6$?

Jawab:

Untuk menerapkan prinsip inklusi - eksklusi, misalkan sebuah solusi memiliki sifat $P_1$ jika $ x_1>3$, sifat $P_2$ jika $x_2>4$, dan sifat $P_3$ jika $x_3>6$. Banyaknya solusi yang memenuhi pertidaksamaan x1≤3, x2≤4, dan x3≤6 adalah

$ \begin{align*} N(P'_1P'_2P'_3)&=N - N(P_1) - N(P_2) - N(P_3) + N(P_1P_2) \\ &+ N(P_1P_3) + N(P_2P_3) - N(P_1P_2P_3). \end{align*}$

Dengan menggunakan rumus kombinasi (pengulangan diperbolehkan), didapatkan