Prinsip Inklusi-Eksklusi

Pada kesempatan kali ini kita akan membahas tentang prinsip inklusi-eksklusi yang sering digunakan dalam kombinatorika khususnya dalam mencari jumlah seperti himpunan dan probabilitas.

Prinsip Inklusi-Eksklusi. Diberikan himpunan $A_1,A_2,\cdots,A_n$. Definisikan $S_k=\sum_{1\le i_1\le i_2\le \cdots \le i_k\le n}|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|$ yang berarti jumlah semua himpunan yang dipilih sebanyak $k$ dari $n$, maka
$$|A_1\cup A_2\cup \cdots \cup A_n|=S_1-S_2+S_3+\cdots+(-1)^{n-1}S_n$$

Bukti. Misal bilangan $x\in A_1\cup A_2\cup \cdots \cup A_n$ maka $x$ terhitung sekali di ruas kiri, kita akan buktikan jika $x$ juga terhitung sekali di ruas kanan. Misalkan $x\in A_{j_1},A_{j_2},\cdots,A_{j_m}$ dan $x$ tidak berada di himpunan selain mereka. Maka ada ${m \choose k}$ himpunan $A_{i_1},A_{i_2},\cdots,A_{i_k}$ sedemikian hingga $x\in A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}$. Hal ini berarti $x$ terhitung sebanyak ${m \choose k}$ pada jumlahan $\sum_{1\le i_1\le i_2\le \cdots \le i_k\le n}|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|$ dengan kata lain, $x$ terhitung total sebanyak
$${m \choose 1}-{m \choose 2}+{m \choose 3}+\cdots +(-1)^{m-1}{m \choose m}=1+(1-1)^m=1$$
jadi $x$ hanya terhitung sekali di ruas kanan.