Prinsip Kemasukan-Pengecualian dalam Kombinatorik: Mengira Saiz Set dengan Mudah

Prinsip rangkuman-pengecualian ialah teknik yang digunakan dalam kombinatorik untuk mengira saiz set dengan memecahkannya kepada subset yang lebih kecil dan mengira persilangannya. Ia berdasarkan idea bahawa jika kita mempunyai dua set, A dan B, dan kita ingin mengira unsur-unsur yang terdapat dalam kedua-dua set, kita boleh melakukannya dengan menolak unsur-unsur yang hanya dalam A daripada jumlah bilangan unsur dalam A, dan kemudian menambah semula unsur-unsur yang hanya dalam B.

Lebih formal, biarkan A dan B menjadi dua set, dan biarkan |A| ialah bilangan elemen dalam A. Kemudian, prinsip inklusi-pengecualian menyatakan bahawa:

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

di mana |A ∪ B| ialah bilangan unsur dalam gabungan A dan B, dan |A ∩ B| ialah bilangan unsur yang terdapat dalam kedua-dua A dan B.

Idea di sebalik formula ini ialah kita boleh mengira saiz gabungan dua set dengan terlebih dahulu mengira bilangan unsur dalam setiap set secara berasingan, dan kemudian menolak unsur-unsur yang hanya dalam salah satu set (iaitu, unsur-unsur dalam persimpangan). Ini memberikan kita jumlah bilangan elemen dalam kesatuan, iaitu jumlah bilangan elemen dalam setiap set tolak bilangan elemen yang hanya dalam salah satu set.

Sebagai contoh, katakan kita mempunyai dua set: A = {1, 2, 3} dan B = {4, 5, 6}. Untuk mengira saiz kesatuan mereka menggunakan prinsip kemasukan-pengecualian, kita mula-mula mengira bilangan elemen dalam setiap set secara berasingan:

|A| = 3
|B| = 3

Seterusnya, kita mengira bilangan unsur yang terdapat dalam kedua-dua set dengan mengira persilangannya:

|A ∩ B| = 2 (memandangkan 1 dan 2 berada dalam kedua-dua set)

Sekarang kita boleh menggunakan prinsip inklusi-pengecualian untuk mengira saiz kesatuan:

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

Jadi, saiz penyatuan A dan B ialah 6.

Prinsip pengecualian-pemasukan mempunyai banyak aplikasi dalam kombinatorik, seperti mengira bilangan pilih atur, gabungan dan penyelesaian kepada persamaan. Ia adalah alat yang berkuasa untuk menyelesaikan masalah mengira dan boleh digunakan untuk memudahkan pengiraan yang rumit.