02 容斥原理

容斥原理

集合的并集

让我们从一个简单的计数问题作为例子出发。在$1$到$100$的整数中，我们想数出“是$2$或$3$或$5$的数的倍数”的数的个数，怎么数比较方便呢？我们很容易数出$2$的倍数的个数、$3$的倍数的个数、$5$的倍数的个数，它们分别是$100/2=50$，$\left\lfloor 100/3\right\rfloor=33$，$100/5=20$。但是，不能把它们简单地加起来，因为有的数又是$2$的倍数又是$3$的倍数，有的数又是$3$的倍数又是$5$的倍数，有的数同时是$2,3,5$的倍数。所以，我们要把重复的给减掉。同时是$2$和$3$的倍数的数的个数为$\left\lfloor 100/(2\times 3)\right\rfloor=16$，同时是$2$和$5$的倍数的的数的个数为$\left\lfloor 100/(2\times 5)\right\rfloor=10$，同时是$3$和$5$的倍数的的数的个数为$\left\lfloor 100/(3\times 5)\right\rfloor=6$。但是，又不能全都减掉，因为因为同时是$2,3,5$的倍数的数之前被多加了两次，现在又被减了三次。所以我们最后还需要加上一次$\left\lfloor 100/(2\times3\times 5)\right\rfloor=3$。综上所述，在$1$到$100$的整数中“是$2$或$3$或$5$的数的倍数”的数的个数为：$50+33+20-16-10-6+3=74$。

上述计数过程的关键在于弄清同时满足多个性质的元素集合之间的交集关系。一个更清晰的办法是用韦恩图表示：设$1$到$100$之间$2$的倍数的集合为$A$，$3$的倍数的集合为$B$，$5$的倍数的集合为$C$，求集合$|A\cup B\cup C|$的大小。在这个问题里，很关键的一点是：我们很容易计算$|A|,|B|,|C|$，$|A\cap B|$，$|A\cap C|$，$|B \cap C|$，$|A\cap B\cap C|$这些集合的大小，所以我们希望建立这些集合与$A\cup B\cup C$之间的计数关系。从例子中，我们找到了这样一个恒成立的关系：

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

上面这个关系可以推广到任意$n$个集合上：对于有限大小的集合$A_1,\cdots,A_n$，设$\mathscr{A}=\{A_1,\cdots,A_n\}$，那么：

$$\left|\bigcup\limits_{i\in [n]}A_i\right|=\sum\limits_{J\subseteq \mathscr{A}}(-1)^{|J|+1}\left|\bigcap\limits_{A_i\in J} A_i\right|$$

这称为容斥原理(inclusion-exclusion principle)。

“坏性质”

在组合数学中，通常会用到另一种方法来叙述容斥原理。这种方法和上面的“求集合的并集”的形式相比，在本质上是完全相同的。我们下面用新的方法重新叙述容斥原理，并给出证明。

我们可以这样看待容斥原理：在全集$U$中，有一系列性质是“坏性质”，我们要求出“好元素”——不满足任何坏性质的元素——的个数。注意，一个“性质”就是一个$U$的子集，这是一种自然语言习惯。通常而言，如果同时满足多个坏性质的元素个数是容易计算的，那么我们就可以用容斥原理求好元素。比如，在上一段的例子中，我们就把“$2$的倍数”、“$3$的倍数”、“$5$的倍数”分别看作三个坏性质，那么只要求出好元素的个数（既不是$2$的倍数也不是$3$的倍数也不是$5$的倍数），再取补集就得到了答案（$2$或$3$或$5$的倍数）。用记号表示：在给定的一个大集合$U$中，设坏集合为$A_1,\cdots,A_n$。已知$|\bigcap\limits_{i=1}^{k}A_{p_i}|$是容易计算的，目标就是计算出$|\bigcup\limits_{i=1}^{n} A_i|$。令$\mathscr{A}=\{A_1,\cdots,A_m\}$。对任意$J\subseteq A$，定义：

$$N_=(J):=\left|\{x \in U \mid \forall A_i \in J, x \in A_i 且 \forall A_i \in \mathscr{A} \setminus J, x \notin A_i\}\right|$$

