包除原理

$A\cup B$ のすべての要素は、$A$ のみに属する、$B$ のみに属する、両方に属する、という三つの互いに素なグループのちょうど一つに入る。$|A|+|B|$ を足すと「両方」のグループが二回数えられるので、一回分を取り除く必要がある。

$A\cup B$ を互いに素な三つの部分に分割する:$A\setminus B$($A$ のみ)、$B\setminus A$($B$ のみ)、$A\cap B$(両方)。これらは互いに素で $A\cup B$ を覆うので、$|A\cup B|=|A\setminus B|+|B\setminus A|+|A\cap B|$ となる。

次に、$A$ 自体が互いに素な $A\setminus B$ と $A\cap B$ に分かれることに注目すると、$|A|=|A\setminus B|+|A\cap B|$ となり、$|A\setminus B|=|A|-|A\cap B|$ を得る。同様に $|B\setminus A|=|B|-|A\cap B|$ である。

この二つの式を最初の等式に代入すると、$|A\cup B|=(|A|-|A\cap B|)+(|B|-|A\cap B|)+|A\cap B|=|A|+|B|-|A\cap B|$ となり、これはまさに $|A\cup B|=|A|+|B|-|A\cap B|$ である。

複数の集合に属する各要素は、単独の集合ごとに一回加算され、各ペアごとに一回減算され、各三つ組ごとにまた加算される、というように続く。この交代パターンこそが、その要素の合計カウントをちょうど $1$ に戻すために必要なものである。

任意の要素 $x$ を固定する。$x$ が $A_1,\ldots,A_n$ のどれにも属さなければ、両辺への寄与は $0$ なので、$x$ がちょうど $m\ge 1$ 個の集合に属すると仮定する。

各 $k$ について、$x$ を含む $k$ 重共通部分 $A_{i_1}\cap\cdots\cap A_{i_k}$ の個数は、$x$ を含む $m$ 個の集合から $k$ 個を選ぶ方法の数、すなわち $\binom{m}{k}$ に等しい。したがって $x$ の右辺への総寄与は $\sum_{k=1}^n(-1)^{k+1}\binom{m}{k}=\sum_{k=1}^m(-1)^{k+1}\binom{m}{k}$ である($k>m$ の項は $\binom{m}{k}=0$ のため消える)。

二項定理により $\sum_{k=0}^m(-1)^k\binom{m}{k}=(1-1)^m=0$ なので $\sum_{k=1}^m(-1)^k\binom{m}{k}=-1$ となり、$-1$ を掛けるとちょうど $\sum_{k=1}^m(-1)^{k+1}\binom{m}{k}=1$ が得られる。

したがって少なくとも一つの集合に属する各要素は右辺にちょうど $1$ を寄与し、これは $\left|\bigcup_{i=1}^n A_i\right|$ への $1$ の寄与と一致する。どの集合にも属さない要素は両辺に $0$ を寄与する。すべての要素が両辺に等しく寄与するので、両辺は等しい。