组合计数 · 第 4 章

容斥原理

数出属于 A 或 B（或 C，或更多集合）的元素，又不把任何东西数两次：先加各集合，再减重叠部分，再加回来，并和补集计数配合使用。

这一章讲什么？

4.0 容斥原理
4.1 练习题

你需要先会

在 YouTube 上打开

4.00%

容斥原理

在本节中，你将能够 数出至少属于若干集合之一的元素个数：先加各集合，再减重叠部分，再加回来，正负号一直交替下去。

从 1 到 100 中，能被 2 或 7 整除的数有多少个？偶数有 50 个，7 的倍数有 14 个。但 64 太多了：14、28 和 42 在两张名单上都出现了！

把两个集合的元素个数直接相加，重叠部分会被数两次。所以要把重叠部分减去一次。这就是容斥原理 （英文缩写 PIE）。

有三个集合时，同时属于三个集合的元素被加了 3 次，又被减了 3 次。剩下 0 次，所以要再加回来一次。集合更多时，正负号一直交替下去。

注意：容斥原理和补集计数是好搭档。不合要求的情况很少时，用容斥原理数出它们，再从总数里减掉。

动手探索先玩，再学公式

试一试： 按“加上 |×2|”和“加上 |×7|”。得到 50 + 14 = 64。哪些数被数了两次？
试一试： 再按“减去 |×2 ∩ ×7|”。现在每个区域都恰好数了一次吗？打开“数字转文字”，核对一下 57。
试一试： 打开下面三个集合的卡片，逐项求和。看中心区域的计数怎样变化：+3，−3，+1。
试一试： 在例 4.9 中，哪些成对的 2×2 方块重叠 2 个格子，哪些只重叠 1 个？

认识概念

定义 4.0.1 · 容斥原理

容斥原理（PIE）是一种计数方法：它求出至少满足若干性质之一的元素个数，同时保证满足不止一个性质的元素不会被数两次。

定义 4.0.2 · 并集符号

$|A \cup B|$ 表示 $A$ 与 $B$ 的并集的元素个数：所有属于 $A$ 或属于 $B$ （或同时属于两者）的元素。重复的元素只写一次。

定义 4.0.3 · 交集符号

$|A \cap B|$ 表示 $A$ 与 $B$ 的交集的元素个数：只包括同时属于两个集合的元素。

定理 4.0.4 · 两个集合的容斥原理

对两个集合 $A_1$ 和 $A_2$ ，

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

简单地说，先数出 2 类“东西”各有多少种可能，再减去重复的部分。

注 4.0.5

当不满足要求的情况比满足要求的情况少得多时，把补集计数和容斥原理一起用往往很有帮助：先用容斥原理数出不合要求的情况，再从总数里减掉。

{1, …, 10} 的子集：不合要求的子集包含全部偶数，或包含全部 3 的倍数。

定理 4.0.6 · 三个集合的容斥原理

对三个集合 $A_1$ 、 $A_2$ 、 $A_3$ ，

\begin{aligned}|A_1 \cup A_2 \cup A_3| ={}& |A_1| + |A_2| + |A_3| \\ &- |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| \\ &+ |A_1 \cap A_2 \cap A_3|.\end{aligned}

先数出 3 类“东西”各有多少种可能，再减去 3 对集合中各自重复的部分，最后把同时属于 3 个集合的元素加回来。

逐项求和 →

重复计数表：每个区域被数了几次

只在美术中还没数
只在乐队中还没数
只在象棋中还没数
只在美术和乐队中还没数
只在美术和象棋中还没数
只在乐队和象棋中还没数
三个圈都在还没数

|美术|10

|乐队|9

|象棋|8

|美术 ∩ 乐队|4

|美术 ∩ 象棋|3

|乐队 ∩ 象棋|3

|美术 ∩ 乐队 ∩ 象棋|1

全部25

定理 4.0.7 · 一般形式的容斥原理

若 $A_1, A_2, \ldots, A_n$ 是有限集合，则

\left|\bigcup_{i=1}^{n} A_i\right| = \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| - \cdots + (-1)^{n-1} |A_1 \cap \cdots \cap A_n|.

