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

上一章里，我们把加法原理、乘法原理、排列和组合连成了一套计数工具。那些方法最舒服的使用场景，是每个结果都能沿着一条清楚的路径被数到，而且只被数一次。可现实中的条件经常互相重叠：同一个学生可能加入两个社团，同一个排列可能同时违反几条限制，同一个对象也可能被好几种描述方式碰到。

这时真正的问题不再是“该乘还是该加”，而是两句更细的问题：一个对象现在被数了几次？我们希望它最后留下几次？ 容斥原理负责把重复次数修正回来；鸽巢原理反过来利用“重复无法避免”推出存在性；组合论证则主动设计两种计数方式，让“同一批对象的总数不变”成为证明。

这三种方法表面上各做各的事，骨子里却共享一个习惯：先说清对象，再谈公式。本章会不断把思考过程摆在台面上。你会看到公式为什么非得长成那个样子，也会看到一道题在动笔前究竟该怎样选择集合、盒子或计数对象。

本章的主线可以压成一句话：容斥问“重复了几次”，鸽巢问“重复是否必然”，组合论证问“能否换一种方式数同一件事”。

容斥的起点：重复从哪里产生

假设班里有人参加数学社，也有人参加编程社。我们把数学社成员组成的集合记为 $A$ ，把编程社成员组成的集合记为 $B$ 。若直接计算 $|A|+|B|$ ，只参加一个社团的人被数一次，同时参加两个社团的人却会在两份名单中各出现一次，也就是被数两次。

但“至少参加一个社团”对应的是并集 $A\cup B$ 。并集只关心一个人是否出现，不关心他出现在哪几份名单里，因此每个人最终都应该只留下一次。这正是减去交集的原因：

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

1+1-1=1.

这是一种很可靠的检查法。遇到复杂容斥时，随便挑一个满足若干条件的对象，沿公式数一遍它的净贡献。若目标是并集，它最后必须恰好贡献 $1$ ；不在并集里的对象必须贡献 $0$ 。

两集合例题：先问并集，再问补集

某班有 48 人，其中 30 人选修离散数学，22 人选修程序设计，12 人同时选修两门课。问至少选修其中一门、两门都不选、恰好选修一门的学生各有多少？

设 $A$ 为选修离散数学的学生集合， $B$ 为选修程序设计的学生集合。“至少一门”就是 $A\cup B$ ，所以

|A\cup B|=30+22-12=40.

全班 48 人是总体。两门都不选的人在并集的补集中，所以人数是

48-|A\cup B|=48-40=8.

“恰好一门”不包含交集。只选离散数学的有 $30-12=18$ 人，只选程序设计的有 $22-12=10$ 人，因此共有 $18+10=28$ 人。

最后一个答案也可以直接写成

|A|+|B|-2|A\cap B|=30+22-2\cdot12=28.

为什么这次交集要减两次？因为只属于一个集合的人在 $|A|+|B|$ 中出现一次，本来就符合目标；交集里的人出现两次，而“恰好一个”希望他们出现零次，所以必须把两次都减掉。

下面的交互允许你调节 $|A|$ 、 $|B|$ 和 $|A\cap B|$ 。可以试着把交集从 0 拉到最大：直接相加的数字不变，但并集会随着重复区域增大而变小。

数学里的“或”通常是包含性的。“属于 $A$ 或属于 $B$ ”表示至少属于一个，也允许同时属于两者。只有“恰好一个”“二者之一但不同时”才会排除交集。

看到“至少一个”时，先看补集是否更短

长度为 6 的十进制数字串允许首位为 0。问至少出现一次数字 7 的字符串有多少个？

如果按“7 出现在第几位”分类，六类会大量重叠：一个字符串可以在两位、三位甚至六位上都出现 7。容斥当然能做，但补集只需一句话：总共有 $10^6$ 个数字串，完全不含 7 的每一位都有 9 种选择，共有 $9^6$ 个。因此答案是

10^6-9^6.

这里值得养成一个次序：

