容斥原理、鸽巢原理与组合论证

第 12 章里，我们用加法原理、乘法原理、排列、组合和二项式系数处理“没有重叠”或“重叠已经被控制好”的计数问题。本章把注意力放到两类更容易出错的情形：有些对象会被重复计数，有些对象虽然无法直接指出是谁，却必然会重复落入同一类。

容斥原理处理“多算了多少”的问题。鸽巢原理处理“平均分也放不下”的问题。组合论证和双计数则把证明改写成计数：只要两种方法数的是同一批对象，它们的结果就必须相等。

本章的共同问题不是“公式是什么”，而是“我们到底在数什么对象”。如果对象说不清，容斥会减错，鸽巢会选错盒子，双计数也会变成形式相似但对象不同的等式。

从重复计数开始

在计数问题中，加法原理常被写成“互不重叠时可以相加”。这句话里的“互不重叠”很关键。若两个条件可能同时满足，直接相加就会把重叠对象数两次。

例如，某班有学生参加数学社，也有学生参加编程社。若我们把“参加数学社的人数”和“参加编程社的人数”直接相加，那么同时参加两个社团的学生会在两个名单里各出现一次。要得到至少参加一个社团的人数，就必须把这部分重复减掉一次。

容斥原理中的重叠计数示意图，参加数学社与参加编程社的重叠元素被数两次。 — 同一个对象满足多个条件时会重复计数：先问对象，再问次数。

这里有一个很实用的检查动作：不要先盯着公式，先盯着一个具体对象。它满足几个条件，就会在“先相加”的步骤里被数几次；目标计数想让它出现几次，就要修正到几次。

两集合容斥

设 $A$ 和 $B$ 是有限集合。并集 $A\cup B$ 中的对象是“属于 $A$ 或属于 $B$ ，或同时属于两者”的对象。先计算 $|A|+|B|$ 时，交集 $A\cap B$ 中的每个元素被数了两次，但在并集中只应该出现一次，所以要减去一次交集。

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

两个半透明集合圆相交，标出 A 集合、B 集合与重复区域，并展示两集合容斥公式。 — 两集合容斥：并集计数时需要减去被重复计算的交集。

例题：某班 48 人中，30 人选修了离散数学，22 人选修了程序设计，12 人同时选修了这两门课。至少选修其中一门课的学生有多少人？

先确定对象：要数的是“至少选修一门课的学生”，也就是两个选课集合的并集。

直接相加得到 $30+22=52$ ，但同时选修两门课的 12 人被数了两次。

下面的交互可以调节 $|A|$ 、 $|B|$ 和 $|A\cap B|$ 。观察交集变大时，并集为什么不一定变大。

“或”在数学里通常包含“同时”。“属于 $A$ 或属于 $B$ ”不是只属于其中一个，而是至少属于一个。若题目要排除同时满足的对象，会说“恰好一个”“只参加一个”或“二者之一但不同时”。

三集合容斥

三集合时，重复计数更容易藏起来。先把 $|A|,|B|,|C|$ 相加，落在两两交集里的对象会被多算；于是减去 $|A\cap B|,|A\cap C|,|B\cap C|$ 。但落在三重交集的对象，原来被加了三次，后来又在三个两两交集中被减了三次，结果变成零次。它在并集中应该出现一次，所以最后要加回三重交集。

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

三集合容斥原理示意图，展示先加单集合、减去两两交、再加回三重交的层级修正。 — 三集合容斥：先加单集合，减去两两交，最后加回三重交。

例题：一次调查中，38 人喜欢数学题，32 人喜欢程序题，25 人喜欢逻辑题。喜欢数学题和程序题的有 15 人，喜欢数学题和逻辑题的有 12 人，喜欢程序题和逻辑题的有 10 人，三类都喜欢的有 5 人。至少喜欢其中一类题的人有多少？

这里要数的是三个集合的并集。题目给出的两两交集人数包含三类都喜欢的人，这是容斥公式所需要的交集，不要把三重交集先排除掉。