加上单个集合，减去每两个的交集，加上每三个的交集，正负号一直交替下去。

集合数4

★ 所在集合数3

4 个集合的容斥轮次
轮次	符号	项数	含 ★ 的项	★ 计数
单个集合	+	4	·	·
每两个的交集	−	6	·	·
每三个的交集	+	4	·	·
每四个的交集	−	1	·	·

★ 被数了 0 次

4 个集合一共有 15 项。改变“★ 所在集合数”：最后一轮之后，计数总是恰好为 1。

看例题先预测，再揭晓

例 4.1

从 1 到 100（含两端）的数中，能被 2 或 7 整除的有多少个？

1
从 1 到 100 中，能被 2 整除的数有多少个？

先预测一下：
你的预测

例 4.2

AIME

许多州的标准车牌格式是三个字母后接三个数字。假设每一种“三个字母、三个数字”的排列都是等可能的，这样的车牌至少含有一个回文（即从左往右读和从右往左读都一样的三字母排列或三数字排列）的概率是 $\dfrac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

1
三个字母组成回文的概率是多少？

先预测一下：
你的预测

在 YouTube 上打开

例 4.3

Omega Learn

集合 $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ 有多少个子集至多含 4 个偶数，并且至多含 2 个 3 的倍数？

1
这里怎样用容斥原理？应该数合要求的子集，还是不合要求的子集？

先预测一下：
点击一个选项，或输入它的字母（A–E）。

例 4.4

Omega Learn

把单词 LOLLIPOP 中的字母重新排列，要求每个 L 都与一个 O 相邻，有多少种不同的排法？

1
有 3 个 L，但只有 2 个 O。每个 O 至多有 2 个邻居。这迫使出现什么情况？

在 YouTube 上打开

例 4.5

AIME

设 $S$ 是一个有六个元素的集合。设 $\mathcal{P}$ 是 $S$ 的所有子集组成的集合。从 $\mathcal{P}$ 中独立且随机地选取 $S$ 的子集 $A$ 和 $B$ （不一定互不相同）。 $B$ 包含于 $A$ 或 $S - A$ 之一的概率是 $\dfrac{m}{n^r}$ ，其中 $m$ 、 $n$ 、 $r$ 是正整数， $n$ 是质数，且 $m$ 与 $n$ 互质。求 $m + n + r$ 。（集合 $S - A$ 是由 $S$ 中所有不属于 $A$ 的元素组成的集合。）

1
选取 $A$ 和 $B$ 使得 $B$ 完全包含在 $A$ 中，有多少种方法？

先预测一下：
你的预测

例 4.6

小于或等于 193 的数中，是 2、3 或 5 的倍数的有多少个？

1
不超过 193 的数中，能被 2 整除的有多少个？

先预测一下：
你的预测

例 4.7

AMC 8

要把五个不同的奖项发给三名学生。每名学生至少得到一个奖项。共有多少种不同的发奖方法？

1
先不管规则。把 5 个不同的奖项发给 3 名学生，有多少种方法？

先预测一下：
你的预测

在 YouTube 上打开

例 4.8

Modified AIME

如果不存在 $a, b, c \in S$ （不一定互不相同）使得 $ab = c$ ，就称集合 $S$ 是无积集。例如，空集和集合 $\{16, 20\}$ 是无积集，而集合 $\{4, 16\}$ 和 $\{2, 8, 16\}$ 不是无积集。求集合 $\{1, 2, 3, 4, \ldots, 7, 8, 9\}$ 的无积子集的个数。

1
1 能在无积集里吗？

先预测一下：
点击一个选项，或输入它的字母（A–E）。

在 YouTube 上打开

例 4.9

AIME

一个 3×3 的单位正方形方格中，每个单位正方形都要涂成蓝色或红色。每个正方形涂哪种颜色是等可能的。得到的方格中不含红色 $2 \times 2$ 正方形的概率是 $\dfrac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

9 个自由格 → 2⁹ = 512

4 个集合的容斥轮次
轮次	选法	涂法数	累计
+ 单个集合	4	·	·
− 每两个的交集	6	·	·
+ 每三个的交集	4	·	·
− 每四个的交集	1	·	·