“至少一个”先翻译成若干集合的并集；
再问它的补集“一个也没有”是否更容易数；
只有补集也互相重叠时，才展开容斥。

三集合容斥：为什么最后必须加回来

两集合只有一层重叠，减一次就结束了。三个集合 $A,B,C$ 的麻烦在三重交集：属于三个集合的对象，同时也属于三个两两交集。

三集合公式是

\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}

这串符号最容易背错的地方，是误以为 $A\cap B$ 只表示“在 $A$ 和 $B$ 里、但不在 $C$ 里”。不是。 $A\cap B$ 包含所有同时属于 $A$ 与 $B$ 的对象，其中也包括三重交集 $A\cap B\cap C$ 。

按对象所在集合的个数逐一检查，就能看见公式为什么成立：

只在一个集合里的对象，在第一行被加一次，净贡献是 $1$ 。
恰好在两个集合里的对象，先被加两次，再由对应的两两交集减一次，净贡献是 $2-1=1$ 。
在三个集合里的对象，先被三个单集合加三次，又被三个两两交集各减一次，暂时变成 $3-3=0$ ；所以最后必须由三重交集加回一次，净贡献才是 $1$ 。

手绘彩色线条风格的三集合容斥图，说明先加单集合、减去包含三重交的两两交，再加回三重交。 — 两两交必须包含中央的三重交；中央区域经历三次加、三次减、一次加回。

三集合例题：题目给的两两交通常包含三重交

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

设三个集合分别为 $A,B,C$ 。直接代入三集合容斥：

\begin{aligned} |A\cup B\cup C| &=38+32+25-15-12-10+5\\ &=63. \end{aligned}

这里的 15 人是完整的 $A\cap B$ ，其中包含三类都喜欢的 5 人。若先把这 5 人从两两交中扣掉，再照原公式计算，就会破坏容斥的次数修正。

“至少”“恰好”如何从同一组数据中读出来

三集合题不只会问并集。为了看清各种问法之间的关系，记

s_1=|A|+|B|+|C|,

s_2=|A\cap B|+|A\cap C|+|B\cap C|,

s_3=|A\cap B\cap C|.

$s_1$ 不是并集人数，而是所有“成员资格”的总出现次数：恰好属于两个集合的人贡献 2，属于三个集合的人贡献 3。类似地， $s_2$ 里，恰好属于两个集合的人贡献 1，属于三个集合的人会落入三个两两交集，因此贡献 3。

于是有：

\begin{aligned} N_{\text{恰好三个}}&=s_3,\\ N_{\text{恰好两个}}&=s_2-3s_3,\\ N_{\text{至少两个}}&=s_2-2s_3,\\ N_{\text{恰好一个}}&=s_1-2s_2+3s_3,\\ N_{\text{至少一个}}&=s_1-s_2+s_3. \end{aligned}

以刚才的调查为例， $s_1=95,s_2=37,s_3=5$ 。因此恰好喜欢两类的有 $37-3\cdot5=22$ 人，至少喜欢两类的有 $37-2\cdot5=27$ 人，恰好喜欢一类的有 $95-2\cdot37+3\cdot5=36$ 人。检查一下： $36+22+5=63$ ，正好等于至少喜欢一类的人数。

遇到“恰好”型问题，不妨先问每种对象在单集合和交集中分别贡献几次。容斥不是只能求并集；它本质上是一套把“出现次数”还原成“对象数”的办法。

一般容斥：交替符号不是装饰

如果有 $n$ 个有限集合 $S_1,S_2,\ldots,S_n$ ，并集大小可以写成

\left|\bigcup_{i=1}^{n}S_i\right| =\sum_{\varnothing\ne I\subseteq\{1,2,\ldots,n\}} (-1)^{|I|+1} \left|\bigcap_{i\in I}S_i\right|.

把它拆成口语，就是：

加上所有单集合大小；
减去所有两两交集大小；
加上所有三重交集大小；
减去所有四重交集大小；
一直交替到最后。

