#容斥原理的组合证明

#背景

我们如何计算两个集合的并集的基数？设 $A_1$ 和 $A_2$ 为两个同一个有限集 $A$ 的子集。如果两者是相离的，那么直接有 $|A_1 \cup A_2|=|A_1|+|A_2|$ 。如果两者相交，仍采用上方的公式计算，两个集合的共有元素就会被计算两次，需要减去 $|A_1 \cap A_2|$ 来保证共有元素只被计算了一次：

$$|A_1 \cup A_2|=|A_1|+|A_2|-|A_1 \cap A_2|$$

#容斥原理

将背景中的想法推广到任意数量的子集上，就得到了容斥原理：

$$|A_1 \cup \cdots \cup A_n| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{S \subseteq \{1, \dots n\}:|S|=k} |\cap_{i\in S}A_i|$$

注：公式中内层求和是对于 $\{1, \dots n\}$ 的所有大小为 $k$ 的子集进行的，因此公式可以转写为：

$$\begin{aligned} |A_1 \cup \cdots \cup A_n| = \sum_{i=1}^{n}|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| \\ - \sum_{i<j<k<l}|A_i \cap A_j \cap A_k \cap A_l| + \dots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n| \end{aligned}$$

其中 $\sum_{i<j}$ 表示对于所有的 $i,j \in {1, \dots, n}$ 且 $i<j$ 的情况求和，以此类推。

#证明思路

欲证明容斥原理，应该验证对 $\forall a \in A_1 \cup \cdots \cup A_n$ 在公式右侧只被计数了 $1$ 次。

#证明

#取点小$a$

从 $A_1 \cup \cdots \cup A_n$ 中任意取 一个 固定的/特定的点小a

#定义小$a$所在的下标集$M$

$$\begin{gathered} M \subseteq \{1, \dots ,n\} \\ M = \{i\in\{1,\dots ,n\} | a \in A_i\} \end{gathered}$$

$M$ 即为 $a$ 所属的 $A_i$ ($A$的子集们) 的下标合集。

也就是：

$$a \in A_i \Leftrightarrow i \in M$$

而且由于 $a \in A_1 \cup \cdots \cup A_n$ ，必然 $\exists A_i \ni a$ ，所以 $M$ 的基数 $|M|\ge 1$。

#$S$的定义回顾

$${S \subseteq \{1, \dots n\}:|S|=k}$$

$S$ 是公式中的下标集。

#$S$与$M$的关系的分类讨论

• 若 $S \subseteq M$, 则 $a \in \cap_{i\in S}A_i$ ，此时 $|\cap_{i\in S}A_i| = 1$

  也就是说：若 给定的下标集$S$ 是 $a$所在的下标集$M$ 的子集，则 $a$ 存在于 给定的下标集$S$ 所指定的子集们的交集$\cap_{i\in S}A_i$ 中。因为我们只取了 $1$ 个点，所以此时基数 $|\cap_{i\in S}A_i| = 1$ ，因为 $a$ 在这个大交集中。

• 与此相对的是，

  若 $S \nsubseteq M$, 则 $a \notin \cap_{i\in S}A_i$ ，此时 $|\cap_{i\in S}A_i| = 0$

  也就是说：若 给定的下标集$S$ 不是 $a$所在的下标集$M$ 的子集，则 $a$ 不存在于 给定的下标集$S$ 所指定的子集们的交集$\cap_{i\in S}A_i$ 中。因为我们只取了 $1$ 个点，所以此时基数 $|\cap_{i\in S}A_i| = 0$ ，因为 $a$ 不在这个大交集中。

#公式右侧对$a$的计数

回忆加减法计算：

$$\begin{gathered} 0+num=num \\ num-0=num \\ 1+num=num+1 \\ num-1=num-1 \end{gathered}$$

通过$S$与$M$的关系的分类讨论，我们知道，每当 $S \subseteq M$ 都有 $|\cap_{i\in S}A_i| = 1$，每当 $S \nsubseteq M$ 都有 $|\cap_{i\in S}A_i| = 0$。

因此在一个点的情况下，公式右侧可以被表示为 ($|\cap_{i\in S}A_i| = 0$ 的情况不用累加)：

$$\sum_{k=1}^m(-1)^{k-1} \sum_{S \subseteq M : |S|=k } 1$$

由于集合 $M$ 的 $k$ 个元素的子集数量等于从 $m$ 个元素中选出 $k$ 个的组合数量 $\binom{m}{k}$，上式可以被表示为：

$$\sum_{k=1}^m(-1)^{k-1} \binom{m}{k}$$

又根据二项式定理的推论 (二项式定理 $a=-1$ $b=1$ 时的特殊情况) ，上式可以被表示为：

$$\sum_{k=1}^m(-1)^{k-1} \binom{m}{k} = 1$$

回顾证明思路会发现我们已经

证明完毕。

#附

#二项式定理 Binomial Theorem

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}$$

注：二项式定理也可以使用组合证明，思路是对单项式的系数计数

#推论 Corollary

$$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$$

#容斥原理的两种常用证明方法

• 数学归纳法

• 指示函数法

  • 定义集合A的指示函数：

    $$1_{A}(x)= \begin{cases} 1,\ x \in A \\ 0,\ x \notin A \end{cases}$$

  • 和组合证明是等价的，是组合证明的严格化

#参考

• CS 70 Fall 2025 - Note 10
• DeepSeek - 探索未至之境