$N_=(J)$表示所有满足$J$中的所有坏性质，而不满足任何其它坏性质的元素个数。比如在刚才的例子中，把三个坏性质“$2$的倍数”、“$3$的倍数”、“$5$的倍数”分别记为$A_1,A_2,A_3$，那么$N_=(\{A_1,A_3\})$就表示“既是$2$的倍数又是$5$的倍数，但不是$3$的倍数”的数的个数（也就是$|(A_1\cap A_3)\setminus A_2|$）。注意到，$N_=(\varnothing)$就表示不满足任何坏性质的元素个数，也就是“好元素”个数。对任意$J\subseteq A$，定义：

$$N_\geq (J)=|\{x \in U \mid \forall A_i \in J, x \in A_i\}|$$

$N_=(J)$表示所有满足$J$中的所有坏性质的元素个数，它其实就相当于$\bigcap\limits_{A_i\in J}A_i$的大小，只不过$J=\varnothing$时$N_\geq (\varnothing)$表示全集而不是空集。在可以使用容斥原理的问题中，$N_\geq(\varnothing)$通常是容易求出的。

“$N_=$和$N_\geq$的定义”也完全可以用“坏性质集合间的交集、并集”来描述，但是要注意边界条件：“满足0个坏性质”对应的是全集，而不是空集。

在这样的记号下，容斥原理的表述为：

$$N_=(\varnothing) = \sum\limits_{J\subseteq \mathscr{A}} (-1)^{|J|}N_\ge(J)$$

计算时可以写为：（其中$\dbinom{\mathscr{A}}{j}$表示全体大小为$j$的$\mathscr{A}$的子集）

$$N_=(\varnothing) = \sum\limits_{j=0}^m (-1)^j \sum\limits_{J\in\binom{\mathscr{A}}{j}} N_\ge(J)$$

证明：我们考虑每个元素的“贡献”（“贡献”是计数中的一种证明方法，上面的等式的左右两边都是在数数，要证明等式相等，只需证明任意$x\in U$被等式左边数到的次数和被等式右边数到的次数是相等的）。如果$x \in N_=(\varnothing)$，将在左侧贡献1。这意味着$x$不属于任何坏集合，因此它在右侧只会在$j=0$时（即$J=\varnothing$）时被统计到，刚好在$N_\geq(\varnothing)$中贡献1次；如果$x \notin N_=(\varnothing)$，那么左侧贡献$0$，此时$x$可能出现在了某几个坏集合中，不妨设出现在$A_{i_1},\cdots,A_{i_t}$中，那么当且仅当$J \subseteq \{A_{i_1},\cdots,A_{i_t}\}$时（包括空集）右侧才会贡献，总的贡献恰好为$\sum\limits_{j=0}^{t}(-1)^j \dbinom{t}{j}$，由二项式定理，这恰好等于$\sum\limits_{j=0}^{t}\dbinom{t}{j}(-1)^j (1)^{t-j}=(-1+1)^t=0$。证毕。

我们可以证明更一般的容斥原理。对于任意$S\subseteq \mathscr{A}$：

$$N_=(S)=\sum\limits_{J:S \subseteq J \subseteq \mathscr{A}}(-1)^{|J|-|S|}N_\geq(J)$$

证明：考虑每个元素的贡献。$\forall x \in N_=(S)$，左边贡献1；等式右边当且仅当$x \in N _\geq (J)$才产生贡献，这要求$J \subseteq S$。而$S \subseteq J$，因此必须有$S=J$。因此等式右边也恰好贡献1。如果$x \notin N_=(S)$，则左边贡献0；等式右边，如果本身就有$S=\mathscr{A}$，则右侧等式直接可以写作$N _\geq(\mathscr{A})=N_=(\mathscr{A})$，等式成立。如果$S \subsetneq \mathscr{A}$，此时分类讨论：①$\exists A_k\in S,x\not\in A_k$，那么因为$S\subseteq J$，所以对于所有等式中的$J$，$N_\geq(J)$的贡献都为$0$，成立。②$\forall A_k\in S,x\in A_k$同时$\exists A_k\in J\setminus S,x\notin A_k$。此时，记$T_x=\{A_i\in \mathscr{A}\mid x\in A_i\}$，那么当且仅当$J\subseteq T_x$，$N_\geq (J)$才产生贡献。所以，等式右侧的贡献为$\sum\limits_{S \subseteq J \subseteq T_x}(-1)^{|J|-|S|}N_\geq(J)=\sum\limits_{j=|S|}^{|T_x|}(-1)^{j-|S|} \sum\limits_{S \subseteq J \in \binom{T_x}{j}} N_\geq(J)$ $=\sum\limits_{j=0}^{|T_x|-|S|}(-1)^j \dbinom{|T_x|-|S|}{j}=(-1+1)^{|T_x|-|S|}=0$。证毕。