为什么奇数层加、偶数层减就够了？假设某个对象 $x$ 恰好属于 $t$ 个集合。它会出现在 $t$ 个单集合中，出现在 $\binom{t}{2}$ 个两两交集中，出现在 $\binom{t}{3}$ 个三重交集中，依此类推。所以它对一般容斥右侧的总贡献是

\binom{t}{1}-\binom{t}{2}+\binom{t}{3}-\cdots+(-1)^{t+1}\binom{t}{t}.

由二项式展开

(1-1)^t =\binom{t}{0}-\binom{t}{1}+\binom{t}{2}-\cdots+(-1)^t\binom{t}{t}=0,

把 $\binom{t}{0}=1$ 移到另一边，就得到上面的交替和等于 $1$ 。也就是说，不管 $x$ 同时满足多少个条件，它经过所有修正以后都恰好留下一个副本。

这个解释非常重要：一般容斥不是凭图形猜出来的。两个圆、三个圆还能画，十个集合已经没法靠维恩图看清；逐元素的净贡献证明却对任意有限个集合都成立。

什么时候不必把公式展开到底

一般公式看起来项很多，但题目中的结构常会让大量交集相等或直接为空。实际计算时，先寻找这两类简化：

若任意四个条件不可能同时满足，那么四重及更高交集全是空集，公式可以在三重交处停止。
若任意 $k$ 个指定条件的交集大小只取决于 $k$ ，就把同层的 $\binom{n}{k}$ 个交集合并计算。

后一种情形正好会在错位排列中出现。

错位排列：用容斥数“谁都不回原位”

有 $n$ 封写好地址的信和 $n$ 个对应的信封。把信随机装入信封，要求没有任何一封信进入自己的信封。这样的排列叫作一个错位排列。

直接数“每封都放错”很别扭，因为第一封放错后，后续可选位置数并不总是简单地少一个；早期选择还会影响最后能否收尾。容斥的思路是反过来：先把所有 $n!$ 个排列都算上，再排除“至少有一封放对”的排列。

对每个位置 $i$ ，定义坏事件集合

A_i=\{\pi:\pi(i)=i\}.

$A_i$ 表示第 $i$ 个对象留在原位。错位排列数 $D_n$ 因而是

D_n=n!-\left|A_1\cup A_2\cup\cdots\cup A_n\right|.

现在逐层计算交集。

指定一个位置固定后，剩余 $n-1$ 个对象任意排列，所以 $|A_i|=(n-1)!$ 。共有 $\binom n1$ 个这样的集合。
指定两个位置都固定后，剩余 $n-2$ 个对象任意排列，所以每个两两交集大小是 $(n-2)!$ 。共有 $\binom n2$ 个两两交集。
一般地，指定 $k$ 个位置固定，剩余对象有 $(n-k)!$ 种排列；选择这 $k$ 个固定位置有 $\binom nk$ 种。

于是容斥给出

\begin{aligned} D_n &=n!-\binom n1(n-1)!+\binom n2(n-2)!-\cdots+(-1)^n\binom nn0!\\ &=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}. \end{aligned}

第二行只是利用了

\binom nk(n-k)!=\frac{n!}{k!}.

以 $n=4$ 为例：

D_4=24-4\cdot6+6\cdot2-4\cdot1+1=9.

这 9 个结果不是靠一个新排列公式突然算出来的，而是从 24 个排列开始，对“位置 1 固定”“位置 2 固定”等互相重叠的坏条件做了完整修正。

计数“所有条件都不发生”时，一个常用策略是先定义每个坏条件 $A_i$ ，再计算总体减去 $\left|\bigcup_i A_i\right|$ 。错位排列就是这套策略最典型的样板。

把 $D_n$ 除以总排列数 $n!$ ，得到错位发生的比例

\frac{D_n}{n!}=\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

这已经开始像概率问题了：计数给出“有利结果数”和“全部结果数”，下一章会把它们的比值正式解释成等可能模型中的概率。

