计数与组合证明

把 7 个相同的任务名额分给三个有名字的小组，有多少种分配？先回答“什么算一种分配”，才能选公式。如果只记录各组拿到几个名额，结果是三元组 $(x_1,x_2,x_3)$；如果 7 个任务各有身份，记录每个任务交给谁，就换成了另一个计数问题。

离散数学地图列出了基本排列与组合公式。组合证明进一步解释这些数为什么相等、为什么要减去重叠，以及为什么某些安排根本不可能。

先定义对象和相等的含义

计数求的是有限集合 $S$ 的大小 $|S|$。写出集合时，要交代对象、限制，以及两个记录什么时候代表同一个结果。

• 序列记录位置，AB 与 BA 不同；集合只记录成员，两者都表示 $\{A,B\}$。
• 允许重复选择某个值，与把相同值的副本视为不可区分，是两个条件。
• 构造过程可能有多条路径通向同一个结果；数路径之前，要确定题目要的是否就是路径数。

例如，用 A、B 组成长度为 2 的序列，允许重复时，结果是 AA、AB、BA、BB。若只记录每个字母出现的次数，AB 与 BA 合并，得到三种结果。此时不能把序列总数除以一个固定倍数：AA 只有一种顺序，AB 却有两种。Berkeley CS70 的计数讲义强调，除法计数要求每个目标结果都有同样多的原像。

分步相乘，分类相加

若对象由 $k$ 步唯一构成，且每个合法前缀在第 $i$ 步都恰好有 $n_i$ 种选择，广义乘法原理（MIT 第 14.3 节）给出 $\prod_{i=1}^k n_i$。选择的具体内容可以依赖前面的选择；同一层的选择数量必须固定。用 3 个不同字母和 4 个不同数字各选一个，按“字母、数字”排列，共有 $3\times4=12$ 个序列。

数量随分支变化时，要分别计算再相加。若第一步选 A 后可接两个字符，选 B 后可接三个字符，总数是 $2+3=5$。

加法原理用于两两不相交的分类。若有限集合 $S_1,\ldots,S_k$ 两两不相交，则

$$\left|\bigcup_{i=1}^k S_i\right|=\sum_{i=1}^k|S_i|.$$

这个不相交条件见 MIT《Mathematics for Computer Science》第 14.2 节。允许前导零的两位和三位十进制字符串，按长度分成两类，共有 $10^2+10^3=1100$ 个。若分类是“含有 A”和“含有 B”，含有两者的字符串会被重复计算，需要修正重叠。

用双射和双重计数证明等式

双射把两个集合的元素一一对应：每个源元素有一个目标，每个目标恰好来自一个源元素。给出映射和逆映射，就能证明两个集合一样大。

在一个含 $n$ 个元素的固定集合中，把 $k$ 元子集映射到它的补集，得到 $(n-k)$ 元子集。再取一次补集便回到原子集，所以当 $0\le k\le n$ 时，

$$\binom nk=\binom n{n-k}.$$

例如，五个人中选两个人，和选出被留下的三个人一一对应，都是 10 种。

双重计数则用两种方法数同一个集合。设 $n\ge1$，$1\le k\le n$，结果是“一个 $k$ 人委员会，加上其中一位负责人”。先选委员会再选负责人，得到 $k\binom nk$；先选负责人，再从其余 $n-1$ 人中选 $k-1$ 人，得到 $n\binom{n-1}{k-1}$。因此

$$k\binom nk=n\binom{n-1}{k-1}.$$

八个人选三人委员会并指定负责人，两种算法都得到 $3\binom83=8\binom72=168$。这里被数的是带有负责人标记的委员会；只数委员会会漏掉每个委员会的三种负责人选择。

重复选择与不可区分的对象

分配相同名额：隔板法

回到开头的分配问题。名额相同，三个小组可区分，每组可以分到零个，也没有容量上限。需要数非负整数解

$$x_1+x_2+x_3=7.$$

用 7 个星号表示名额，2 个隔板分出三组；**|***|** 对应 $(2,3,2)$。隔板可以相邻，也可以在两端，分别表示中间小组或端点小组拿到零个。由三元组能唯一写出星号与隔板的串，从串也能唯一读回三元组。

因此只需在 9 个位置中选出 2 个隔板的位置，答案是 $\binom92=36$。一般地，把 $r\ge0$ 个相同对象分给 $b\ge1$ 个可区分的盒子，允许空盒且无容量上限，有 $\binom{r+b-1}{b-1}$ 种。CS70 讲义中“不计顺序的重复抽样”使用了同样的对应。

若每组至少分到一个，先给每组一个，再分剩下的 4 个，得到 $\binom62=15$。若对象各不相同，原题就有 $3^7=2187$ 种；若小组也不可区分，隔板的位置会多次表示同一种分配，需另建模型。

排列固定的重复值

AABC 中两个 A 不可区分。先给它们编号，四个不同对象有 $4!$ 种排列；抹去编号后，每个可见结果恰好对应 $2!$ 个带编号的排列，所以共有 $4!/2!=12$ 种。

一般地，$n$ 个值中各类的重数为 $m_1,\ldots,m_t$，满足 $\sum_i m_i=n$，不同序列的数量是

