本节对应原书 PDF 第 221–225 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

容斥原理是组合计数里的一条基本定理，它处理的是这样一类问题：在一个有穷集合中，有多少个元素不具备所列出的那些性质。多重集的 r-组合计数、错位排列计数等都归它管。本章只讲容斥原理的基本形式和应用，不涉及它的推广形式。

9.1.1 容斥原理的基本形式

先从一个小例子看它是怎么起作用的。

例 9.1 设集合 S=\{1,2,3\}，求 S 上既不是对称、也不是反对称的关系个数.

解 先计算 S 中的关系总数，等于 2^{3^2}=2^9=512.然后计算 S 中对称关系的个数，根据第 4 章的结果，这个数应该等于 2^{\frac{3^2+3}{2}}=2^6=64.接着，计算反对称关系的个数，是 2^3 \cdot 3^{\frac{3^2-3}{2}}=2^3 \cdot 3^3=216.最后还需要知道既对称、也反对称的关系的个数，是 2^3=8 个.为了得到所求的结果，应该从关系总数中减去对称关系的个数、反对称关系的个数.但是这样一来，同时具有对称性和反对称性的关系就被减去了 2 次，因此需要在上述结果中再加上这种关系的个数，最终得到如下结果：

512-(64+216)+8=240

上述求解方法就是使用容斥原理的一个简单的例子.

下面给出容斥原理.

定理 9.1 设 S 为有穷集，P_1,P_2,\cdots,P_m 是 m 种性质，A_i 是 S 中具有性质 P_i 的元素构成的子集，\bar{A}_i 是 A_i 相对于 S 的补集，其中 i=1,2,\cdots,m.那么 S 中不具有性质 P_1,P_2,\cdots,P_m 的元素数为

\begin{aligned} |\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A}_m| &= |S|-\sum_{i=1}^{m}|A_i|+\sum_{1 \leqslant i<j \leqslant m}|A_i \cap A_j|\\ &-\sum_{1 \leqslant i<j<k \leqslant m}|A_i \cap A_j \cap A_k|+\cdots+(-1)^m|A_1 \cap A_2 \cap \cdots \cap A_m| \end{aligned}

证明 可以使用数学归纳法对 m 进行归纳，也可以使用组合分析的方法，这里给出的是组合分析的方法.只需要证明：如果 S 中的元素 x 具有 m 种性质中的任何一种，那么它对等式右边的计数贡献是 0；如果不具有任何性质，则对等式右边的计数贡献是 1.下面分别讨论这两种情况.

若 x 不具有任何性质，则 x 在 S 中出现 1 次，但是 x 不会出现在任何 A_i 中，其中 i=1,2,\cdots,m.因此 x 对等式右边的贡献为

1-0+0-0+\cdots+(-1)^m \cdot 0=1

若 x 具有 n 条性质，1 \leqslant n \leqslant m，则 x 在 S 中出现 1 次，在 \sum_{i=1}^{m}|A_i| 中出现 \binom{n}{1} 次，在 \sum_{1 \leqslant i<j \leqslant m}|A_i \cap A_j| 中出现 \binom{n}{2} 次，\cdots\cdots，在 (-1)^m|A_1 \cap A_2 \cap \cdots \cap A_m| 中出现 \binom{n}{m} 次，因此对等式右边的贡献为

1-\binom{n}{1}+\binom{n}{2}-\cdots+(-1)^m\binom{n}{m}=\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0

解读：证明的关键不是去数 x 在左边出现几次，而是看右边这一长串加减里 x 一共被算了多少遍——不具备性质时算 1 遍，具备性质时正负恰好抵消成 0。这也解释了为什么各项的符号必须正负交替。

推论 S 中至少具有其中一条性质的元素数为

\begin{aligned} |A_1 \cup A_2 \cup \cdots \cup A_m| &= \sum_{i=1}^{m}|A_i|-\sum_{1 \leqslant i<j \leqslant m}|A_i \cap A_j|\\ &+\sum_{1 \leqslant i<j<k \leqslant m}|A_i \cap A_j \cap A_k|+\cdots+(-1)^{m-1}|A_1 \cap A_2 \cap \cdots \cap A_m| \end{aligned}

证明 根据集合论的知识可以知道，

\begin{aligned} |A_1 \cup A_2 \cup \cdots \cup A_m| &= |S|-|\overline{A_1 \cup A_2 \cup \cdots \cup A_m}|\\ &= |S|-|\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A}_m|\\ &= |S|-\left(|S|-\sum_{i=1}^{m}|A_i|+\sum_{1 \leqslant i<j \leqslant m}|A_i \cap A_j|\right.\\ &\quad -\sum_{1 \leqslant i<j<k \leqslant m}|A_i \cap A_j \cap A_k|\\ &\quad \left.+\cdots+(-1)^m|A_1 \cap A_2 \cap \cdots \cap A_m|\right)\\ &= \sum_{i=1}^{m}|A_i|-\sum_{1 \leqslant i<j \leqslant m}|A_i \cap A_j|+\sum_{1 \leqslant i<j<k \leqslant m}|A_i \cap A_j \cap A_k|\\ &\quad +\cdots+(-1)^{m-1}|A_1 \cap A_2 \cap \cdots \cap A_m| \end{aligned}