鸽巢原理：平均容量不够时，重复必然发生

容斥是在重复已经出现后修正计数。鸽巢原理则更干脆：当类别数量不足时，不必知道具体怎样分配，也能断定重复一定出现。

最基本的形式是：把 $n+1$ 个物品放入 $n$ 个盒子，至少有一个盒子装了不少于 2 个物品。

证明只有一步反证。假设每个盒子至多装 1 个物品，那么 $n$ 个盒子的总容量至多是 $n$ ，不可能容纳 $n+1$ 个物品。因此“每盒至多 1 个”的假设必定失败。

用函数语言说得更精确一些：设物品集合为 $A$ ，盒子集合为 $B$ ，每个物品按规则 $f$ 放进一个盒子，也就是有一个函数

f:A\to B.

若 $|A|>|B|$ ，这个函数不可能是一一对应到不同盒子的单射，所以必有不同的 $a_1,a_2\in A$ 满足

f(a_1)=f(a_2).

这句话把鸽巢题的真正难点暴露出来了：通常不是证明原理，而是设计 $A$ 、 $B$ 和 $f$ 。

建模时必须说清的三件事

每次使用鸽巢原理，最好明确写出：

物品是什么：哪些对象正在被分配；
盒子是什么：按哪一种共同特征分类；
分配规则是什么：每个物品究竟进入哪个盒子，并且是否恰好进入一个盒子。

例如，任取 13 个人，证明至少两个人出生月份相同。物品是 13 个人，盒子是 12 个月份，分配规则是“把每个人放进自己的出生月份”。每个人恰好有一个出生月份，因此这确实定义了从 13 个物品到 12 个盒子的函数。

“盒子”必须形成一个完整分类。若某个物品无盒可进，或能同时随意进入多个盒子，就还没有定义好分配函数，不能直接使用鸽巢原理。

余数为什么经常是好盒子

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

看到“差能被 5 整除”，先把它翻译成“除以 5 的余数相同”。整数除以 5 只有 $0,1,2,3,4$ 五种余数，于是：

物品是选出的 6 个整数；
盒子是 5 种余数；
分配规则是把每个整数放入它的余数盒子。

6 个物品进入 5 个盒子，必有两个整数进入同一个余数盒。设它们是 $x,y$ ，那么 $x\equiv y\pmod 5$ ，所以 $5\mid(x-y)$ 。

这里的盒子不是题面上现成写出的。我们是从目标“差可整除”倒推，发现相同余数正好能推出目标，于是主动把余数设计成盒子。

广义鸽巢原理与保证阈值

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

\left\lceil\frac Nk\right\rceil

个物品。天花板符号 $\lceil x\rceil$ 表示不小于 $x$ 的最小整数。

为什么要向上取整？若平均数是 $5.1$ ，物品数又必须是整数，那么“至少有一个盒子达到平均数”实际就意味着至少有 6 个，而不是 5 个。

证明仍然从容量上限出发。若每个盒子至多有 $\left\lceil N/k\right\rceil-1$ 个物品，总物品数至多为

k\left(\left\lceil\frac Nk\right\rceil-1\right)<N,

与已经放入 $N$ 个物品矛盾。

广义形式还常写成一个更适合“至少 $r$ 个”的阈值：若想保证某个盒子至少有 $r$ 个物品，最少需要

k(r-1)+1

个物品。因为只放 $k(r-1)$ 个时，完全可能每个盒子恰好放 $r-1$ 个；再多放一个，至少一个盒子就会越过上限。

例如，一周有 7 种出生星期。要保证一群学生中至少有 6 人出生在同一个星期几，人数至少应为

7(6-1)+1=36.

35 人还不够，因为可能七天各有 5 人；36 人时，无论怎样分配，都有某一天至少 6 人。

下面的模拟器可以改变物品数和盒子数。请特别观察两件事：下界由 $\lceil N/k\rceil$ 决定；结论只保证“某个盒子”达到下界，并不保证每个盒子都接近平均。