先加三个单集合：

38+32+25=95

因此至少喜欢一类题的人有 63 人。

至少、至多与恰好

容斥经常和“至少”“至多”“恰好”一起出现。它们不是同一种问法。

“至少一个”常常对应并集。比如至少参加一个活动，就是属于活动集合的并集。

“一个也不”常常用补集处理。若总体有 $N$ 个对象，而至少满足一个条件的有 $M$ 个，那么一个条件也不满足的有 $N-M$ 个。

“恰好一个”不能直接用并集。它要排除同时满足多个条件的对象。例如对两个集合来说，恰好属于一个集合的人数是

|A\setminus B|+|B\setminus A|=|A|+|B|-2|A\cap B|

常见错误是看到“至少一个”就直接把各条件人数相加。只要条件之间可能重叠，直接相加就不是并集人数，而是“带重复的出现次数”。

练习：某校 100 名学生中，60 人参加过志愿服务，45 人参加过学术讲座，25 人两者都参加过。至少参加过一种活动的有多少人？两种活动都没参加过的有多少人？恰好参加一种活动的有多少人？

至少参加一种活动的人数是 $60+45-25=80$ 。两种都没参加过的人数是 $100-80=20$ 。恰好参加一种活动的人数是 $(60-25)+(45-25)=55$ ，也可以用。

鸽巢原理

容斥处理的是“重复计数已经发生，怎样修正”。鸽巢原理处理的是另一种重复：当物品比盒子多时，即使不知道具体分布，也能断定某个盒子里必然放了不止一个物品。

最基本的鸽巢原理是：若把 $n+1$ 个物品放入 $n$ 个盒子，那么至少有一个盒子中有不少于 $2$ 个物品。

7 个物品分配到 6 个盒子中，其中一个盒子至少包含 2 个物品，展示鸽巢原理。 — 鸽巢原理：7 个物品放入 6 个盒子，必有一个盒子不少于 2 个。

这个结论的证明很短。若每个盒子最多只有 1 个物品，那么 $n$ 个盒子最多只能容纳 $n$ 个物品。这与已经放入 $n+1$ 个物品矛盾。所以至少有一个盒子中有 2 个或更多物品。

如何选物品和盒子

用鸽巢原理时，真正困难的地方通常不是证明，而是建模。需要明确两件事：物品是什么，盒子是什么。物品是被分配的对象；盒子是按某个特征划分出的类别。

例题：任取 13 个人，必有两个人出生月份相同。

把 13 个人看成物品。每个人都有一个出生月份。

把 12 个月份看成盒子。一个人出生在哪个月，就被放入哪个月份盒子。

若每个月最多只有 1 人，那么 12 个月最多容纳 12 人。

现在有 13 人，所以至少有一个月份盒子中不少于 2 人。也就是至少有两个人出生月份相同。

12 个月份格子中分布 13 个学生圆点，其中一个月份格子有 2 个圆点并高亮，说明 13 人中至少有 2 人同月生日。 — 13 人分到 12 个月，至少有一个月份有 2 人。

广义鸽巢原理

若把 $N$ 个物品放入 $k$ 个盒子，那么至少有一个盒子中有不少于

\left\lceil \frac{N}{k}\right\rceil

个物品。这里的天花板符号表示向上取整。

理由仍然来自反证。若每个盒子最多只有 $\left\lceil N/k\right\rceil-1$ 个物品，那么总容量最多是

k\left(\left\lceil \frac{N}{k}\right\rceil-1\right)

这个数小于 $N$ ，无法放下全部物品。因此必有某个盒子达到至少 $\left\lceil N/k\right\rceil$ 个。

下面的模拟器可以调节物品数和盒子数。注意观察：结论保证的是“至少有一个盒子达到下界”，并不保证每个盒子都接近平均。

例题：班里有 41 名学生。若按星期几出生来分组，证明至少有 6 名学生出生在同一个星期几。

物品是 41 名学生，盒子是 7 个星期类别。

按广义鸽巢原理，至少有一个盒子里的人数不少于

