包除原理の２通りの証明

包除原理の右辺で「集合ちょうど $m$ 個の共通部分」が何回現れているかを数え，それがどんな $m$ に対しても1に等しいことを示す。

まず，右辺第一項で $m$ 回足され，第二項で $_{m}\mathrm{C}_2$ 回引かれ，第三項で $_{m}\mathrm{C}_3$ 回足され，$\cdots$ なので，

数えたい回数は，$\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}\mathrm{C}_k$ である。

一方，二項定理より，

$$\begin{aligned} 0 &= (1-1)^m\\ &=\sum_{k=0}^m {}_m\mathrm{C}_k(-1)^k\\ &=1-\sum_{k=1}^m{}_m\mathrm{C}_k(-1)^{k-1} \end{aligned}$$

よって，$\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}\mathrm{C}_k=1$ となり包除原理が示された。

$n=2$ の場合は簡単なので省略，帰納法で示す。

$$\begin{aligned} &|A_1\cup A_2\cup\cdots\cup A_n|\\ &=|(A_1\cup A_2\cup\cdots\cup A_{n-1})\cup A_n|\\ &=|A_1\cup A_2\cup\cdots\cup A_{n-1}|+|A_n|\\ &\quad -|(A_1\cup A_2\cup\cdots\cup A_{n-1}) \cap A_n| \end{aligned}$$

第一項と第三項を帰納法の仮定を用いて計算：

• 第一項 $$\sum_{k=1}^{n-1}\left((-1)^{k-1}\sum_{i_1 \cdots i_k}|A_{i_1}\cap\cdots\cap A_{i_k}|\right)$$

• 第二項 $$(-1)^{1-1}|A_n|$$

• 第三項 $$\begin{aligned} &-|(A_1\cap A_n)\cup(A_2\cap A_n)\cup\cdots\cup(A_{n-1}\cap A_n)|\\ &=- \sum_{k=1}^{n-1}\left((-1)^{k-1}\sum_{i_1 \cdots i_k}|(A_{i_1}\cap A_n)\cap \cdots\cap (A_{i_k}\cap A_n)|\right)\\ &=\sum_{k=1}^{n-1}\left((-1)^{k}\sum_{i_1 \cdots i_k}|(A_{i_1}\cap\cdots\cap A_{i_k})\cap A_n|\right) \end{aligned}$$

3つの項を加える事により，包除原理が証明される：

$$\begin{aligned} &|A_1\cup A_2\cup\cdots\cup A_n|\\ &=\sum_{k=1}^{n}\left((-1)^{k-1}\sum_{i_1 \cdots i_k}|A_{i_1}\cap\cdots\cap A_{i_k}|\right) \end{aligned}$$

一般の場合も同様なので，集合が3つの場合について証明する。全体集合を

$U=A\cup B\cup C$ として，それぞれの補集合に「普通の包除原理」を適用する：

$$\begin{aligned} &|\overline{A}\cup \overline{B}\cup \overline{C}|\\ &=|\overline{A}|+|\overline{B}|+|\overline{C}|\\ &\quad -|\overline{A}\cap \overline{B}|-|\overline{B}\cap \overline{C}|-|\overline{C}\cap \overline{A}|\\ &\quad +|\overline{A}\cap \overline{B}\cap \overline{C}| \end{aligned}$$

ド・モルガンの法則を使うと「または」と「かつ」がひっくり返る：

$$\begin{aligned} &|\overline{A\cap B\cap C}|\\ &=|\overline{A}|+|\overline{B}|+|\overline{C}|\\ &\quad -|\overline{A\cup B}|-|\overline{B\cup C}|-|\overline{C\cup A}|\\ &\quad +|\overline{A\cup B\cup C}| \end{aligned}$$

最後にそれぞれの項について，補集合の要素数公式 $|\overline{S}|=|U|-|S|$ を使うと，求める公式になる。