广义鸽巢原理能保证什么，不能保证什么

它保证的是一个最坏情况下仍无法逃开的下界。例如 $41$ 名学生按出生星期分到 7 个盒子，必有一个盒子至少包含

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

人。但它没有告诉我们是哪一天，也没有说刚好是 6 人；实际可能有 7 人、10 人甚至更多。更不能反过来说每个星期都至少有 6 人。

这类证明通常是非构造性的：它证明某个对象一定存在，却不负责把对象指出来。若题目还要求找出具体的那一组，就需要数据、算法或额外结构。

盒子不一定是日历格：相同子集和

给定 10 个正整数，每个都不超过 20；即使某些数值相同，也按它们在列表中的位置区分。证明存在两个不同的下标子集，它们选中数的和相同。

这次物品不是 10 个整数，而是 10 个位置的 所有下标子集。10 个位置共有

2^{10}=1024

个子集。每个子集的和最小为 0，最大不超过 $10\cdot20=200$ ，所以可能的和只有 $0,1,\ldots,200$ ，共 201 个。把每个子集按“元素和”放进相应盒子，1024 个物品进入 201 个盒子，必有两个不同子集具有相同的和。

这个例子展示了鸽巢原理最有创造性的地方：物品可以是组合对象，盒子可以是一个数值结果。我们没有找出那两个子集，却能确定它们无论如何都存在。

组合证明：先决定要数哪一批对象

组合证明用计数来证明等式。标准结构很短：

定义一个有限对象集合 $S$ ；
用第一种方式计数，得到 $|S|=L$ ；
用第二种方式计数，得到 $|S|=R$ ；
因为两边数的是同一个 $S$ ，所以 $L=R$ 。

真正费脑子的不是最后一句，而是如何选择 $S$ 。一个很实用的起点是先看等式中最简单的一边：如果出现 $\binom nk$ ，就尝试把 $S$ 设计成某个 $n$ 元集合的 $k$ 元子集；如果出现两个组合数的乘积，往往意味着对象由两步选择组成；如果出现一串求和，往往意味着同一批对象按某个参数被分成互不重叠的类别。

补集解释对称恒等式

恒等式

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

可以用阶乘化简，但组合解释更能说明它为什么自然。令 $S$ 为从 $n$ 个对象中选出的所有 $r$ 元子集。每选出一个 $r$ 元子集，就唯一确定了一个由未选对象组成的 $(n-r)$ 元补集；反过来，给定补集也唯一确定被选集合。因此“选出 $r$ 个”和“留下 $n-r$ 个”是一一对应的两种描述，两边数量相同。

Pascal 恒等式：围绕一个特殊对象分情况

从 $n$ 个人中选 $r$ 人小组，一共有 $\binom nr$ 种。现在固定其中一个人，叫他小林。每个 $r$ 人小组恰好属于下面两类之一：

小林入选：还需从其余 $n-1$ 人中选 $r-1$ 人，有 $\binom{n-1}{r-1}$ 种；
小林不入选：全部 $r$ 人都从其余 $n-1$ 人中选，有 $\binom{n-1}{r}$ 种。

两类互不重叠，又覆盖所有 $r$ 人小组，因此

\binom nr=\binom{n-1}{r-1}+\binom{n-1}{r}.

这里不是把右边代数化简成左边，而是把同一个集合 $S$ 按“是否包含小林”切成了两块。Pascal 三角形中每个内部数字等于左上与右上之和，背后的计数意义就在这里。

带组长的小组：乘法次序不同，总数不变

证明

r\binom nr=n\binom{n-1}{r-1},\qquad 1\le r\le n.

我们不先动公式，而是定义对象：从 $n$ 个人中选一个 $r$ 人小组，并在组内指定一名组长。

先选小组，有 $\binom nr$ 种；再从组内 $r$ 人中选组长，有 $r$ 种。总数为

\binom nr\cdot r.

