Teorema 7.7. Prinsip Inklusi–Eksklusi.
Banyaknya elemen \(X\) yang tidak memenuhi satu pun sifat dalam \(\mathcal{P}\) diberikan oleh
\begin{equation}
\sum_{S\subseteq [m]} (-1)^{|S|}N(S).\tag{7.2.1}
\end{equation}
Subbab 7.2 Rumus Inklusi–Eksklusi
Setelah memahami apa yang dimaksud dengan sebuah sifat, mari kita lihat bagaimana konsep ini dapat digunakan untuk menggeneralisasi proses yang kita pakai pada dua contoh pertama di bagian sebelumnya.
Misalkan \(X\) sebuah himpunan dan \(\mathcal{P}=\{P_1,P_2,\dots,P_m\}\) sebuah keluarga sifat. Kemudian, untuk setiap subhimpunan \(S\subseteq [m]\text{,}\) misalkan \(N(S)\) menyatakan banyaknya elemen \(X\) yang memenuhi sifat \(P_i\) untuk setiap \(i\in S\text{.}\) Perhatikan bahwa jika \(S=\emptyset\text{,}\) maka \(N(S)=|X|\text{,}\) karena setiap elemen \(X\) memenuhi setiap sifat dalam \(S\) (yang sebenarnya tidak memuat sifat apa pun).
Mari sejenak kembali ke Contoh 7.1. Jika \(P_1\) menyatakan sifat “mengambil program studi ilmu komputer” dan \(P_2\) menyatakan sifat “laki-laki”, kita memperoleh bahwa \(N(\{1\})=47\text{,}\) karena terdapat \(47\) mahasiswa yang mengambil program studi ilmu komputer di kelas tersebut. Selain itu, \(N(\{2\})=51\) karena \(51\) mahasiswa adalah laki-laki. Terakhir, \(N(\{1,2\})=45\) karena terdapat \(45\) mahasiswa laki-laki yang mengambil program studi ilmu komputer di kelas tersebut.
Pada contoh-contoh di bagian sebelumnya, kita mengurangkan \(N(S)\) untuk himpunan \(S\) yang berukuran \(1\text{,}\) lalu menambahkan kembali \(N(S)\) untuk himpunan sifat yang berukuran \(2\text{,}\) karena kita telah dua kali mengurangkan banyaknya objek yang memenuhi kedua sifat tersebut (mahasiswa laki-laki yang mengambil program studi ilmu komputer atau solusi dengan \(x_3>7\) sekaligus \(x_4'>8\)). Secara simbolis, kita memperoleh bahwa banyaknya objek yang tidak memenuhi satu pun sifat adalah
\begin{equation*}
N(\emptyset) - N(\{1\}) - N(\{2\}) + N(\{1,2\}).
\end{equation*}
Andaikan kita memiliki tiga sifat \(P_1,P_2\text{,}\) dan \(P_3\text{.}\) Bagaimana kita menghitung banyaknya objek yang tidak memenuhi satu pun sifat tersebut? Seperti sebelumnya, kita mulai dengan mengurangkan banyaknya objek yang memenuhi masing-masing \(P_1\text{,}\) \(P_2\text{,}\) dan \(P_3\text{.}\) Dengan demikian, banyaknya objek yang memenuhi \(P_1\) sekaligus \(P_2\) telah dikurangkan dua kali, sehingga kita harus menambahkan kembali \(N(\{1,2\})\text{.}\) Demikian pula, kita harus melakukan hal yang sama untuk objek yang memenuhi \(P_2\) sekaligus \(P_3\text{,}\) serta objek yang memenuhi \(P_1\) sekaligus \(P_3\text{.}\) Sekarang, mari kita tinjau objek yang memenuhi ketiga sifat tersebut. Objek-objek itu dihitung dalam \(N(\emptyset)\text{,}\) dihilangkan tiga kali oleh suku-suku \(N(\{i\})\text{,}\) lalu ditambahkan kembali tiga kali oleh suku-suku \(N(\{i,j\})\text{.}\) Jadi, objek-objek itu masih dihitung! Oleh karena itu, kita masih harus mengurangkan \(N(\{1,2,3\})\) untuk memperoleh banyaknya objek yang diinginkan:
\begin{equation*}
N(\emptyset) - N(\{1\}) - N(\{2\}) - N(\{3\}) + N(\{1,2\}) +
N(\{2,3\}) + N(\{1,3\}) - N(\{1,2,3\}).
\end{equation*}
Pola ini dapat kita generalisasikan menjadi teorema berikut.
Bukti.
Kita menggunakan induksi pada banyaknya sifat, yaitu \(m\text{.}\) Jika \(m=1\text{,}\) rumus tersebut menjadi \(N(\emptyset)-N(\{1\})\text{.}\) Rumus ini benar karena menyatakan bahwa banyaknya elemen yang tidak memenuhi sifat \(P_1\) sama dengan banyaknya semua elemen dikurangi banyaknya elemen yang memenuhi sifat \(P_1\text{.}\)
Sekarang, andaikan rumus tersebut berlaku apabila \(m\le k\) untuk suatu \(k\ge1\text{,}\) lalu tinjau kasus \(m=k+1\text{.}\) Misalkan \(X'=\{x\in X: x\) memenuhi \(P_{k+1}\}\) dan \(X''=X-X'\) (i.e., \(X''\) adalah himpunan elemen yang tidak memenuhi \(P_{k+1}\)). Selain itu, misalkan \(\mathcal{Q}=\{P_1,P_2,\dots,P_k\}\text{.}\) Kemudian, untuk setiap subhimpunan \(S\subseteq [k]\text{,}\) misalkan \(N'(S)\) menyatakan banyaknya elemen \(X'\) yang memenuhi sifat \(P_i\) untuk setiap \(i\in
S\text{.}\) Selain itu, misalkan \(N''(S)\) menyatakan banyaknya elemen \(X''\) yang memenuhi sifat \(P_i\) untuk setiap \(i\in S\text{.}\) Perhatikan bahwa \(N(S)=N'(S)+N''(S)\) untuk setiap \(S\subseteq
[k]\text{.}\)
Misalkan \(X'_0\) menyatakan himpunan elemen dalam \(X'\) yang tidak memenuhi satu pun sifat dalam \(\mathcal{Q}\) (dengan kata lain, elemen yang hanya memenuhi \(P_{k+1}\) dari \(\mathcal{P}\)), dan misalkan \(X''_0\) menyatakan himpunan elemen dalam \(X''\) yang tidak memenuhi satu pun sifat dalam \(\mathcal{Q}\text{,}\) dan karena itu juga tidak memenuhi satu pun sifat dalam \(\mathcal{P}\text{.}\)
Berdasarkan hipotesis induksi, kita memperoleh
\begin{equation*}
|X'_0| = \sum_{S\subseteq [k]} (-1)^{|S|}N'(S)\qquad \text{dan} \qquad
|X''_0| = \sum_{S\subseteq [k]} (-1)^{|S|}N''(S).
\end{equation*}
Dengan demikian,
\begin{align*}
|X''_0| \amp = \sum_{S\subseteq [k]} (-1)^{|S|}N''(S) = \sum_{S\subseteq [k]}
(-1)^{|S|}\left(N(S)-N'(S)\right)\\
\amp = \sum_{S\subseteq [k]} (-1)^{|S|}N(S)+
\sum_{S\subseteq [k]} (-1)^{|S|+1}N(S\cup\{k+1\})\\
\amp = \sum_{S\subseteq [k+1]} (-1)^{|S|}N(S).
\end{align*}
