容斥原理

$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$。由于每个元素对两边的贡献相同,两边相等。