解读：推论与定理 9.1 是同一件事的两种说法——「不满足任何性质」的补集就是「至少满足一条性质」。注意推论最后一项的符号是 (-1)^{m-1}，比定理 9.1 少一次变号。

9.1.2 容斥原理的应用

使用容斥原理可以求多重集的 r-组合数.下面用一个例子说明求解方法.

例 9.2 求多重集 B=\{3 \cdot a,4 \cdot b,5 \cdot c\} 的 10-组合数.

解 令 S=\{x|x 是 a,b,c 任意重复的 10-组合\}，如下定义 S 的 3 个子集：

A_1=\{x|x \in S,x 中至少含 4 个 a\}=\{x|x 是 a,b,c 的任意 6 组合\}

A_2=\{x|x \in S,x 中至少含 5 个 b\}=\{x|x 是 a,b,c 的任意 5 组合\}

A_3=\{x|x \in S,x 中至少含 6 个 c\}=\{x|x 是 a,b,c 的任意 4 组合\}

所求的 10-组合数应该等于 |\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3|，下面对这个数进行计算.

S 的 10-组合总数应该是

|S|=\binom{3+10-1}{10}=\binom{12}{2}=66

如果一个 10-组合中至少含有 4 个 a，那么从这个 10-组合中拿走 4 个 a，就得到 S 的一个 6-组合；反之，如果在 S 的一个 6-组合中加上 4 个 a，就得到一个至少含有 4 个 a 的 10-组合.根据这种一一对应，S 的至少含有 4 个 a 的 10-组合数就等于它的 6-组合数，从而得到

|A_1|=\binom{3+6-1}{6}=\binom{8}{2}=28

类似地，也可以得到

|A_2|=\binom{3+5-1}{5}=\binom{7}{2}=21
|A_3|=\binom{3+4-1}{4}=\binom{6}{2}=15
|A_1 \cap A_2|=\binom{3+1-1}{1}=3
|A_1 \cap A_3|=\binom{3+0-1}{0}=1
|A_2 \cap A_3|=0
|A_1 \cap A_2 \cap A_3|=0

代入容斥原理得到

|\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3|=66-(28+21+15)+(3+1+0)-0=6

对于这样简单的问题也可以使用文氏图求解.如图 9.1 所示，从 3 个子集的交集开始，分别在代表它们的面积中填上适当的数字.当中心位置的子集填上 0 以后，接着填上两个集合交集位置的数字，如图中的 3,0 和 1；最后填上只在一个子集中的元素数，即 24,18,14.将已经填好的数字加起来就得到 A_1 \cup A_2 \cup A_3 的元素数，就是 60，从而得到不在 3 个子集中的元素数为 6.

原书图9.1

文氏图的方法只适用于 S 的性质比较少或者同时具有两种性质的元素比较少的情况.因为当性质比较多时，涉及的子集以及它们之间的交集也比较多，就很难用文氏图来表示它们之间的关系了.在这种情况下容斥原理就成为一个有用的工具.

使用容斥原理应该注意什么问题呢？首先注意容斥原理适于求解的问题类型是：对有穷集中不具有任何性质的元素进行计数.求解过程是：先设定有穷集合 S，然后定义 S 中的若干条性质.这些性质应该与题目所要求元素具有的性质恰好相反，同时这些性质应该是彼此独立的.换句话说，在计数具有某种性质的元素时，与这些元素是否具有其他性质无关.

解读：例 9.2 里定义性质时，题目的多重集给的是 3 \cdot a,4 \cdot b,5 \cdot c，所以「超限」的门槛分别是 4 个 a、5 个 b、6 个 c——比允许的个数多 1 才算违反。拿走超出的部分后剩下的就是普通组合，这一步的一一对应是全部计算能化简的原因。

下面通过例子进一步说明这种求解方法.

例 9.3 求不超过 120 的素数个数.

解 因为 11^2=121，不超过 120 的合数至少含有 2,3,5 或者 7 这几个素因子之一.先求在 1～120 之间不能被 2,3,5 或 7 整除的整数个数.由于 2,3,5,7 本身是素数，而 1 不是素数，因此上述整数个数需要加 4，再减去 1.设

S=\{x|x \in \mathbf{Z},1 \leqslant x \leqslant 120\}
A_1=\{x|x \in S,x\text{ 是 }2\text{ 的倍数}\}
A_2=\{x|x \in S,x\text{ 是 }3\text{ 的倍数}\}
A_3=\{x|x \in S,x\text{ 是 }5\text{ 的倍数}\}
A_4=\{x|x \in S,x\text{ 是 }7\text{ 的倍数}\}

那么