容斥原理的应用

错位排列

一个排列$\{a_i\}_{i=1}^{n}$是错位排列当且仅当$\forall i\in [n],a_i \neq i$。求长度为$n$的错位排列的个数$f_n$。

设全集为$U$，共包含$n!$个排列。对任意$i\in [n]$，把所有满足$a_i=i$的排列集合看作坏性质$A_i$。那么，容易发现$N_\geq(\{A_{i_1},\cdots,A_{i_t}\})=(n-t)!$

代入容斥原理的公式，$N_=(\varnothing)=\sum\limits_{j=0}^n (-1)^j \sum\limits_{J\in\binom{\mathscr{A}}{j}} (n-j)!=\sum\limits_{j=0}^n (-1)^j \dbinom{n}{j} (n-j)!$。所以

$$f_n=\sum\limits_{j=0}^n (-1)^j \dbinom{n}{j} (n-j)!$$

这就是错位排列的通项公式。

第二类斯特林数通项

“$k$个球放进$n$个箱子，球不同，箱子相同，箱子不能为空”的答案是第二类斯特林数$\left\{\begin{array}{l} k \\ n \end{array}\right\}$。我们还证明过，“$k$个球放进$n$个箱子，球不同，箱子不同，箱子不能为空”的答案是$\left\{\begin{array}{l} k \\ n \end{array}\right\}n!$，因为只需在箱子相同的答案的基础上对箱子做轮换即可。现在我们利用容斥原理来计算后面这个小球装箱问题，由此给出第二类斯特林数的通项公式。

“$k$个球放进$n$个箱子，球不同，箱子不同，箱子不能为空”可以看作：求“从$[k]$到$[n]$的满射”的个数。从$[k]$到$[n]$的映射共有$n^k$个，把这看作全集$U$。对于任意$i\in [n]$，把“$i$没有被映射到的映射”看作坏性质集合$A_i$，那么有$N_\geq(\{A_{i_1},\cdots,A_{i_t}\})$ $=(n-t)^k$。于是有$N_=(\varnothing)=\sum\limits_{j=0}^n (-1)^j \sum\limits_{J\in\binom{\mathscr{A}}{j}} (n-j)^k=\sum\limits_{j=0}^n (-1)^j \dbinom{n}{j} (n-j)^k$。

综上，我们得到：

$$\left\{\begin{array}{l} k \\ n \end{array}\right\}=\dfrac{1}{n!}\sum\limits_{j=0}^n (-1)^j \dbinom{n}{j} (n-j)^k$$

二分图完美匹配

给定$2n$个顶点的二分图，二分图的两侧各$n$个节点。设$A_{i_1,i_2}$表示左侧的第$i_1$个点与右侧的第$i_2$个点直接是否有边相连（有则为$1$，无则为$0$）。一个“完美匹配(perfect match)”是$n$条边，分别连接左右的全部点。给定邻接矩阵，我们可以枚举$n$上的全排列$\sigma$，计算该二分图上的完美匹配方案数：$\sum\limits_{\sigma}\prod\limits_{i=1}^{n}A_{i,\sigma(i)}$。这样做的计算复杂度为$O(n! \cdot n)$

我们可以利用容斥原理计算完美匹配方案数。把$n!$种全排列看作全集$U$。把“右侧的节点$i$没有被匹配上的匹配”看作坏性质集合$A_i$，那么$N_\geq(J)=\prod\limits_{i=1}^{n}\left(\sum\limits_{j \in [n] \backslash J}A_{i,j}\right)$。于是有$N_=(\varnothing)=\sum\limits_{J\in\mathscr{A}}(-1)^{|J|} \prod\limits_{i=1}^{n}\left(\sum\limits_{j \in [n] \backslash J}A_{i,j}\right)$。用这个式子计算，不再需要枚举全排列，只需要枚举大小为$n$的集合的子集。如果对后面部分做好预处理，复杂度可以达到$O(2^n \cdot n)$。可以证明，在渐进意义下这是最优复杂度了。

参考资料

[1] Chihao Zhang, Combinatorics in Computer Science (Spring 2023)