$$\frac{n!}{m_1!\cdots m_t!}.$$

MIT 第 14.6 节给出了这一规则。每个结果的带编号版本数量相同，正是能做除法的原因。如何在搜索时直接消除这些重复分支，见回溯生成排列。

重叠集合：容斥原理

MIT 第 14.9 节的容斥原理对有限集合的并集修正重叠。两个集合时，$|A\cup B|=|A|+|B|-|A\cap B|$。三个集合时，

$$\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}$$

属于三个集合的元素先被加了三次，又被减了三次，必须再加一次。对更多集合，继续按交集涉及的集合数量交替加减，直到最后一层。

完整例题：筛选 1–100 的整数

求从 1 到 100（含两端）中，不能被 2、3、5 中任何一个整除的整数个数。令 $U=\{1,\ldots,100\}$，$A,B,C$ 分别是其中能被 2、3、5 整除的数。

集合	判定条件	数量
$A$	2 的倍数	$\lfloor100/2\rfloor=50$
$B$	3 的倍数	$\lfloor100/3\rfloor=33$
$C$	5 的倍数	$\lfloor100/5\rfloor=20$
$A\cap B$	6 的倍数	16
$A\cap C$	10 的倍数	10
$B\cap C$	15 的倍数	6
$A\cap B\cap C$	30 的倍数	3

交集由相应除数的最小公倍数决定；只有两两互质时，最小公倍数才等于它们的乘积。因此

$$|A\cup B\cup C|=50+33+20-16-10-6+3=74.$$

这些是要排除的整数，答案是 $|U|-74=100-74=26$。下面用 Python 3 直接枚举集合：

U = set(range(1, 101))
A = {x for x in U if x % 2 == 0}
B = {x for x in U if x % 3 == 0}
C = {x for x in U if x % 5 == 0}
union_count = (len(A) + len(B) + len(C)
               - len(A & B) - len(A & C) - len(B & C)
               + len(A & B & C))
valid = U - (A | B | C)
assert union_count == len(A | B | C)
print(union_count, len(valid))
print(sorted(valid))

输出：

74 26
[1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97]

鸽巢原理与不可能性

鸽巢原理把对象放入有限个类别：若 $N$ 个对象各归入 $b\ge1$ 个盒子之一，总有一个盒子含有至少 $\lceil N/b\rceil$ 个对象。MIT 第 14.8 节将它表述为函数的性质：源集合比目标集合大，就不可能是单射。

例如，17 个任务交给 5 个执行器，必有一个执行器收到至少 4 个任务。若每个最多收到 3 个，总容量只有 $5\times3=15$，装不下 17 个。

同样，任意把所有 9 位二进制字符串映射为 8 位字符串的确定性函数，都会发生碰撞：输入有 $2^9=512$ 个，输出只有 $2^8=256$ 个。因此，它不可能在全部输入上都有唯一逆映射。证明保证至少有一对输入碰撞，但没有指出是哪一对，也没有给出寻找它们的成本。

搜索空间、输出下界与区分下界

计数可以估计搜索需要面对多少候选。三组分配的 36 种结果，可以用隔板法得到，也可以枚举三元组：

from itertools import product
from math import comb

allocations = [x for x in product(range(8), repeat=3) if sum(x) == 7]
assert len(allocations) == comb(9, 2)
print(len(allocations), allocations[:5])

输出：

36 [(0, 0, 7), (0, 1, 6), (0, 2, 5), (0, 3, 4), (0, 4, 3)]

这段代码检查了 $8^3=512$ 个三元组，才留下 36 个。候选数、合法结果数和实际运行成本要分别计算；剪枝会改变访问的节点数，处理一个节点也可能有额外成本。

如果要求显式输出 $M$ 个长度为 $\ell$ 的序列，并为每个序列写出全部元素，输出时间至少为 $\Omega(M\ell)$，按常数成本写入一个元素计算。把所有结果作为独立列表同时保留，空间也至少为 $\Omega(M\ell)$。例如，10 个不同值有 $10!=3628800$ 个排列，完整输出要写出 36288000 个元素。流式输出能减少同时保留的空间，但仍要完成这些写入；只求结果数量则是另一项任务。

另一种下界来自必须区分多少情况。若确定性算法只通过每次至多 $q\ge2$ 种结果的询问区分 $M\ge1$ 种情况，深度为 $h$ 的决策树至多有 $q^h$ 个叶子。因此 $h\ge\lceil\log_q M\rceil$。对任意不同键的比较排序，$M=n!$，比较不同键时 $q=2$；这就是 Open Data Structures 第 11.1.4 节的决策树论证。八个不同键的 $8!=40320$ 种相对次序，要求最坏情况下至少 16 次比较，因为 $2^{15}<40320\le2^{16}$。

输出下界数的是必须写出的内容，决策树下界数的是必须获得的区分信息。它们分别帮助判断“更快枚举所有结果”和“用更少询问作出决定”的可能性。排序算法地图说明了比较模型的适用范围，以及利用键的额外结构时为何可以换用其他排序方法。

我的阅读 · 打开过的笔记会记在当前浏览器里。