也可以先从全体 $n$ 人中选组长，有 $n$ 种；再从剩下的 $n-1$ 人中选 $r-1$ 名普通成员，有 $\binom{n-1}{r-1}$ 种。总数为

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

两条路径都生成且只生成“带一名组长的 $r$ 人小组”，所以结果相等。

下面的交互把两条计数路径并排展示。改变 $n$ 与 $r$ 时，数值会变，但被计数对象始终是“带组长的小组”。

双计数不能只看两边式子是否相似。若一边数“带组长的小组”，另一边数“普通小组”，对象已经不同；若一边允许重复选择而另一边不允许，对象也不同。必须明确说明两边的限制完全一致，并且每个对象在每边都恰好出现一次。

求和型组合恒等式：按类别数，再一次数完

乘积常对应连续选择，求和常对应互斥分类。考虑恒等式

\sum_{j=0}^{r}\binom mj\binom n{r-j}=\binom{m+n}{r}.

令 $S$ 为从两个班的学生中合选 $r$ 人代表的所有方案：甲班有 $m$ 人，乙班有 $n$ 人。

直接数：两班合计 $m+n$ 人，从中选 $r$ 人，所以

|S|=\binom{m+n}{r}.

分类数：按代表中“有多少人来自甲班”分类。若甲班恰有 $j$ 人入选，就要从甲班选 $j$ 人、从乙班选 $r-j$ 人，共有

\binom mj\binom n{r-j}

种。不同的 $j$ 不可能描述同一个代表团，因此这些类别互不重叠；把所有可能的 $j$ 相加，就得到左边。

严格地说，若某些 $j$ 超出可选范围，对应组合数视为 0；也可以把求和范围写成

\max(0,r-n)\le j\le\min(r,m).

两种计数都覆盖了 $S$ 中每个 $r$ 人代表团且不重不漏，所以恒等式成立。

这个例子也为下一章埋下一条线索：两个选择来源合在一起时，按总规模 $r$ 汇总所有拆分 $j+(r-j)$ ，正是生成函数乘法中“系数卷积”的计数含义。

双计数：从两个方向数关联关系

组合证明有时不是“一次选出一组对象”，而是数一批配对关系。设有限集合 $X,Y$ 之间有某种关系 $R\subseteq X\times Y$ 。对每个 $x\in X$ ，数它关联了多少个 $y$ ；再对每个 $y\in Y$ ，数它关联了多少个 $x$ 。两边都在数关系 $R$ 中的有序对，因此

\sum_{x\in X}\#\{y:(x,y)\in R\} = \sum_{y\in Y}\#\{x:(x,y)\in R\}.

这就是双计数最通用的形状。

握手思想：每条边有两个端点

在一个有限简单无向图中，把关系对象定义为

R=\{(v,e):v\text{ 是边 }e\text{ 的一个端点}\}.

按顶点 $v$ 来数，与它关联的边有 $\deg(v)$ 条，所以

|R|=\sum_{v\in V}\deg(v).

按边 $e$ 来数，每条无向边有两个端点，所以

|R|=2|E|.

因此

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

这不是把图论结论硬塞进计数公式，而是从两个方向数同一批“顶点—边关联”。它还立刻推出：任意有限无向图中，奇度顶点的个数必为偶数。因为度数总和是偶数，偶度顶点贡献的和也是偶数，剩下的奇度数之和必须为偶数；只有偶数个奇数相加才是偶数。

后面进入图论时，这种“每条边向两个端点各贡献一次”的视角会反复出现。

怎样判断该用哪一种工具

综合题不会在题目前标注方法名。可以先观察语言信号，再用对象检查确认。

出现“至少满足一个条件”“把多份有重叠的名单合并”“所有坏条件都不发生”，先考虑并集、补集与容斥。
出现“无论怎样安排都必有”“最少多少个才能保证”“证明两个对象共享同一特征”，先尝试寻找物品、盒子与分配规则。
出现组合数恒等式，尤其一边是求和、一边是单个组合数，先尝试为两边寻找同一个选择对象。
出现度数和、行和与列和、成员与小组、顶点与边等双向关联，优先考虑双计数。