\left\lceil \frac{41}{7}\right\rceil=6

鸽巢原理给的是存在性结论。它能证明“必有某个盒子很多”，但通常不能告诉你是哪一个盒子。若题目要求指出具体对象，还需要额外信息。

练习：从 10 双不同颜色的袜子中任意取袜子。最少取多少只，才能保证至少有两只是同一双的左右袜？

最少取 11 只。把 10 双袜子看成 10 个盒子，每取一只袜子就落入对应那一双的盒子。若只取 10 只，可能每双各取一只，还不能保证成双。取 11 只时，10 个盒子放入 11 个物品，至少有一个盒子有 2 只袜子，也就是取到了同一双的左右袜。

组合证明

组合证明的目标不是先做代数变形，而是给等式两边找到同一个计数对象。若左边和右边都在数同一批东西，只是分组方式不同，那么它们相等。

一个经典例子是

\binom{n}{r}=\binom{n}{n-r}

代数上可以用阶乘公式化简。组合上更直接：从 $n$ 个对象中选出 $r$ 个，与从 $n$ 个对象中留下 $n-r$ 个没有被选中的对象，是同一个选择的两种描述。每选出一个 $r$ 人小组，就唯一决定一个 $n-r$ 人的未选集合；反过来也一样。

组合证明的写法

组合证明通常有三步。

先定义一个清楚的对象集合，例如“从 $n$ 人中选出一个 $r$ 人小组”或“带组长的 $r$ 人小组”。

用第一种方法计数，得到等式左边。这里要说明每个选择为什么被数一次，不能只写公式。

组合证明的好处是保留了式子的意义。等式不再只是符号相等，而是在说“同一批对象可以被两种方式组织”。

例题：用组合证明说明

r\binom{n}{r}=n\binom{n-1}{r-1}

其中 $1\le r\le n$ 。

证明对象设为“从 $n$ 个人中选出一个 $r$ 人小组，并在小组中指定一名组长”。

先按小组来数。先从 $n$ 人中选出 $r$ 人小组，有 $\binom{n}{r}$ 种；每个小组中再选一名组长，有种。因此共有种。

下面的交互把这两个路径放在同一屏中。改变 $n$ 和 $r$ ，观察两边为什么同步变化。

练习：给出一个组合证明说明

\binom{n}{2}=\frac{n(n-1)}{2}

数同一批对象：从 $n$ 个人中选出一对人。按组合数定义，有 $\binom{n}{2}$ 种。若先选第一个人再选第二个人，有 $n(n-1)$ 种有顺序选择；但每一对人被按两个顺序数了两次，所以无顺序的一对共有 $\frac{n(n-1)}{2}$ 种。两种方法数的是同一批二人组，因此。

双计数与握手思想

双计数是组合证明中最常见的一种形式：把同一批对象按两种维度求和。它经常用来证明恒等式，也能解释图论里的握手定理。

设一个有限无向图有顶点集合 $V$ 和边集合 $E$ 。把所有顶点的度数相加，相当于数“边端点关联”这批对象：

\{(v,e): v\in V,\ e\in E,\ v\text{ 是 }e\text{ 的端点}\}

从顶点角度数，对每个顶点 $v$ ，与它关联的边有 $\deg(v)$ 条，所以总数是

\sum_{v\in V}\deg(v)

从边角度数，每条边有两个端点，所以总数是

2|E|

两种方法数的是同一批“顶点与关联边”的配对，因此

\sum_{v\in V}\deg(v)=2|E|

双计数与握手定理示意图，左侧无向图标出各顶点度数，右侧按边的两个端点计数，底部给出度数和等于二倍边数。 — 同一批边既可按顶点度数求和，也可按每条边贡献两个端点来计数。

双计数证明中的对象一致性

双计数最容易出错的地方，是两边实际上数了不同对象。例如，一边数“有组长的小组”，另一边却数“没有组长的小组”；或者一边允许重复，另一边不允许重复。这时即使式子看起来相近，也不能构成证明。

