Lecture 16: Combinatorial Proofs（组合证明）
Lecture 16: Combinatorial Proofs（组合证明）
概述
上一讲（L14 计数）教会我们算数：给一个具体场景，用第一法则（乘法原理）、第二法则（有序除以重复倍数）、容斥原理把答案算出来。本讲要反过来做一件更有意思的事：证明关于计数的恒等式本身。
组合证明（combinatorial proof）的核心主张是：一个等式之所以成立，往往不是因为代数运算恰好凑上了，而是因为等式两边在数同一批东西。我们可以数两次（double counting），也可以在两批东西之间架一座桥（bijection）。这种证明的价值在于它不依赖任何代数技巧——你不需要知道 $\sum_k \binom{n}{k}^2$ 怎么化简，只要找到一个能把两边都解释清楚的故事。
本讲在课程中的位置很关键：它是 L14 计数与 L15 概率公理的自然延续（”均匀样本空间下，概率 = 计数 / 总数”），同时又是 L17 条件概率与 L18 独立性、L19 随机变量的论证工具——二项分布的 $\binom{n}{k}p^k(1-p)^{n-k}$、Vandermonde 恒等式在联合分布中的反复出现，都要靠本讲的技巧来解释和推导。
核心概念的直观解释
组合证明（Combinatorial Proof）
- 定义：组合证明是指不通过代数变形，而是通过给出所计数量的一种或两种组合解释（combinatorial interpretation），来建立恒等式 $L = R$ 的证明。形式上有两大范式：双计数（double counting）与双射（bijection）。
- 直观解释（”它是什么意思？”）：代数证明像是在验算收据上的加法；组合证明则像是在讲一个故事，然后说”这个故事从两个角度听，得到两个不同的数字，但故事本身只有一个，所以两个数字必然相等”。可以把等式理解成一句双关语：左边是一种读法，右边是另一种读法，说的是同一件事。
- 具体示例：$\binom{n}{k} = \binom{n}{n-k}$。代数上就是 $\frac{n!}{k!(n-k)!} = \frac{n!}{(n-k)!k!}$，两边长得一样，没什么可证。但组合解释是：从 $n$ 个人里选 $k$ 个人去开会，等价于从 $n$ 个人里选 $n-k$ 个人不去开会。同一个”选择”用两种说法描述，因此两种说法的个数相等。
双计数（Double Counting / Counting in Two Ways）
- 定义：设 $S$ 是某个有限集合。若能用两种互不相同的、各自无重无漏的方法分别数出 $\vert S\vert $，得到表达式 $E_1$ 与 $E_2$，则必定有 $E_1 = E_2$。这类证明中，两边数的是同一个集合 $S$。
- 直观解释（”它是什么意思？”）：想象一间教室，我们可以按行数（每行人数相加），也可以按列数（每列人数相加）。无论怎么数，教室里的人数是同一个人数。这就是”同一个量的两种记账方式”。
- 具体示例：数矩阵中”1”的个数。若矩阵第 $i$ 行有 $r_i$ 个 1，第 $j$ 列有 $c_j$ 个 1，则 $\sum_i r_i = \sum_j c_j$。这个平凡的事实正是握手引理的骨架（见后文）。
双射（Bijection）
- 定义：函数 $f: A \to B$ 称为双射（bijection），若它既单射（injective，一对一）（$a \ne a^{\prime} \Rightarrow f(a) \ne f(a^{\prime})$）又满射（surjective，映上）（$\forall b \in B, \exists a \in A, f(a) = b$）。此时 $\vert A\vert = \vert B\vert $。
- 直观解释（”它是什么意思？”）：双射就是完美配对。假设有两个班的同学要结对写信，规则是”每人只写一封、每人只收一封”。如果这个规则能公平地执行完毕，两个班的人数必定相同。单射保证没有两个人写给同一个人（不会重复占用），满射保证没有人收不到信（不会漏掉）。少检查任何一条，结论都不成立。
- 具体示例：把 $\{1,2,3\}$ 的子集与长度为 3 的 0/1 串配对：子集 $S \mapsto$ 向量 $(x_1,x_2,x_3)$，其中 $x_i = 1$ 当且仅当 $i \in S$。$\varnothing \leftrightarrow 000$，$\{1,3\} \leftrightarrow 101$。$8$ 个子集刚好配 $8$ 个位串，因为 $2^3 = 8$。
“要数的对象”（The Objects Being Counted）
- 定义：组合证明的成败，几乎完全取决于你把什么定义为被数的对象。所谓对象可以是一个集合、一个有序对、一个带标记的配置，甚至是一个”过程”。
- 直观解释（”它是什么意思？”）：这是组合证明最需要创造力、也最容易出错的一步。有时候恒等式右边看起来像一个莫名其妙的乘积 $n2^{n-1}$，直到你说出”我数的是（子集，子集中的某个元素）这样的 $n2^{n-1}$ 个对”，一切才豁然开朗。对象定义错了，后面的论证再流畅也是错的。
- 具体示例：恒等式 $\sum_{k=0}^{n} k\binom{n}{k} = n2^{n-1}$。如果试图把左边的 $k\binom{n}{k}$ 理解成”先选 $k$ 个元素，再从里面选一个”，那么左边的对象是”（$k$ 元子集，其中一个元素）”。右边 $n2^{n-1}$ 必须能被解释成同样的一批对——事实证明可以：先定那个特殊元素（$n$ 种），再把剩下 $n-1$ 个元素任意决定是否加入（$2^{n-1}$ 种）。同一个对象集合，两条构造路径。
均匀样本空间中的概率（Probability on a Uniform Sample Space）
- 定义：若样本空间 $\Omega$ 有限且每个样本点概率相同，则该概率空间称为均匀的（uniform），此时对任意事件 $A$，$\Pr[A] = \dfrac{\vert A\vert }{\vert \Omega\vert }$。
- 直观解释（”它是什么意思？”）：均匀空间里，”求概率”退化成了”数数再除一除”。这是 L15 反复强调的范式：均匀 + 计数 = 概率。组合证明在这里的用途是：它不用（也无法）算出 $\vert A\vert $ 的具体数字，却能证明两个概率相等，或把 $\Pr[A]$ 化成一个已知的计数表达式。
- 具体示例：抛 $n$ 枚公平硬币，恰好 $r$ 个正面。$\Omega$ 有 $2^n$ 个位串，每个概率 $2^{-n}$；事件”恰有 $r$ 个正面”就是”位串中恰有 $r$ 个 1”的集合，其大小是 $\binom{n}{r}$。所以 $\Pr[\text{恰 }r\text{ 个正面}] = \binom{n}{r}/2^n$。这个推导的全部工作在于计数，而不在于概率论。
组合恒等式（Combinatorial Identity）
- 定义：形如”两个含 $\binom{\cdot}{\cdot}$ 的表达式恒相等”的命题，如 $\sum_k \binom{n}{k} = 2^n$、$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$。
直观解释（”它是什么意思？”）：每个恒等式背后都藏着一个关于集合的等式。本讲的核心哲学可以浓缩成一句话：
等式两边的差 = 两个集合的差。
也就是说，若 $L = R$，则必定存在集合 $S_L, S_R$ 使 $L = \vert S_L\vert , R = \vert S_R\vert $，且 $S_L = S_R$（双计数情形）或 $\vert S_L\vert = \vert S_R\vert $（双射情形）。找不到这两个集合，就没有组合证明。
- 具体示例：$\sum_{k=0}^{n}\binom{n}{k} = 2^n$ 中，左边的集合是”全体子集按大小分组的并”，右边的集合是”全体 $n$ 位 0/1 串”，二者通过”子集 ↔ 特征向量”完美配对。
完整证明与推导（核心）
定理 16.1（对称性 / Symmetry）： 对任意整数 $0 \le k \le n$，
\[\binom{n}{k} = \binom{n}{n-k}.\]证明策略：双射证明。目标是建立从「$n$ 元集合的 $k$ 元子集全体」到「$n$ 元集合的 $(n-k)$ 元子集全体」的一个显式双射。最自然的候选是取补集（complementation）。之所以选这个策略，是因为代数证明在这里毫无信息量（两边写开后字面相同），而双射可以顺便告诉我们”为什么”。
逐步推导：
- 设 $S$ 是任意一个 $n$ 元集合，令 $\mathcal{A} = \{X \subseteq S : \vert X\vert = k\}$，$\mathcal{B} = \{Y \subseteq S : \vert Y\vert = n-k\}$。由 L14 的定义，$\vert \mathcal{A}\vert = \binom{n}{k}$，$\vert \mathcal{B}\vert = \binom{n}{n-k}$。我们只需证明 $\vert \mathcal{A}\vert = \vert \mathcal{B}\vert $。
- 定义映射 $f : \mathcal{A} \to \mathcal{B}$ 为 $f(X) = S \setminus X$（取补集）。
- 验证 $f$ 确实落在 $\mathcal{B}$ 中：若 $\vert X\vert = k$ 且 $\vert S\vert = n$，则 $\vert S \setminus X\vert = n - k$，故 $f(X) \in \mathcal{B}$。映射良定义。
- 验证 $f$ 单射：设 $f(X_1) = f(X_2)$，即 $S \setminus X_1 = S \setminus X_2$。对两边同时在 $S$ 中取补集，由”补集的补集是自身”（$S \setminus (S \setminus X) = X$）得 $X_1 = X_2$。故 $f$ 单射。
- 验证 $f$ 满射：任取 $Y \in \mathcal{B}$，取 $X = S \setminus Y$。因为 $\vert Y\vert = n-k$，所以 $\vert X\vert = k$，即 $X \in \mathcal{A}$；且 $f(X) = S \setminus (S \setminus Y) = Y$。故 $f$ 满射。
- 由 4、5，$f$ 是双射，于是 $\vert \mathcal{A}\vert = \vert \mathcal{B}\vert $，即 $\binom{n}{k} = \binom{n}{n-k}$。$\blacksquare$
【证明机制解说】：这个证明的”灵光一现”是把”选 $k$ 个人”重新描述为”把 $n-k$ 个人留在外面”。计数上这两种描述给出不同的表达式，但描述的是同一个选择行为。注意单射的证明用到了一个隐藏的代数事实：取补操作是自逆的（an involution），即 $f \circ f = \mathrm{id}$。凡是一个自逆的映射，必然是双射——这是组合证明中一个可反复使用的”快捷通道”。以后遇到 $f^{-1} = f$ 的情形，单射与满射可以一次证完。
反例（如果适用）：若把双射改成”从 $X$ 中去掉最小元素”，即 $g(X) = X \setminus \{\min X\}$，映射 $\mathcal{A} \to \mathcal{B}$ 就不成立。例如 $n = 3, k = 2$：$\mathcal{A} = \{\{1,2\},\{1,3\},\{2,3\}\}$，$g$ 的像分别是 $\{2\},\{3\},\{3\}$。像集只有 2 个元素，而定义域有 3 个元素，$g$ 不是单射，更不是满射（$\{1\}$ 不在像中）。这说明”我构造了一个映射”离”我构造了一个双射”还差着单射与满射两步验证。
定理 16.2（Pascal 法则 / Pascal’s Rule）： 对任意 $1 \le k \le n-1$，
\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.\]证明策略：双计数。左边直接数「$n$ 元集合的 $k$ 元子集」。右边则按某个特定元素是否被选中来分类，把同一批子集拆成两类分别数。之所以选双计数而非双射，是因为等式右边是”和”的形式——和式天然对应于分类（分情形），这是判断该用哪种范式的一条经验法则。
逐步推导：
- 设 $S$ 是 $n$ 元集合，特别地固定一个元素 $a \in S$。令 $\mathcal{A} = \{X \subseteq S : \vert X\vert = k\}$，则 $\vert \mathcal{A}\vert = \binom{n}{k}$，这就是等式的左边。
- 按 $a$ 是否属于 $X$ 分类。这两类互不相交（$a$ 要么在 $X$ 里要么不在），且合起来覆盖全部 $\mathcal{A}$（划分）。因此 \(\vert \mathcal{A}\vert = \vert \{X \in \mathcal{A} : a \in X\}\vert + \vert \{X \in \mathcal{A} : a \notin X\}\vert .\)
- 第一类（含 $a$）：$X$ 含有 $a$，还需要从 $S \setminus \{a\}$ 这个 $n-1$ 元集合中再选 $k-1$ 个元素。由 L14 第二法则，数目为 $\binom{n-1}{k-1}$。
- 第二类（不含 $a$）：$X$ 不含 $a$，故 $X$ 的 $k$ 个元素全部取自 $S \setminus \{a\}$。数目为 $\binom{n-1}{k}$。
- 相加即得 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$。$\blacksquare$
【证明机制解说】：Pascal 法则就是杨辉三角（Pascal’s triangle）的生成规则：每个数等于它左肩与右肩两数之和。组合证明揭示了这条规则的”物理意义”——它说的是”任何一次选择，都可以按’某个特定对象是否入选’剖成两半“。同一技巧可以递归使用，就得到了二项式系数的全部递推结构。注意这个证明必须避免用代数展开（$\frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!} = \cdots$），那样做虽然正确，却丢掉了本讲想让你掌握的思想。
反例（如果适用）：分类必须是划分。若把”$X$ 含 $a$”与”$X$ 含 $b$”（$b \ne a$）当作两类，则它们会重叠（$X$ 可以同时含 $a,b$），相加就重复计数了。正确的划分只能靠”是/否”这样的二分。
定理 16.3（子集总数）： 对任意 $n \ge 0$，
\[\sum_{k=0}^{n} \binom{n}{k} = 2^n.\]证明策略：先用双计数给出核心解释，再顺带给出双射视角（子集 ↔ 0/1 串）。这里要特别注意：这个恒等式也可以由二项式定理取 $a=b=1$ 秒得（见下文定理 16.6），但代数捷径不等于组合解释——本定理的价值恰在于把 $2^n$ 从一个”乘出来的数”变成”数出来的数”。
逐步推导：
- 左边在数什么：设 $S$ 为 $n$ 元集合。$\binom{n}{k}$ 是 $S$ 的 $k$ 元子集个数。这些子集按大小 $k = 0,1,\dots,n$ 分类后相加，恰好数出 $S$ 的全体子集（任意大小）。记 $\mathcal{P}(S) = \{X : X \subseteq S\}$，则 \(\sum_{k=0}^{n}\binom{n}{k} = \vert \mathcal{P}(S)\vert .\)
- 右边在数什么：构造映射 $\varphi : \mathcal{P}(S) \to \{0,1\}^n$。先把 $S$ 的元素任意排成 $s_1,\dots,s_n$，定义 \(\varphi(X) = (x_1,\dots,x_n), \quad x_i = \begin{cases} 1, & s_i \in X,\\ 0, & s_i \notin X.\end{cases}\) 称为 $X$ 的特征向量（characteristic vector / indicator vector）。
- $\varphi$ 单射：假设 $\varphi(X) = \varphi(X^{\prime})$。对每个 $i$，$s_i \in X \iff x_i = 1 \iff s_i \in X^{\prime}$。故 $X$ 与 $X^{\prime}$ 含完全相同的元素，$X = X^{\prime}$。
- $\varphi$ 满射：任给 $(x_1,\dots,x_n) \in \{0,1\}^n$，令 $X = \{s_i : x_i = 1\}$。显然 $X \subseteq S$ 且 $\varphi(X) = (x_1,\dots,x_n)$。
- 由 3、4，$\varphi$ 是双射，因此 $\vert \mathcal{P}(S)\vert = \vert \{0,1\}^n\vert $。
- 数位串：长度为 $n$ 的 0/1 串，每一位有 2 种选择，且每一位的选择相互独立（第 $i$ 位的可选值不因前 $i-1$ 位的取值而改变——这一点正是 L14 第一法则的适用前提，必须明说）。由乘法原理，$\vert \{0,1\}^n\vert = 2^n$。
- 合并 1 与 6，得 $\sum_{k=0}^{n}\binom{n}{k} = 2^n$。$\blacksquare$
【证明机制解说】：本证明的关键动作是把”集合”翻译成”字符串”。集合这种对象不好直接乘，但字符串的每一位天然对应一次二选一，乘法原理立刻可用。这个”翻译”后来反复出现：L14 里水果沙拉的多重集被翻成 0/1 串；L19 里二项分布被翻成”正面位置的选择”；L21 里随机变量独立性被翻成”联合分布等于边缘分布之积”。遇到难数的对象，先问：它能编码成什么串？
算例验证（$n=3$）：全体子集共 $2^3 = 8$ 个。按大小分组：
子集 特征向量 大小 k
----------------- ---------- ------
∅ 0 0 0 0
{1} 1 0 0 1
{2} 0 1 0 1
{3} 0 0 1 1
{1,2} 1 1 0 2
{1,3} 1 0 1 2
{2,3} 0 1 1 2
{1,2,3} 1 1 1 3
----------------- ---------- ------
|{k 元子集}|: C(3,0)=1, C(3,1)=3, C(3,2)=3, C(3,3)=1
左 边 求 和: 1 + 3 + 3 + 1 = 8
右 边 计 数: 2^3 = 8 ✓
定理 16.4（Vandermonde 恒等式 / Vandermonde’s Identity）： 对任意非负整数 $m, n, r$，
\[\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}.\]特别地，取 $m = n = r$，得到最漂亮的特例：
\[\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}.\]证明策略：双计数。这是全讲最值得反复品味的例子。想法是用一个两类人群（男生 / 女生）的模型：从 $n$ 个男生、$n$ 个女生中选 $n$ 个人。一种数法是”直接数”；另一种数法是”按选中了几个男生分类“。之所以能这样做，是因为”选 $n$ 个人”这件事既可以整体看成一次选择，也可以分解成”男生部分 + 女生部分”两步——分解的维度就是求和指标 $k$。
逐步推导（先证特例，再推广）：
- 设男生集合 $M$ 满足 $\vert M\vert = n$，女生集合 $W$ 满足 $\vert W\vert = n$，且 $M \cap W = \varnothing$。总人数 $2n$。设 $\mathcal{S}$ 为从 $M \cup W$ 中选 $n$ 个人（不分性别）的全体方案。
- 数法一（直接数）：$\vert \mathcal{S}\vert = \binom{2n}{n}$。这就是等式右边。
- 数法二（按性别分类）：对每个方案，记录其中男生的个数 $k$。可能的 $k$ 取值是 $0,1,\dots,n$（因为一共只选 $n$ 个人，男生不可能超过 $n$ 个）。这些类别互不相交（一个方案的男生数唯一），且并起来是 $\mathcal{S}$（任何方案都有确定的男生数），所以构成一个划分。
- 第 $k$ 类怎么数：先选 $k$ 个男生（$\binom{n}{k}$ 种），再选 $n-k$ 个女生（$\binom{n}{n-k}$ 种）。由于男生部分与女生部分的选择互不影响（两个集合不相交，选谁做男生和选谁做女生是彼此独立的决定），乘法原理适用，第 $k$ 类有 $\binom{n}{k}\binom{n}{n-k}$ 个方案。
- 求和：$\vert \mathcal{S}\vert = \sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k}$。
- 由定理 16.1（对称性），$\binom{n}{n-k} = \binom{n}{k}$，于是 $\vert \mathcal{S}\vert = \sum_{k=0}^{n}\binom{n}{k}^{2}$。
- 两种数法数的是同一个 $\mathcal{S}$，故 $\sum_{k=0}^{n}\binom{n}{k}^{2} = \binom{2n}{n}$。$\blacksquare$
- 推广到一般 Vandermonde：只需把男生数改成 $m$、女生数改成 $n$、要选的人数改成 $r$。同样的论证一字不改给出 $\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$。（注意 $k$ 的上限由 $\binom{m}{k} = 0$（当 $k>m$）与 $\binom{n}{r-k} = 0$（当 $r-k>n$）自动处理，写成 $\sum_{k=0}^{r}$ 或 $\sum_{k}$ 都对。）$\blacksquare$
【证明机制解说】：这是双计数最经典的样板，值得把三个动作背下来：
- 动作一：把等式右边 $\binom{m+n}{r}$ 认作”从一个 $m+n$ 元的合并池里选 $r$ 个”。
- 动作二：把左边每一项 $\binom{m}{k}\binom{n}{r-k}$ 认作”从两个子池里分别选 $k$ 个和 $r-k$ 个”。
- 动作三：求和指标 $k$ 就是”把合并池拆成子池的方式“。左边按 $k$ 分类穷尽了所有可能，右边则不在乎 $k$ 是多少。
换句话说：左边是”先分性别再选人”，右边是”先选人不问性别”。 结果当然一样。
反例（如果适用）：注意 $\sum_k \binom{n}{k}^2 = \binom{2n}{n}$ 不能随手推广到三次方。例如有人会猜 $\sum_{k}\binom{n}{k}^3 = \binom{3n}{n}$，但脚本验算给出：
| $n$ | $\sum_k \binom{n}{k}^3$ | $\binom{3n}{n}$ | 相等？ |
|---|---|---|---|
| 1 | 2 | 3 | 否 |
| 2 | 10 | 15 | 否 |
| 3 | 56 | 84 | 否 |
| 4 | 346 | 495 | 否 |
为什么不能推广？因为在双计数的故事里，$\binom{3n}{n}$ 要求把 $3n$ 个人分成 3 组，而左边的 $\binom{n}{k}^3$ 只对应”三组各选 $k$ 个”，三组选出的总数是 $3k$ 而不是固定的 $n$——左右两边数的根本不是同一批对象。这就是”两个集合的差“没对上的典型症状。真正对的三次方版本（Dixon 恒等式等）形式要复杂得多，远非本讲范围。
逐项算例（$n = 4$）：
| $k$ | $\binom{4}{k}$ | $\binom{4}{k}^2$ |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 4 | 16 |
| 2 | 6 | 36 |
| 3 | 4 | 16 |
| 4 | 1 | 1 |
| 和 | 70 |
而 $\binom{8}{4} = 70$。相合。$\checkmark$
一般式的逐项算例（$m=3, n=4, r=4$）：
| $k$ | $\binom{3}{k}$ | $\binom{4}{4-k}$ | 乘积 |
|---|---|---|---|
| 0 | 1 | $\binom{4}{4}=1$ | 1 |
| 1 | 3 | $\binom{4}{3}=4$ | 12 |
| 2 | 3 | $\binom{4}{2}=6$ | 18 |
| 3 | 1 | $\binom{4}{1}=4$ | 4 |
| 4 | 0 | $\binom{4}{0}=1$ | 0 |
| 和 | 35 |
而 $\binom{3+4}{4} = \binom{7}{4} = 35$。相合。$\checkmark$
ASCII 分类示意（双计数的”两种数法”）：
S = 从 4 男 + 4 女 中选 4 人 (n = 4, 共 8 人)
数法一（不分性别，直接数）: C(8,4) = 70
┌──────────────────────────────────────────────────────┐
│ 从 {男1 男2 男3 男4 女1 女2 女3 女4} 中任取 4 人 │
└──────────────────────────────────────────────────────┘
‖ 同一个集合 S ‖
┌──────────────────────────────────────────────────────┐
│ 数法二（按"选中几个男生" k 分类，各类互不相交） │
│ │
│ k = 0 : 选 0 男 + 4 女 → C(4,0)·C(4,4) = 1·1 = 1│
│ k = 1 : 选 1 男 + 3 女 → C(4,1)·C(4,3) = 4·4 =16│
│ k = 2 : 选 2 男 + 2 女 → C(4,2)·C(4,2) = 6·6 =36│
│ k = 3 : 选 3 男 + 1 女 → C(4,3)·C(4,1) = 4·4 =16│
│ k = 4 : 选 4 男 + 0 女 → C(4,4)·C(4,0) = 1·1 = 1│
│ │
│ 合计 = 1 + 16 + 36 + 16 + 1 = 70 │
└──────────────────────────────────────────────────────┘
∴ sum_k C(4,k)^2 = C(8,4) = 70 ✓
定理 16.5（子集元素总数）： 对任意 $n \ge 1$，
\[\sum_{k=0}^{n} k\binom{n}{k} = n\,2^{n-1}.\]证明策略：双计数。难点不在计算，而在定义被数的对象。左边的求和指标 $k$ 提示我们：对象里必须携带一个”大小为 $k$ 的子集”和一个介于 $1$ 与 $k$ 之间的东西。最自然的读法是”（子集，子集里的一个元素）”这样的有序对。右边 $n2^{n-1}$ 则要求另一种构造同样这批对的路径。这是”创造力定义对象”的最典型案例。
逐步推导：
- 定义对象集合：令 \(T = \{(X, x) : X \subseteq S,\ x \in X\},\) 其中 $S$ 是固定的 $n$ 元集合。也就是说，$T$ 的元素是”一个子集 $X$，外加 $X$ 中指定的一个元素 $x$“。注意 $(X,x)$ 是有序对：$X$ 相同而 $x$ 不同时，是不同的对象。
- 数法一（按子集大小分类）：对固定的 $k$，满足 $\vert X\vert = k$ 的子集有 $\binom{n}{k}$ 个；对每个这样的 $X$，元素 $x$ 有 $k$ 种选法。于是这一类的对象数是 $k\binom{n}{k}$。对 $k = 0,1,\dots,n$ 求和（这些类互不相交，因为 $\vert X\vert $ 唯一）： \(\vert T\vert = \sum_{k=0}^{n} k\binom{n}{k}.\)
- 数法二（先挑特殊元素）：反着来。先定 $x$：$x$ 可以是 $S$ 中任意一个元素，共 $n$ 种选法。再定 $X$：$X$ 必须包含 $x$，而 $S$ 中剩下的 $n-1$ 个元素各自独立地决定”加入 $X$”或”不加入 $X$”——每个元素 2 种选择，共 $2^{n-1}$ 种。由乘法原理， \(\vert T\vert = n \cdot 2^{n-1}.\)
- 两种数法数同一个 $T$，故 $\sum_{k=0}^{n}k\binom{n}{k} = n2^{n-1}$。$\blacksquare$
【证明机制解说】：这个证明最有教育意义的地方是它没有做任何计算——没有化简阶乘，没有配对技巧，只有两次”讲故事”。特别是数法二的顺序反转：左边是”先选大集合再选小元素”，右边是”先选小元素再决定大集合”。交换两个决定的先后次序，往往就是双计数证明的整个内容。 请把这个模式记牢：凡是等式出现”$\binom{n}{k}$ 乘以 $k$”（或除以 $k$ 再乘回来），都可以试试”（集合，其中元素）”这种带标记的对象。
逐项算例（$n = 4$）：
| $k$ | $k\binom{4}{k}$ |
|---|---|
| 0 | 0 |
| 1 | 4 |
| 2 | 12 |
| 3 | 12 |
| 4 | 4 |
| 和 | 32 |
而 $4 \cdot 2^{4-1} = 4 \cdot 8 = 32$。相合。$\checkmark$ 另一个直观校验：$\vert T\vert $ 也等于”所有子集的大小之和”。$n = 4$ 时子集大小之和为 $0\cdot1 + 1\cdot4 + 2\cdot6 + 3\cdot4 + 4\cdot1 = 0+4+12+12+4 = 32$；用对称性看，$2^4 = 16$ 个子集的平均大小是 $2$，$16 \times 2 = 32$。一致。
反例（如果适用）：若误以为 $\sum_k k\binom{n}{k} = n2^{n}$（把指数写成 $n$ 而非 $n-1$），则 $n=3$ 时左边 $= 0+3+6+3 = 12$，右边 $= 3\cdot 8 = 24$，不成立。错误根源是数法二里”剩下的 $n-1$ 个元素”被误当成”剩下的 $n$ 个元素”；因为 $x$ 已经确定在 $X$ 里，它对 $X$ 的其余部分不再有自由度。这类”指数该是 $n$ 还是 $n-1$”的混淆在 CS70 的计数题中极为常见。
定理 16.6（二项式定理 / Binomial Theorem）： 对任意 $n \in \mathbb{N}$，
\[(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^k b^{n-k}.\]证明策略：双计数（把展开过程当作一次计数过程）。注意这里的”集合”是展开式中出现的 $2^n$ 个项（带位置标记）。这是一个把代数对象”组合化”的示范：展开式不是一个符号游戏，而是在数”从 $n$ 个括号里各取一个字母”的方案数。
逐步推导：
- 把 $(a+b)^n$ 写成 $n$ 个因子的乘积 $f_1 f_2 \cdots f_n$，其中每个 $f_i = (a+b)$。给因子编号 $1,2,\dots,n$——这个编号是证明的关键，它让”哪个 $a$ 来自哪个括号”变得可区分。
- 用分配律展开：每一轮乘法都从当前因子里挑一个字母（$a$ 或 $b$）出来。因为每个 $f_i$ 有 2 种取法，且第 $i$ 个因子的取法不因前 $i-1$ 个因子的取法而改变（每个 $f_i$ 永远是 $(a+b)$，内容不变），由乘法原理，展开式共有 $2^n$ 个带位置标记的乘积项。
- 在这 $2^n$ 个项中，按”挑了多少个 $a$“来分类。设挑了 $k$ 个 $a$、$n-k$ 个 $b$，则由幂的乘法法则，这一项的值为 $a^k b^{n-k}$。所以每个这样的项都贡献一个 $a^kb^{n-k}$。
- 数一数有多少项落入”$k$ 个 $a$”这一类：这等价于从 $n$ 个编号因子 $\{1,\dots,n\}$ 中选出哪 $k$ 个出 $a$；一旦选定，其余因子全部出 $b$。选择方案数是 $\binom{n}{k}$。（这里没有重复也没有遗漏：每个方案唯一决定一个项，每个项也唯一决定一个方案，这是一个双射。）
- 因此 $a^kb^{n-k}$ 在展开式中（合并同类项后）恰好出现 $\binom{n}{k}$ 次，系数即为 $\binom{n}{k}$。
- 对所有 $k = 0,\dots,n$ 求和：$(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k}$。$\blacksquare$
【证明机制解说】：步骤 1 的”给因子编号”看似多余，实则不可或缺。若不给因子编号，$(a+b)^2$ 展开成 $a^2, ab, ba, b^2$ 就无法区分 $ab$ 与 $ba$——实际上是先把它们当不同项（$4$ 个），再按指数分类合并（$ab$ 与 $ba$ 合成 $2ab$，系数 2，即 $\binom{2}{1}$）。“先数带标记的，再按等价类归并” 是 L14 第二法则的思想，在这里以一个更精致的形式重现。
算例： $(a+b)^3 = \binom{3}{0}a^0b^3 + \binom{3}{1}ab^2 + \binom{3}{2}a^2b + \binom{3}{3}a^3 = b^3 + 3ab^2 + 3a^2b + a^3$。系数 $1,3,3,1$ 正是杨辉三角第 3 行。$(a+b)^4$ 系数为 $1,4,6,4,1$（由 Pascal 法则从上一行得到：$1;\ 1+3,\ 3+3,\ 3+1;\ 1$）。
推论（交替和为零 / Corollary 10.1）： $\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0$（$n \ge 1$）。
代数证明：在定理 16.6 中取 $a = -1, b = 1$，得 $(1-1)^n = 0 = \sum_{k=0}^{n}\binom{n}{k}(-1)^k \cdot 1^{n-k}$。$\blacksquare$
组合证明：设 $S$ 为 $n$ 元集合。考虑用两种方法数 $S$ 的奇数元子集个数与偶数元子集个数之差。
- 形式上，令 $E = \#\{\text{偶数元子集}\}$，$O = \#\{\text{奇数元子集}\}$。则 $E - O = \sum_k (-1)^k\binom{n}{k}$（$k$ 为偶数时 $(-1)^k=+1$，奇数时 $-1$）。故恒等式等价于 $E = O$。
- 构造双射：固定元素 $s_n \in S$，定义 $\sigma(X) = X \triangle \{s_n\}$（对称差，即”$s_n$ 在则删去，不在则加入”）。这个操作把子集大小改变 $1$（$\vert X\vert $ 增减 1），因此它在奇偶性之间来回切换。
- $\sigma$ 是自逆的：$\sigma(\sigma(X)) = X$（对同一个元素做两次”切换”等于没做），所以 $\sigma$ 是双射。
- 由于 $\sigma$ 把偶数元子集一一配给奇数元子集，$E = O$，故 $E - O = 0$。$\blacksquare$
【机制解说】：这个证明的巧妙之处在于避免了对 $n$ 的奇偶分类讨论。注意 $\sigma$ 会给 $\varnothing$ 配到 $\{s_n\}$（大小 0 ↔ 1），给 $\{s_n\}$ 配回 $\varnothing$，完美闭环。$n=1$ 时：$E = 1$（$\varnothing$），$O = 1$（$\{s_1\}$），差为 0。$n=3$ 时：$E = \binom30+\binom32 = 1+3 = 4$，$O = \binom31+\binom33 = 3+1 = 4$，差为 0。$\checkmark$ 注意 $n=0$ 时 $\sum_k(-1)^k\binom{0}{k} = 1 \ne 0$，所以推论要求 $n \ge 1$——条件不能省。
定理 16.7（曲棍球棒恒等式 / Hockey-stick Identity）： 对任意 $0 \le k \le n-1$，
\[\binom{n}{k+1} = \binom{k}{k} + \binom{k+1}{k} + \cdots + \binom{n-1}{k} = \sum_{i=k}^{n-1}\binom{i}{k}.\]证明策略：双计数。左边数「$n$ 元集合 $S = \{1,\dots,n\}$ 的 $(k+1)$ 元子集」。右边则换一个构造过程：不直接说”我要选哪些”，而是先决定”选出的集合中编号最小的元素是谁”，再补全其余元素。这个”按最小元素分类”是组合证明里的一把常用钥匙。
逐步推导：
- 令 $\mathcal{A} = \{X \subseteq \{1,\dots,n\} : \vert X\vert = k+1\}$，则 $\vert \mathcal{A}\vert = \binom{n}{k+1}$（左边）。
- 对每个 $X \in \mathcal{A}$，它有一个最小的编号元素 $\min X$。不同的 $X$ 可能共享同一个最小元，但每个 $X$ 的最小元唯一，因此”按 $\min X$ 分类”是一个划分。
- $\min X$ 能取哪些值？ 若令 $j = \min X$，则 $X$ 中剩下 $k$ 个元素都必须严格大于 $j$（因为 $j$ 是最小的），所以必须 $n - j \ge k$，即 $j \le n-k$。也就是说 $j \in \{1,2,\dots,n-k\}$。这个上限 $n-k$（而不是 $n$）绝不能漏掉——它正是”还要留出 $k$ 个更大的元素”这一约束的体现。
- 若 $\min X = j$，有多少个这样的 $X$？ 剩下 $k$ 个元素必须从 $\{j+1, j+2, \dots, n\}$ 中选，该集合有 $n-j$ 个元素，故有 $\binom{n-j}{k}$ 个方案。
- 换元整理：令 $i = n - j$。当 $j$ 从 $1$ 递增到 $n-k$ 时，$i$ 从 $n-1$ 递减到 $k$。于是 \(\vert \mathcal{A}\vert = \sum_{j=1}^{n-k}\binom{n-j}{k} = \sum_{i=n-1}^{k}\binom{i}{k} = \sum_{i=k}^{n-1}\binom{i}{k}.\) 这正是恒等式右边。$\blacksquare$
- 另一种同样漂亮的”最大元素”版本：也可以按最大元素 $\max X$ 分类。若 $\max X = i$（此时 $i$ 至少为 $k+1$，因为还需 $k$ 个更小的元素），其余 $k$ 个元素从 $\{1,\dots,i-1\}$ 的 $i-1$ 元集合中选，方案数 $\binom{i-1}{k}$；令 $t = i-1$ 得 $\sum_{t=k}^{n-1}\binom{t}{k}$，与步骤 5 完全一致，且这次换元是”顺向”的、更不容易搞错。两条路径殊途同归。推荐用最大元素版本，它的上下限天然对齐。
【证明机制解说】：这个恒等式得名于它在杨辉三角上的形状——沿对角线求和，和为拐角处那个数，像一根曲棍球棒：
杨辉三角（行 n，列 k） 曲棍球棒: sum_{i=k}^{n-1} C(i,k) = C(n,k+1)
k=0 1 2 3 4 5
n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
n=5 1 5 10 10 5 1
n=6 1 6 15 20 15 6 1
取 k = 2 的竖列: C(2,2)=1, C(3,2)=3, C(4,2)=6, C(5,2)=10, C(6,2)=15
沿此列从上往下累加 (i = 2..6):
1
1 + 3 = 4
1 + 3 + 6 = 10
1+3+6+10 = 20
1+3+6+10+15 = 35
这些和 4, 10, 20, 35 落在竖列右边一列:
C(4,3)=4, C(5,3)=10, C(6,3)=20, C(7,3)=35 ✓
∴ sum_{i=2}^{6} C(i,2) = C(7,3) = 35
算例（$n=7, k=2$）：$\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2}+\binom{6}{2} = 1+3+6+10+15 = 35$，而 $\binom{7}{3} = 35$。相合。$\checkmark$
一般性的直接校验（脚本验证结果）：
| $n$ | $k$ | $\sum_{i=k}^{n-1}\binom{i}{k}$ | $\binom{n}{k+1}$ |
|---|---|---|---|
| 5 | 1 | $1+2+3+4 = 10$ | $\binom{5}{2} = 10$ |
| 6 | 2 | $1+3+6+10 = 20$ | $\binom{6}{3} = 20$ |
| 7 | 3 | $1+4+10+20 = 35$ | $\binom{7}{4} = 35$ |
| 4 | 2 | $1+3 = 4$ | $\binom{4}{3} = 4$ |
四行全部相合。$\checkmark$（核算时把 $i$ 的上限 $n-1$ 用足；中间列最容易漏掉最后一项。）
反例（如果适用）：曲棍球棒恒等式的求和必须从 $i = k$ 开始。若误写成从 $i=1$ 开始，则当 $k \ge 2$ 时会引入一堆 $\binom{i}{k} = 0$（不存在的组合数）或错误项。例如 $k=2, n=7$：从 $i=1$ 起算会得到 $\binom12 + \binom22 + \binom32 + \cdots$，其中 $\binom12$ 按惯例取 $0$ 尚可，但若误按 $\binom12 = 1$（把”从 1 个东西里选 2 个”算成 1）就会得到 $36 \ne 35$。组合数的边界约定 $\binom{n}{k} = 0$（$k>n$ 或 $k<0$）在组合证明中必须严格遵守。
定理 16.8（握手引理，组合证明视角 / Handshake Lemma）： 对任意有限无向图 $G = (V,E)$，
\[2\vert E\vert = \sum_{v \in V} \deg(v).\]其中 $\deg(v)$ 是与 $v$ 关联的边数。
证明策略：双计数。这不是一个恒等式的”计算”，而是本讲哲学在图论领域的直接移植。被数的对象是（顶点，与该顶点关联的边）这样的有序对集合 $T$。之所以选双计数，是因为这两边本质上就是”按行数 vs 按列数”的关系，代数证明反而绕远。
逐步推导：
- 定义对象集合 \(T = \{(v, e) : v \in V,\ e \in E,\ v \text{ 是 } e \text{ 的一个端点}\}.\) 即”一条边和一个碰在它上面的顶点”组成的对。注意每条边有恰好 2 个端点（无向图，不含自环；含自环时端点需要按重数计），因此 $T$ 的每个元素都可以形象地理解为”边在某个端点处的’一头’“。
- 数法一（按边分组）：每条边 $e = \{u,v\}$ 贡献两个对：$(u,e)$ 与 $(v,e)$。因此 $\vert T\vert = 2\vert E\vert $。
- 数法二（按顶点分组）：顶点 $v$ 参与的边数恰好是它的度数 $\deg(v)$，因此顶点 $v$ 贡献 $\deg(v)$ 个对，$\vert T\vert = \sum_{v}\deg(v)$。
- 两种数法数同一个 $T$，故 $2\vert E\vert = \sum_v \deg(v)$。$\blacksquare$
【证明机制解说】：这个证明告诉你组合证明不只是组合数学的专利。只要你能把某个量写成”一个集合的大小”，并找到两种数法，无论对象是子集、是排列、是图的边，方法都通用。事实上，定理 16.5 的证明与握手引理在结构上完全同构：那里的 $T$ 是”（子集，其中元素）”，这里的 $T$ 是”（顶点，关联边）”；那里按子集大小分类等价于这里按顶点分类。认出”同构的证明骨架”是提高数学成熟度的关键一步。
推论： 任何有限无向图中，奇度顶点的个数必为偶数。
- 证明：$\sum_v \deg(v) = 2\vert E\vert $ 是偶数。设奇度顶点集为 $V_{\text{odd}}$，则 $\sum_{v \in V_{\text{odd}}}\deg(v) = 2\vert E\vert - \sum_{v \notin V_{\text{odd}}}\deg(v)$。右边两项都是偶数（$2\vert E\vert $ 显然；偶度顶点的度数和是偶数之和，仍为偶数），所以左边是偶数。而左边是 $\vert V_{\text{odd}}\vert $ 个奇数之和，奇数个奇数之和为奇数，偶数个奇数之和为偶数。故 $\vert V_{\text{odd}}\vert $ 必为偶数。$\blacksquare$
- 具体示例：一个三角形（$K_3$）每个顶点度数为 2（偶数），奇度顶点数 0。一条路径 $1-2-3$ 的度数为 $1,2,1$，奇度顶点是 $\{1,3\}$，共 2 个（偶数）。能否画出一个恰有 3 个奇度顶点的图？ 不能——这正是推论的内容。这直接解释了为什么”一笔画（欧拉路径）”问题中，起终点必须成对出现。
与经典问题的联系
一、均匀样本空间 + 计数 = 概率
L15 已经确立了这个范式：若 $\Omega$ 有限且均匀，则 $\Pr[A] = \vert A\vert /\vert \Omega\vert $。本讲的组合论证在此处提供了不用暴力枚举的推导力量。核心工具是下面这个由定理 16.6 直接得到的结论（官方 Note 13 的推导完全依赖计数）。
命题（二项分布的组合推导）：抛一枚正面概率为 $p$ 的硬币 $n$ 次，恰好得到 $r$ 个正面的概率为 \(\Pr[\text{恰 } r \text{ 个正面}] = \binom{n}{r}p^{r}(1-p)^{n-r}.\)
推导（纯组合）：
- 样本空间 $\Omega$ 是全部长度 $n$ 的 H/T 序列，$\vert \Omega\vert = 2^n$（定理 16.3 的位串计数）。
- 事件”恰有 $r$ 个正面”就是”序列中恰有 $r$ 个位置是 H”。选择哪些位置是 H 的方案数就是 $\binom{n}{r}$（定理 16.6 步骤 4 的同一计数）。所以该事件含 $\binom{n}{r}$ 个样本点。
- 每个”恰有 $r$ 个正面”的样本点概率都是 $p^r(1-p)^{n-r}$（这就是 L15 中对样本点概率的定义方式，L17 会用乘法法则给出它的严格理由）。
- 由可加性，$\Pr[\cdot] = \binom{n}{r} \cdot p^r(1-p)^{n-r}$。$\blacksquare$
具体算例：$n=4, p=2/3$，求恰有 2 个正面的概率。
- 计数部分：$\binom42 = 6$。
- 单个样本点概率：$(2/3)^2(1/3)^2 = 4/81$。
- 所以 $\Pr = 6 \times 4/81 = 24/81 = 8/27 \approx 0.2963$。
- 脚本验算：$24/81 = 8/27$。$\checkmark$
二、扑克牌同花（Flush）——概率即是计数之比
52 张牌取 5 张（无序、不放回），样本空间大小 $\binom{52}{5} = 2{,}598{,}960$（L14 第二法则）。事件”同花”= 5 张同花色。每种花色 13 张，取 5 张有 $\binom{13}{5} = 1287$ 种；4 种花色，且不同花色的 5 张手牌互不相交（这正是一个划分，所以可以直接相加），总数 $4\binom{13}{5} = 5148$。因此
\[\Pr[\text{同花}] = \frac{4\binom{13}{5}}{\binom{52}{5}} = \frac{5148}{2598960} \approx 0.00198 \approx \frac{2}{1000}.\]脚本验算：$4\binom{13}{5}/\binom{52}{5} = 0.00198079\ldots$ $\checkmark$（官方 Note 13 给出的正是约 $0.002$。）
三、生日悖论（Birthday Paradox）——用补集 + 不放回序列计数
$n$ 个人的生日序列构成样本空间 $\Omega = \{1,\dots,365\}^n$，$\vert \Omega\vert = 365^n$（有放回、有序）。令 $\overline{A}$ 为”所有人都不同生日”的事件，则 $\overline{A}$ 是从 365 天中取 $n$ 天作有序排列（不放回）的方案集，$\vert \overline{A}\vert = 365 \cdot 364 \cdots (365-n+1)$。于是
\[\Pr[A] = 1 - \frac{365 \cdot 364 \cdots (365-n+1)}{365^{n}}.\]脚本验算：$n=23$ 时 $\Pr[A] \approx 0.5073 > 50\%$；$n=60$ 时 $\Pr[A] \approx 0.9941 > 99\%$。$\checkmark$ 这个例子的教学价值在于：“至少一对相同”用补集数远比正面数容易，而”取补集”本身就是一个双射（$\overline{A} \leftrightarrow A$ 通过 $X \mapsto \Omega \setminus X$），正是定理 16.1 的同一思想。
四、球与箱（Balls and Bins）——负载均衡的计数模型
把 $m$ 个有标号的球投入 $n$ 个有标号的箱，样本空间 $\Omega = \{(b_1,\dots,b_m) : 1 \le b_i \le n\}$，$\vert \Omega\vert = n^m$（有放回有序）。事件”1 号箱为空”就是”每个球都落进其余 $n-1$ 个箱”，方案数 $(n-1)^m$，故
\[\Pr[\text{1 号箱空}] = \left(\frac{n-1}{n}\right)^{m} = \left(1-\frac{1}{n}\right)^m.\]脚本验算：$m=20, n=10$ 时 $\Pr \approx 0.12$，故”1 号箱非空”≈ $0.88$。$\checkmark$ 这个模型在 L20（期望与线性性）、L23（集中不等式）会被反复使用：把”每个作业随机发给一台处理器”建模成投球，就能回答”是否会出现某台处理器过载”。注意这里的计数依赖”球有标号”——如果球无标号，样本空间就变成多重集，计数公式完全不同（见 L14 第三法则 $\binom{n+k-1}{k}$）。
五、Monty Hall —— 样本空间的树形计数
这个经典悖论的纠错关键，恰恰是老老实实地把样本空间数清楚。用三元组 $(i,j,k)$ 表示（奖品门 $i$、选手初选门 $j$、主持人开的门 $k$），合法样本点共 12 个：
- $i \ne j$ 型（6 个）：此时主持人别无选择（不能开 $i$，不能开 $j$），$k$ 被唯一确定，每个概率 $\frac13 \cdot \frac13 \cdot 1 = \frac19$。
- $i = j$ 型（6 个）：此时主持人有两个非奖品门可选，按假设各 $\frac12$，每个概率 $\frac13\cdot\frac13\cdot\frac12 = \frac1{18}$。
校验总概率：$6 \cdot \frac19 + 6 \cdot \frac1{18} = \frac69 + \frac6{18} = 1$。$\checkmark$
换门策略的胜率：换门获胜 $\iff$ 选手初选不是奖品门 $\iff$ $i \ne j$，即那 6 个概率为 $\frac19$ 的样本点。故 $\Pr[W] = 6 \cdot \frac19 = \frac23$。而坚持原选仅 $\frac13$。
脚本验算：$(1/9)/(1/6) = 2/3$，$(1/18)/(1/6) = 1/3$。$\checkmark$ 这个计算会在 L17 用贝叶斯法则重做一遍，作为”教科书式”与”贝叶斯式”两种解法的对照。
与其他讲次的关联
- 与 L14（Counting）：本讲的每个定理都建立在 L14 的两条法则上。定理 16.4 的”男生女生分别选”用第一法则（乘法原理）；定理 16.6 的”先数带标记的、再按等价类归并”用第二法则；定理 16.4 的特殊情形 $\sum_k \binom{n}{k}^2 = \binom{2n}{n}$ 是 L14”多重集计数 $\binom{n+k-1}{k}$”之外，另一个必须掌握的经典封闭形式。
- 与 L15（Probability Foundations）：L15 给出 $\Pr[A] = \vert A\vert /\vert \Omega\vert $（均匀空间）与”事件 = 子集”。本讲则提供计算 $\vert A\vert $ 与 $\vert \Omega\vert $ 的手段。你在 L15 看到的 $\Pr[\text{恰 }2\text{ H in }4] = \binom42/2^4 = 6/16 = 3/8$，其背后正是定理 16.3（$\vert \Omega\vert = 2^4$）与定理 16.6 步骤 4（$\vert A\vert = \binom42$）。
- 与 L17（Conditional Probability & Bayes）：条件概率的定义式 $\Pr[A \mid B] = \Pr[A \cap B]/\Pr[B]$ 在均匀空间下退化为纯计数比 $\vert A \cap B\vert /\vert B\vert $。本讲的组合论证因此可以直接搬到条件概率里：例如”已知第一次抽到 A，第二次也是 A”的概率 $= \frac{4\cdot3}{4 \cdot 51}/\frac{4}{52}$ 的每步都是一个计数论证。L17 还会用贝叶斯法则重做 Monty Hall。
- 与 L18（Independence & Combination of Events）：定义独立性需要 $\Pr[A \cap B] = \Pr[A]\Pr[B]$。“乘法法则在什么条件下合法”这个问题，本讲在定理 16.6 的步骤 2 已经给出了原型答案（每一步的可选数不因前序选择而改变）；L18 会把它正式化为”独立性”。本讲的容斥原理（L14 定理）也会在 L18 以概率形式重现。
- 与 L19（Random Variables）：二项分布的 PMF $p_X(k) = \binom{n}{k}p^k(1-p)^{n-k}$ 就是本讲”均匀计数 + 加权”的产物。理解 $\binom{n}{k}$ 从哪来（选择哪些位置是成功），是理解二项分布的前提。
- 与 L20（Expectations & Linearity）：定理 16.5（$\sum_k k\binom{n}{k} = n2^{n-1}$）有一个概率版本：若 $X \sim \mathrm{Binomial}(n, 1/2)$，则 $\mathbb{E}[X] = \sum_k k\binom{n}{k}2^{-n} = n/2$。L20 会用期望线性性（把 $X$ 拆成 $n$ 个指示变量之和）一行证完，与本讲的组合双计数互为映证。而定理 16.5 的 $T = \{(X,x)\}$ 与 L20 里 $X = \sum_i \mathbb{1}_i$ 是同一个故事的两种讲法。
- 与 L09/L10（Graphs）：定理 16.8（握手引理）是 L09 图论基础的核心工具，也是 L10 讨论欧拉路径（一笔画）存在性判据的前提。奇度顶点个数为偶数这个推论，正是欧拉路径存在性定理的一半。
- 与 L14 的容斥原理（同一讲）：容斥原理的证明本身就是双计数——它数的是”元素 $a$ 在右端被数了几次”。设 $a$ 属于 $m$ 个集合，则被数次数为 $\sum_{k=1}^{m}(-1)^{k-1}\binom{m}{k} = 1$（由本讲交替和推论）。这个”数被数了几次”的技巧在 CS70 中反复出现，值得单独记住。
- 与 L07/L08（Polynomials & ECC）：二项式定理（定理 16.6）是多项式系数的基础，也是 L08 讨论 Reed–Solomon 纠错码时”错误多项式”展开的工具。
关键要点
- 组合证明的两大范式，先分清楚再动手：
- 双计数（double counting）：同一个集合，两种数法。适合处理含求和号的恒等式（右边是”和” ⇒ 对应”分类”）。
- 双射（bijection）：两个集合，一个显式配对。适合处理两边各是一个组合数的恒等式（如 $\binom{n}{k} = \binom{n}{n-k}$）。双射必须验证单射与满射两条，缺一不可。
- 核心哲学：等式两边的差 = 两个集合的差。 找不到”两边各在数什么”，就没有组合证明。
- 组合证明的思考框架（四步法）：
- 第一步：识别两边在数什么。 左边 $\binom{n}{k}$ 通常数”$n$ 元集合的 $k$ 元子集”；左边的和式通常数”按某种特征分类后的并集”。
- 第二步：确定（常常是创造性地定义）”要数的对象”。 这是最难也最关键的一步。遇到”$\binom{n}{k}$ 乘以 $k$”，试试 （子集，其中元素）对；遇到”$\binom{m}{k}\binom{n}{r-k}$”，试试 （从两个池子里分别取）；遇到”求和指标 $i \le n-k$”，试试 （集合的最小元素）。对象定义错了，后面全错。
- 第三步：验证两种数法都无重、无漏。 分类必须是划分（两两不交、并集为全体）；用乘法法则时必须验证每一步的可选数不因前序选择而改变。
- 第四步：若是双射，验证单射与满射。 若 $f \circ f = \mathrm{id}$（自逆），两条可以一次证完。
必须能默写的六条恒等式：
恒等式 组合解释（一句话） 范式 $\binom{n}{k} = \binom{n}{n-k}$ 选谁去 = 选谁不去 双射（取补集） $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ 按某特定元素是否入选分类 双计数 $\sum_{k=0}^{n}\binom{n}{k} = 2^n$ 子集 ↔ 0/1 串 双射 / 双计数 $\sum_{k}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$ 分池子选 vs 合并池选 双计数 $\sum_{k=0}^{n}k\binom{n}{k} = n2^{n-1}$ 数（子集，其中元素）对 双计数 $\sum_{i=k}^{n-1}\binom{i}{k} = \binom{n}{k+1}$ 按最小（或最大）元素分类 双计数 概率中的组合论证 = 均匀样本空间 + 计数。 记住三件套：样本空间是什么 → 每个样本点概率多少 → 事件对应哪些样本点。$\Pr[\text{恰 }r\text{ 个正面}] = \binom{n}{r}/2^n$ 与 $\Pr[\text{同花}] = 4\binom{13}{5}/\binom{52}{5}$ 都是这条范式的直接产物。
组合证明是”跨领域”的工具。 握手引理 $2\vert E\vert = \sum_v \deg v$ 的证明与 $\sum_k k\binom{n}{k} = n2^{n-1}$ 的证明在结构上完全同构（都是”数同一个（对象，附属物）对的集合”）。认出同构的证明骨架比记住单个证明更有价值。
- 交替和 $\sum_k (-1)^k\binom{n}{k} = 0$（$n\ge1$）也可纯组合证明：用”对称差翻转一个固定元素”的对合 $\sigma(X) = X \triangle \{s_n\}$，把偶数元子集与奇数元子集一一配对。注意 $n=0$ 时不成立（和为 1），条件 $n\ge1$ 不能省。
常见误区与注意事项
把有序当无序（或反之）。$\binom{n}{k}$ 数的是无序的 $k$ 元子集；若被数的对象天生带顺序（如”第一次抽到谁、第二次抽到谁”），就必须用 $n(n-1)\cdots(n-k+1)$ 而不是 $\binom{n}{k}$。典型错误：算”两枚骰子点数相同”时把 $(\Omega) = \binom{6}{2} = 15$ 当成样本空间（正确答案是 $6/36 = 1/6$；若用无序样本空间 $15$ 个，点数相同只有 6 个，得到 $6/15 = 2/5$，完全错误）——因为无序样本空间不是均匀的（$(1,1)$ 与 $(1,2)$ 出现概率不同）。
“数了两次但两次数的对象其实不同”。这是本讲最隐蔽的错误。定理 16.4 的反例就是它：$\sum_k \binom{n}{k}^3$ 与 $\binom{3n}{n}$ 看起来形似，但前者数的对象要求”三组各选 $k$ 个（总数 $3k$）”，后者要求”总共选 $n$ 个”——对象不同，等式必假。用脚本验算即可立刻发现（$n=2$ 时 $10 \ne 15$）。
双射只证了单射（或只证了满射）。例如”从 $k$ 元子集中去掉最小元素”这个映射看起来”几乎”是双射，实际上既非单射也非满射（$n=3,k=2$ 时 $\{1,2\}$ 与 $\{2,3\}$ 都映到含 3 的那个集合模式）。有限集合上单射与满射互相蕴含（$\vert A\vert = \vert B\vert $ 时），但在你还不知道该证什么之前，必须两条都检查。
用乘法法则时未验证”每步的选择数与前序选择无关”。L14 第一法则的前提条件：对每一种前 $i-1$ 步的选择，第 $i$ 步都恰好有 $n_i$ 种选择。反例见 L14 的”水果沙拉”问题：$3^5$ 个有序结果按无序结果分组时，每组大小从 1（五根香蕉）到 5（四根香蕉一个苹果）不等，不能除以常数，第二法则失效。用乘法前先问：这个数依赖于前面的选择吗？
把”和”当成”加”而不检查是否构成划分。$\sum_k \binom{n}{k}$ 能这样加，是因为”$k$ 元子集”对不同的 $k$ 互不相交。反之，若把”含 $a$ 的子集”与”含 $b$ 的子集”相加，就不构成划分（会重复计入同时含 $a,b$ 的子集）。每次写 $\sum$ 时都要问：这些类两两不交吗？合起来是全体的吗？
在双计数中忘记排除退化情形。定理 16.7 中 $\min X$ 的上限是 $n-k$ 而非 $n$（因为还要留出 $k$ 个更大的元素）。定理 16.5 中”剩下的元素”是 $n-1$ 个而非 $n$ 个（因为 $x$ 已经固定入选），导致指数是 $n-1$ 而不是 $n$。边界条件通常就是错误藏身之处，写完 $\sum$ 的上限和指数后一定要用小 $n$ 验算一遍。
在均匀样本空间判据上出错。$\Pr[A] = \vert A\vert /\vert \Omega\vert $ 只在均匀空间成立。偏硬币（$p \ne 1/2$）抛 $n$ 次时，各序列概率不同（$p^r(1-p)^{n-r}$），不能简单地用”有利序列数 / 总序列数”，必须对样本点概率加权求和。这一点在 L17 会成为核心。
思考题（带答案）
Q1.（纯计算） 用 Vandermonde 恒等式计算 $\displaystyle\sum_{k=0}^{5}\binom{5}{k}\binom{7}{4-k}$，并写出逐项分解。
答案
由定理 16.4，取 $m=5, n=7, r=4$： $$\sum_{k=0}^{5}\binom{5}{k}\binom{7}{4-k} = \binom{12}{4}.$$ 逐项： | $k$ | $\\binom{5}{k}$ | $\\binom{7}{4-k}$ | 乘积 | |:---|:---|:---|:---| | 0 | 1 | $\\binom74 = 35$ | 35 | | 1 | 5 | $\\binom73 = 35$ | 175 | | 2 | 10 | $\\binom72 = 21$ | 210 | | 3 | 10 | $\\binom71 = 7$ | 70 | | 4 | 5 | $\\binom70 = 1$ | 5 | | 5 | 1 | $\\binom7{-1} = 0$ | 0 | | **和** | | | **495** | 而 $\\binom{12}{4} = 495$。相合。$\\checkmark$ 注意 $k=5$ 时 $\\binom{7}{-1} = 0$（按边界约定），所以上限写成 $5$ 或 $4$ 都一样。**组合解释**：从 5 个男生与 7 个女生中选 4 个人，按"选了几个男生"分类。Q2.（概念理解 / 证明） 证明 $\displaystyle\sum_{k=0}^{n} \binom{n}{k} k^2 = n(n+1)2^{n-2}$（$n \ge 1$）。提示：定义合适的”要数的对象”。
答案
**证明策略**：双计数。左边出现 $k \\cdot \\binom{n}{k}$ 再乘 $k$，提示对象应携带**两个（可以相同）被标记的元素**，或者携带**一个有序的标记对**。 **对象定义**：令 $$T = \{(X, x, y) : X \subseteq S,\ x \in X,\ y \in X\},$$ 其中 $S$ 是 $n$ 元集合，$x, y$ **可以相同**（有序对，允许重复），且都必须在 $X$ 中。 **数法一（按 $\\vert X\\vert = k$ 分类）**：固定 $k$，$X$ 有 $\\binom{n}{k}$ 种；$x$ 有 $k$ 种、$y$ 有 $k$ 种选法，独立，共 $k^2$ 种。于是 $\\vert T\\vert = \\sum_{k=0}^{n}k^2\\binom{n}{k}$。 **数法二（按 $x, y$ 是否相同分情形）**： - **情形 A：$x = y$**。选 $x$（$n$ 种），再决定 $X$ 是否包含其余 $n-1$ 个元素中的每一个（$2^{n-1}$ 种）。共 $n2^{n-1}$ 个。这正好是定理 16.5。 - **情形 B：$x \\ne y$**。先选有序对 $(x,y)$：$x$ 有 $n$ 种、$y$ 有 $n-1$ 种，共 $n(n-1)$ 种。再决定 $X$ 是否包含其余 $n-2$ 个元素（$2^{n-2}$ 种）。（注意 $x,y$ 都必须已经在 $X$ 里，所以它们两个不是自由选择的。）共 $n(n-1)2^{n-2}$ 个。 **合并**： $$\vert T\vert = n2^{n-1} + n(n-1)2^{n-2} = n2^{n-2}\bigl(2 + (n-1)\bigr) = n(n+1)2^{n-2}.$$ 两种数法数同一个 $T$，故 $$\sum_{k=0}^{n}k^2\binom{n}{k} = n(n+1)2^{n-2}. \qquad \blacksquare$$ **验算（$n = 4$）**：左边 $= 0 + 1^2\\cdot4 + 2^2\\cdot6 + 3^2\\cdot4 + 4^2\\cdot1 = 0 + 4 + 24 + 36 + 16 = 80$；右边 $= 4\\cdot5\\cdot2^{2} = 80$。相合。$\\checkmark$ **（顺带指出另一种验算路径）**：若 $X \\sim \\mathrm{Binomial}(n, 1/2)$，则 $\\mathbb{E}[X^2] = \\sum_k k^2\\binom{n}{k}2^{-n} = \\frac{n(n+1)}{4}$。当 $n=4$：$\\mathbb{E}[X^2] = 80/16 = 5 = \\frac{4\\cdot5}{4}$。$\\checkmark$ 与 $\\operatorname{Var}(X) = \\mathbb{E}[X^2] - \\mathbb{E}[X]^2 = 5 - 4 = 1 = n \\cdot \\frac12 \\cdot \\frac12$ 一致（L22 会给出方差公式）。Q3.（概念理解 / 找错误） 下面这个”证明”错在哪里？
待证：$\displaystyle\sum_{k=1}^{n} k\binom{n}{k} = n2^{n}$。 “证明”：考虑从 $n$ 个人中选出一个委员会（任意大小），再从委员会中选出一名主席。选委员会有 $2^n$ 种（定理 16.3），选主席有 $n$ 种……所以总数是 $n2^n$。另一方面，若委员会有 $k$ 人，则有 $\binom{n}{k}$ 个委员会、$k$ 个主席人选，故总数为 $\sum_k k\binom{n}{k}$。两边相等。
答案
**错误在于：对"选主席有 $n$ 种"这一步的两次计数不一致，导致两次数的对象其实不同。** 拆开看： - **左边数的对象**是 $T = \\{(X, x) : X \\subseteq S,\\ x \\in X\\}$ —— **主席必须属于委员会**。 - **右边（"$n2^n$"）数的对象**是 $T^{\\prime} = \\{(X, x) : X \\subseteq S,\\ x \\in S\\}$ —— 主席可以是**任何**人，**不需要**在委员会里。 这两个集合不相等：$\\vert T\\vert $ 中 $x$ 由 $X$ 决定（必须入选），$\\vert T^{\\prime}\\vert $ 中 $x$ 与 $X$ 无关（$X$ 可以是空集，此时"主席不在委员会里"）。所以 $\\vert T\\vert \\ne \\vert T^{\\prime}\\vert $。 **正确做法**（定理 16.5）：选定主席 $x$ 后（$n$ 种），**剩下的 $n-1$ 个人**各自独立决定是否加入委员会（$2^{n-1}$ 种），因为 $x$ 已经在里面了，它没有自由度。故 $\\vert T\\vert = n2^{n-1}$，**不是 $n2^n$**。 **数值反例**：$n = 3$。 - 正确的左边：$1\\cdot3 + 2\\cdot3 + 3\\cdot1 = 3+6+3 = 12$。 - 错误的右边：$n2^{n} = 3\\cdot8 = 24$。 - 若用错误的"证明"，还会推出荒谬结论：$n=1$ 时左边 $= 1$，右边 $= 2$。**$1 \\ne 2$，命题本身是假的。** **教训**：写双计数证明时，必须逐字核对**两次数的是不是同一个集合**。特别是"剩下的元素有几个"这类细节（$n$ 还是 $n-1$）以及"某个元素是否被约束在子集内"，是这类错误的绝对高发区。**用 $n=1$ 或 $n=2$ 过一遍是最便宜的检测手段。**Q4.（证明） 用组合论证证明容斥原理只数一次这一关键步骤：若元素 $a$ 属于 $m$ 个集合 $A_1,\dots,A_n$，则它在 \(\sum_{k=1}^{n}(-1)^{k-1}\sum_{S \subseteq \{1,\dots,n\},\ \vert S\vert = k}\left\vert \bigcap_{i \in S}A_i\right\vert\) 中被数了恰好 $1$ 次。