Dalam analisis kombinatorial, menghitung jumlah elemen dalam suatu himpunan atau peristiwa sering kali menjadi tantangan yang rumit. Ketika kita berhadapan dengan masalah yang melibatkan himpunan dengan elemen yang tumpang tindih, menghitung jumlah elemen secara langsung bisa menyebabkan duplikasi. Untuk mengatasi masalah ini, salah satu metode yang sangat berguna adalah Prinsip Inklusi-Eksklusi (PIE). Prinsip ini memungkinkan kita untuk menghitung ukuran gabungan beberapa himpunan dengan menghindari perhitungan ganda pada elemen yang beririsan.

Apa itu Prinsip Inklusi-Eksklusi?

Prinsip inklusi-eksklusi adalah teknik yang digunakan untuk menghitung jumlah elemen dalam gabungan beberapa himpunan, dengan memperhitungkan interseksi atau tumpang tindih antar himpunan. Prinsip ini dinyatakan dengan rumus dasar untuk dua himpunan AAA dan BBB:∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| – |A \cap B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

Di sini, ∣A∣|A|∣A∣ dan ∣B∣|B|∣B∣ adalah jumlah elemen dalam himpunan AAA dan BBB, sementara ∣A∪B∣|A \cup B|∣A∪B∣ adalah jumlah elemen dalam gabungan kedua himpunan tersebut. Pengurangan ∣A∩B∣|A \cap B|∣A∩B∣ diperlukan untuk menghilangkan duplikasi elemen yang ada di kedua himpunan.

Rumus ini dapat diperluas ke lebih banyak himpunan. Untuk tiga himpunan AAA, BBB, dan CCC, prinsip inklusi-eksklusi dapat dinyatakan sebagai:∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A \cup B \cup C| = |A| + |B| + |C| – |A \cap B| – |A \cap C| – |B \cap C| + |A \cap B \cap C|∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

Prinsip ini dapat diterapkan pada lebih banyak himpunan dengan pola yang serupa: kita menambahkan ukuran setiap himpunan, kemudian mengurangkan ukuran interseksi dua himpunan, menambahkan kembali interseksi dari tiga himpunan, dan seterusnya.

Contoh Penerapan Prinsip Inklusi-Eksklusi

Salah satu aplikasi klasik dari prinsip inklusi-eksklusi adalah menghitung berapa banyak bilangan bulat antara 1 dan 100 yang habis dibagi oleh 2, 3, atau 5.

Langkah-langkah:

1. Definisikan Himpunan: Misalkan AAA adalah himpunan bilangan yang habis dibagi oleh 2, BBB adalah himpunan bilangan yang habis dibagi oleh 3, dan CCC adalah himpunan bilangan yang habis dibagi oleh 5.
2. Hitung Ukuran Setiap Himpunan:
   • Banyaknya bilangan antara 1 hingga 100 yang habis dibagi oleh 2 adalah ∣A∣=⌊1002⌋=50|A| = \left\lfloor \frac{100}{2} \right\rfloor = 50∣A∣=⌊2100​⌋=50.
   • Banyaknya bilangan yang habis dibagi oleh 3 adalah ∣B∣=⌊1003⌋=33|B| = \left\lfloor \frac{100}{3} \right\rfloor = 33∣B∣=⌊3100​⌋=33.
   • Banyaknya bilangan yang habis dibagi oleh 5 adalah ∣C∣=⌊1005⌋=20|C| = \left\lfloor \frac{100}{5} \right\rfloor = 20∣C∣=⌊5100​⌋=20.
3. Hitung Ukuran Interseksi:
   • Banyaknya bilangan yang habis dibagi oleh 6 (kelipatan 2 dan 3) adalah ∣A∩B∣=⌊1006⌋=16|A \cap B| = \left\lfloor \frac{100}{6} \right\rfloor = 16∣A∩B∣=⌊6100​⌋=16.
   • Banyaknya bilangan yang habis dibagi oleh 10 (kelipatan 2 dan 5) adalah ∣A∩C∣=⌊10010⌋=10|A \cap C| = \left\lfloor \frac{100}{10} \right\rfloor = 10∣A∩C∣=⌊10100​⌋=10.
   • Banyaknya bilangan yang habis dibagi oleh 15 (kelipatan 3 dan 5) adalah ∣B∩C∣=⌊10015⌋=6|B \cap C| = \left\lfloor \frac{100}{15} \right\rfloor = 6∣B∩C∣=⌊15100​⌋=6.
   • Banyaknya bilangan yang habis dibagi oleh 30 (kelipatan 2, 3, dan 5) adalah ∣A∩B∩C∣=⌊10030⌋=3|A \cap B \cap C| = \left\lfloor \frac{100}{30} \right\rfloor = 3∣A∩B∩C∣=⌊30100​⌋=3.
4. Terapkan Prinsip Inklusi-Eksklusi: Menggunakan rumus untuk tiga himpunan:

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A \cup B \cup C| = |A| + |B| + |C| – |A \cap B| – |A \cap C| – |B \cap C| + |A \cap B \cap C|∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣ =50+33+20−16−10−6+3=74= 50 + 33 + 20 – 16 – 10 – 6 + 3 = 74=50+33+20−16−10−6+3=74

Jadi, ada 74 bilangan antara 1 dan 100 yang habis dibagi oleh 2, 3, atau 5.

Aplikasi Lain Prinsip Inklusi-Eksklusi

Prinsip Inklusi-Eksklusi memiliki aplikasi luas dalam berbagai masalah kombinatorik. Beberapa contoh aplikasinya meliputi:

1. Teori Graf: Menghitung jumlah pasangan simpul yang terhubung atau menghitung jumlah siklus dalam graf.
2. Teori Bilangan: Menghitung banyaknya bilangan yang tidak habis dibagi oleh beberapa bilangan prima menggunakan fungsi totient Euler.
3. Pengaturan Permutasi: Prinsip ini juga sering digunakan dalam masalah permutasi dengan batasan, seperti menghitung jumlah permutasi tanpa elemen yang tetap (derangements).

Kesimpulan

Prinsip Inklusi-Eksklusi adalah alat yang sangat kuat dalam analisis kombinatorik untuk menghitung ukuran gabungan beberapa himpunan dengan menghindari perhitungan ganda pada elemen yang beririsan. Dengan menerapkan prinsip ini, kita dapat menyelesaikan berbagai masalah yang melibatkan himpunan tumpang tindih secara efisien. Prinsip ini tidak hanya relevan dalam teori, tetapi juga memiliki aplikasi praktis di banyak bidang seperti teori bilangan, graf, dan pengolahan data

sumber : Tucker, A. (2002). Applied Combinatorics. John Wiley & Sons.