|S|=120,\ |A_1|=60,\ |A_2|=40,\ |A_3|=24,\ |A_4|=17
|A_1 \cap A_2|=20,\ |A_1 \cap A_3|=12,\ |A_1 \cap A_4|=8,\ |A_2 \cap A_3|=8,\ |A_2 \cap A_4|=5,
|A_3 \cap A_4|=3
|A_1 \cap A_2 \cap A_3|=4,\ |A_1 \cap A_2 \cap A_4|=2,\ |A_1 \cap A_3 \cap A_4|=1,\ |A_2 \cap A_3 \cap A_4|=1
|A_1 \cap A_2 \cap A_3 \cap A_4|=0

根据容斥原理

\begin{aligned} |\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3 \cap \bar{A}_4| &= 120-(60+40+24+17)\\ &\quad +(20+12+8+8+5+3)-(4+2+1+1)+0\\ &= 120-141+56-8=27 \end{aligned}

因此，不超过 120 的素数个数是 27+3=30.

解读：算出的 27 是「不被 2,3,5,7 整除」的数，其中混进了 2,3,5,7 这 4 个素数本身，所以要加回 4；又要扣掉同样混进来的 1（它不被任何素数整除但不是素数），故减 1。这一步的 ±修正与原书的容斥公式是分开的两件事。

例 9.4 求欧拉函数的值.

欧拉函数 \phi 是数论中的一个重要函数，设 n 是正整数，\phi(n) 表示 \{0,1,\cdots,n-1\} 中与 n 互素的数的个数.例如 \phi(12)=4，因为与 12 互素的数有 1,5,7,11.这里认为 \phi(1)=1.关于欧拉函数将在第 11 章进一步讨论，这里只是利用容斥原理给出欧拉函数的计算公式.

给定正整数 n，n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} 为 n 的素因子分解式，令

A_i=\{x|0 \leqslant x \leqslant n-1\text{ 且 }p_i\text{ 整除 }x\}

那么

\phi(n)=|\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A}_k|

下面计算等式右边的各项.

|A_i|=\frac{n}{p_i}\qquad i=1,2,\cdots,k
|A_i \cap A_j|=\frac{n}{p_ip_j}\qquad 1 \leqslant i<j \leqslant n
\vdots
|A_1 \cap A_2 \cap \cdots \cap A_k|=\frac{n}{p_1p_2\cdots p_k}

根据容斥原理

\begin{aligned} \phi(n) &= |\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A}_k|\\ &= n-\left(\frac{n}{p_1}+\frac{n}{p_2}+\cdots+\frac{n}{p_k}\right)+\left(\frac{n}{p_1p_2}+\frac{n}{p_1p_3}+\cdots+\frac{n}{p_{k-1}p_k}\right)-\cdots+(-1)^k\frac{n}{p_1p_2\cdots p_k}\\ &= n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right) \end{aligned}

例如，\phi(60)=60\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5}=16，与 60 互素的正整数有 16 个，它们是 1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59.

解读：A_i 是「被 p_i 整除」的数集，\phi(n) 要的是「不被任何素因子整除」的数，正好是 A_i 全体的补交集，于是容斥的每一项都只是 n 除以若干素因子的乘积——这解释了末行那个漂亮连乘积的来源。

使用容斥原理可以证明组合恒等式.

例 9.5 证明：

\binom{n-m}{r-m}=\sum_{i=0}^{m}(-1)^i\binom{m}{i}\binom{n-i}{r}\qquad m \leqslant r \leqslant n

证明 令 S=\{1,2,\cdots,n\}，A=\{1,2,\cdots,m\}，等式左边是从 S 中选取包含 A 的 r-子集的方法数.下面证明等式右边也是对这种子集的计数.如下定义 m 种性质：

P_i：在 S 的 r 子集中不包含 i，i=1,2,\cdots,m

令 S 的 r-子集中满足性质 P_i 的子集构成集合 A_i，i=1,2,\cdots,m.那么 |\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A}_m| 代表了含有 1,2,\cdots,m 的子集个数.不难看出，

|A_i|=\binom{n-1}{r}\qquad 1 \leqslant i \leqslant m
|A_i \cap A_j|=\binom{n-2}{r}\qquad 1 \leqslant i<j \leqslant m
\vdots
|A_1 \cap A_2 \cap \cdots \cap A_m|=\binom{n-m}{r}

根据容斥原理得

\begin{aligned} &|\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A}_m|\\ =&\binom{n}{r}-\binom{m}{1}\binom{n-1}{r}+\binom{m}{2}\binom{n-2}{r}-\cdots+(-1)^m\binom{m}{m}\binom{n-m}{r}\\ =&\sum_{i=0}^{m}(-1)^i\binom{m}{i}\binom{n-i}{r} \end{aligned}

解读：这里性质定义成「不包含 i」，于是满足全部性质就等价于「一个都不含」，取补后恰好是「含全 1,2,\cdots,m」，正是等式左边的含义。恒等式的两端于是被同一批子集同时数了两遍。