1
应该直接数不含红色 $2 \times 2$ 正方形的方格吗？

先预测一下：
点击一个选项，或输入它的字母（A–E）。

竞赛角真实竞赛题

习题 4.1.1

AIME

这道题在书中还以 4.2 的编号出现。

习题 4.1.2

AMC 10

要把七块互不相同的糖果分到三个袋子里。红袋子和蓝袋子都必须至少得到一块糖果；白袋子可以是空的。共有多少种分法？

习题 4.1.3

AMC 10

把数列 $1, 2, 3, 4, 5$ 重新排列，使得没有连续三项递增，也没有连续三项递减，有多少种方法？

习题 4.1.4

AMC 10

Ang、Ben 和 Jasmin 每人都有 5 块积木，颜色分别是红、蓝、黄、白、绿；另有 5 个空盒子。每个人都随机地、且与另外两人相互独立地，往每个盒子里放入自己的一块积木。至少有一个盒子收到 3 块同色积木的概率是 $\dfrac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。 $m + n$ 是多少？

过关检测（第 4.0 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

4.1

练习题

在本节中，你将能够 在竞赛题中运用容斥原理，从 AMC 10 热身题到 AIME 挑战题。

该做难一点的题了。每道题里都藏着一个需要数的并集，或者它的补集。先找出这些集合，再让容斥原理来干活。

最后三道是 AIME 挑战题。卡住时，每道题都有三条提示。

想在一页里看到本章的所有题目？打开习题集。

竞赛角真实竞赛题

习题 4.1.5

AMC 10

这道题在书中还以 4.1.3 的编号出现。

把数列 $1, 2, 3, 4, 5$ 重新排列，使得没有连续三项递增，也没有连续三项递减，有多少种方法？

习题 4.1.6（补充题）

AIME

求至少是 $10^{10}$ 、 $15^7$ 、 $18^{11}$ 中一个数的因数的正整数的个数。

习题 4.1.7（补充题）

AIME

在一场五支球队参加的比赛中，每支球队都与其他每支球队各赛一场。每支球队赢得它所参加的任何一场比赛的概率都是 $50\%$ 。（没有平局。）设比赛结果中既没有全胜的球队、也没有全败的球队的概率为 $\dfrac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的整数。求 $m + n$ 。

习题 4.1.8（补充题）

AIME挑战

如果不存在 $a, b, c \in S$ （不一定互不相同）使得 $ab = c$ ，就称集合 $S$ 是无积集。例如，空集和集合 $\{16, 20\}$ 是无积集，而集合 $\{4, 16\}$ 和 $\{2, 8, 16\}$ 不是无积集。求集合 $\{1, 2, 3, 4, \ldots, 7, 8, 9, 10\}$ 的无积子集的个数。

习题 4.1.9（补充题）

AIME挑战

定义正 $n$ 角星为 $n$ 条线段 $P_1P_2, P_2P_3, \ldots, P_nP_1$ 的并集，满足

点 $P_1, P_2, \ldots, P_n$ 共面，且其中任意三点不共线，
这 $n$ 条线段中的每一条都与其他线段中的至少一条在端点以外的某点相交， $P_1, P_2, \ldots, P_n$ 处的所有角都相等，
所有 $n$ 条线段 $P_1P_2, P_2P_3, \ldots, P_nP_1$ 都相等，并且路径 $P_1P_2, P_2P_3, \ldots, P_nP_1$ 在每个顶点处都按逆时针方向转一个小于 180 度的角。

不存在正 3 角星、正 4 角星或正 6 角星。所有正 5 角星都相似，但有两种互不相似的正 7 角星。互不相似的正 1000 角星有多少种？

习题 4.1.10（补充题）

AIME挑战

看节目时，Ayako、Billy、Carlos、Dahlia、Ehuang 和 Frank 按这个顺序坐在一排六把椅子上。中场休息时，他们去厨房拿零食。回来后，他们重新坐在这六把椅子上，并且如果两人在休息前相邻而坐，那么休息后他们就不相邻。求他们休息后可能的座次有多少种。