Prinsip Inklusi-Eklusi dalam Kombinatorik: Menghitung Ukuran Set dengan Mudah

Prinsip inklusi-eksklusi adalah teknik yang digunakan dalam kombinatorik untuk menghitung ukuran suatu himpunan dengan memecahnya menjadi himpunan bagian yang lebih kecil dan menghitung perpotongannya. Hal ini didasarkan pada gagasan bahwa jika kita mempunyai dua himpunan, A dan B, dan kita ingin menghitung elemen-elemen yang ada di kedua himpunan, kita dapat melakukannya dengan mengurangkan elemen-elemen yang hanya ada di A dari jumlah total elemen di A. A, lalu menjumlahkan kembali elemen-elemen yang hanya ada di B.

Lebih formalnya, misalkan A dan B adalah dua himpunan, dan misalkan |A| adalah banyaknya elemen pada A. Maka prinsip inklusi-eksklusi menyatakan:

|A ∪ B| = |SEBUAH| + |B| - |A ∩ B|

di mana |A ∪ B| adalah banyaknya anggota gabungan A dan B, dan |A ∩ B| adalah banyaknya anggota yang ada di A dan B.

Ide di balik rumus ini adalah kita dapat menghitung besar gabungan dua himpunan dengan terlebih dahulu menghitung jumlah anggota setiap himpunan secara terpisah, lalu mengurangkan unsur-unsur yang ada di dalam himpunan tersebut. hanya ada di salah satu himpunan (yaitu, elemen di perpotongan). Ini memberi kita jumlah total elemen dalam gabungan, yang merupakan jumlah dari jumlah elemen dalam setiap himpunan dikurangi jumlah elemen yang hanya ada di salah satu himpunan.

Sebagai contoh, katakanlah kita mempunyai dua himpunan: A = {1, 2, 3} dan B = {4, 5, 6}. Untuk menghitung besar gabungannya menggunakan prinsip inklusi-eksklusi, pertama-tama kita menghitung jumlah elemen dalam setiap himpunan secara terpisah:

|A| = 3
|B| = 3

Selanjutnya, kita menghitung banyaknya elemen pada kedua himpunan dengan menghitung perpotongannya:

|A ∩ B| = 2 (karena 1 dan 2 berada pada kedua himpunan)

Sekarang kita dapat menggunakan prinsip inklusi-eksklusi untuk menghitung besar gabungan:

|A ∪ B| = |SEBUAH| + |B| - |A ∩ B|
= 3 + 3 - 2
= 6

Jadi, besar gabungan A dan B adalah 6.

Prinsip inklusi-eksklusi mempunyai banyak penerapan dalam kombinatorik, seperti menghitung banyaknya permutasi, kombinasi, dan penyelesaian ke persamaan. Ini adalah alat yang ampuh untuk memecahkan masalah penghitungan dan dapat digunakan untuk menyederhanakan perhitungan yang rumit.