写双计数证明时，可以用下面的问题自查：

对象集合能不能用一句话说清？
每个对象在左边是否恰好出现一次？
每个对象在右边是否恰好出现一次？
左边和右边是否允许相同的限制条件？

例题：证明在任意有限无向图中，奇度数顶点的个数是偶数。

由握手定理，所有顶点度数之和是 $2|E|$ ，所以它是偶数。

偶度数顶点的度数相加仍然是偶数。

因此奇度数顶点的度数总和也必须是偶数。

这个结论很小，但它展示了本章三种思想的连接：先明确计数对象，再用双计数得到总量约束，最后从奇偶性推出必然结构。

混合例题：选工具

很多题目不会直接告诉你“请使用容斥”或“请使用鸽巢”。选择工具时，先看题目中的信号。

若问题问“至少满足一个条件”“没有满足任何条件”“重复名单如何合并”，通常考虑容斥或补集。

若问题问“证明必有两个对象共享某个特征”“最少多少个才能保证重复”，通常考虑鸽巢原理。

若问题问“证明一个组合恒等式”“同一对象能不能从两条路径计数”，通常考虑组合证明或双计数。

例题：整数余数

证明：任取 6 个整数，必有两个整数的差能被 5 整除。

两个整数的差能被 5 整除，等价于它们除以 5 的余数相同。

把 6 个整数看成物品，把除以 5 的余数 $0,1,2,3,4$ 看成 5 个盒子。

例题：含指定数字的字符串

长度为 4 的数字串允许首位为 0。问：至少含有一个 0 或至少含有一个 1 的数字串有多少个？

设 $A$ 为含有至少一个 0 的数字串集合， $B$ 为含有至少一个 1 的数字串集合。题目要数 $|A\cup B|$ 。

这里最后的结果也有一个更短解释：至少含 0 或至少含 1，等价于“不全由 2 到 9 这 8 个数字组成”，所以是 $10^4-8^4$ 。容斥推导和补集推导得到同一个结果，说明它们确实在数同一批对象。

当条件很多时，容斥不一定是最短路线。若题目问“至少满足某些条件”，先看补集是否更简单；若补集只需要排除少数情况，通常比逐层容斥更干净。

本章小结与练习

容斥原理的核心是修正重复。两集合时，先加两个集合，再减交集；三集合时，先加单集合，减两两交，再加三重交。

鸽巢原理的核心是容量不足。只要物品数超过盒子按某个上限能容纳的总数，就能推出某个盒子超过这个上限。广义形式给出至少 $\left\lceil N/k\right\rceil$ 的下界。

组合证明和双计数的核心是对象一致。先说清同一批对象，再分别从两条路径计数，得到等式或结构约束。

练习 1：某班 70 人中，42 人会 Python，35 人会 Java，18 人两种都会。至少会一种语言的有多少人？两种都不会的有多少人？

至少会一种语言的人数是 $42+35-18=59$ 。两种都不会的人数是 $70-59=11$ 。

练习 2：证明任取 9 个整数，必有两个整数除以 8 的余数相同。

把 9 个整数看成物品，把除以 8 的余数 $0,1,\ldots,7$ 看成 8 个盒子。9 个物品放入 8 个盒子，按鸽巢原理，至少有一个盒子中有两个整数，所以这两个整数除以 8 的余数相同。

练习 3：用组合证明说明

\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}

其中 $0\le k\le r\le n$ 。

数同一批对象：从 $n$ 个对象中先选出一个 $r$ 个对象的集合，并在其中标出一个 $k$ 个对象的子集合。左边先选 $r$ 个对象，再从这 $r$ 个对象中选出被标出的 $k$ 个对象，所以是 $\binom{n}{r}\binom{r}{k}$ 。右边先选出被标出的个对象，再从剩下的个对象中选出个普通对象，所以是。两种方法数的是同一批带标出子集的元集合，因此相等。

r

r

离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 13 章：容斥原理、鸽巢原理与组合论证 | 自在学