方法不是由关键词机械决定的。最后的检验始终是：容斥中每个对象净贡献是否正确；鸽巢中每个物品是否恰好进入一个盒子；组合证明中两边是否真在数同一批对象。

混合例题：至少含 0 或 1 的数字串

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

设 $A$ 为至少含一个 0 的字符串集合， $B$ 为至少含一个 1 的字符串集合。若展开容斥，

|A|=|B|=10^4-9^4,

而同时含 0 和 1 的字符串数为

|A\cap B|=10^4-2\cdot9^4+8^4.

所以

\begin{aligned} |A\cup B| &=2(10^4-9^4)-(10^4-2\cdot9^4+8^4)\\ &=10^4-8^4. \end{aligned}

不过，思路更短的是直接看补集：不属于 $A\cup B$ ，就意味着四位都不是 0 或 1，每一位只有 $2,3,\ldots,9$ 共 8 种选择，因此补集有 $8^4$ 个。这个例子提醒我们：容斥能做，不代表一定要把它完全展开；同一对象的更好描述往往能省掉计算。

本章小结与练习

容斥原理从“重复计数”出发。两集合是加单集合、减交集；三集合是加单集合、减完整的两两交、再加三重交；一般情形按交集层数交替加减。判断公式是否正确的最好办法，是追踪一个恰好属于 $t$ 个集合的对象，看它最后是否净贡献一次。

鸽巢原理从“容量不够”出发。基本形式断言物品多于盒子时必有重复；广义形式给出某盒至少达到 $\lceil N/k\rceil$ ，而保证某盒至少有 $r$ 个物品的临界数量是 $k(r-1)+1$ 。使用时要把物品、盒子和分配函数都说清。

组合证明与双计数从“同一对象”出发。等式两边不需要先做代数变形，只要分别数清同一批对象，并确认两边都不重不漏。求和常来自分类，乘积常来自连续选择，度数和常来自关联关系的两个方向。

练习 1：三集合调查

某年级 120 人中，70 人参加体育活动，58 人参加艺术活动，52 人参加科技活动；参加体育与艺术的有 30 人，参加体育与科技的有 26 人，参加艺术与科技的有 24 人，三项都参加的有 12 人。求至少参加一项、恰好参加两项、一项也不参加的人数。

练习 2：保证同余

至少任取多少个整数，才能保证其中有 5 个整数除以 7 的余数相同？

练习 3：标出子集的组合证明

用组合方法证明

\binom nr\binom rk=\binom nk\binom{n-k}{r-k}, \qquad 0\le k\le r\le n.

数同一批对象：从 $n$ 个对象中选出一个 $r$ 元集合，并在其中标出一个 $k$ 元子集。

左边先选 $r$ 元集合，再从其中选出被标出的 $k$ 个对象，得到 $\binom nr\binom rk$ 。右边先从全部 $n$ 个对象中选出被标出的 $k$ 个，再从剩余 $n-k$ 个对象中选 $r-k$ 个未标出的成员，得到 $\binom nk\binom{n-k}{r-k}$ 。两条路径生成的是同一种“带标出子集的 $r$ 元集合”，所以两边相等。

练习 4：错位排列

五个人把写有自己名字的卡片随机放入五个位置。问没有任何卡片回到同名位置的排列有多少个？

使用错位排列公式：

\begin{aligned} D_5 &=5!\left(1-1+\frac1{2!}-\frac1{3!}+\frac1{4!}-\frac1{5!}\right)\\ &=44. \end{aligned}

也可以按容斥逐层理解：从 $5!$ 个排列中减去指定一个位置固定的排列，加回指定两个位置固定的排列，如此交替修正到五个位置全部固定。

下一章会把计数结果装进生成函数的系数里，再把“有利结果数除以全部结果数”解释为离散概率。到那时，本章的两条线会同时回来：容斥会处理事件的重叠，组合论证会解释系数为什么满足那些看似神奇的恒等式。