Lecture 14: Counting（计数）

目录 · ← l14 · l16 →

Lecture 14: Counting（计数）

概述

本讲是课程从”确定性推理”跨入”不确定性推理”的桥梁。上一讲（讲次 13）我们用对角化证明停机问题不可判定；从本讲开始，我们要问的问题变了：掷一枚公平硬币 1000 次，恰好出现 500 次正面的概率是多少？答案是大约 2.5%；而恰好 1000 次正面的概率小到可以当作”不可能”。但在能够计算、估计这些概率之前，我们必须先学会数数——因为在一个结果等可能的样本空间里，概率就是”有利结果数 ÷ 总结果数”，概率计算直接退化为计数问题（这一点在讲次 15 会被正式确立）。

本讲的技术主线是：先把”有多少种”这个问题翻译成”结构 + 规则的组合”，再从两条最基本的规则（乘法法则与和法则）出发，系统构建出排列、组合、二项式系数、星棒法、容斥原理这一整套工具，并且用双射（bijection）和双计数（double counting）给出组合式的证明——这种”同一个故事用两种视角讲”的证明风格，将在讲次 16 被专门展开。

核心概念的直观解释

计数（Counting）

• 定义：给定一个有限集合 $A$，计数就是要确定 $\vert A\vert $，即 $A$ 中元素的个数。这里的”集合”可以是一组牌、一串硬币结果、一堆把球放进箱子的方案，等等。
• 直观解释（”它是什么意思？”）：计数的核心思想是把”有多少”变成”结构与规则的组合”。我们很少真的去一个个列出来数（对 $\vert A\vert = 2{,}598{,}960$ 的一手扑克牌根本数不过来），而是识别出生成这些对象的”过程”——这个过程的每一步有多少种选择，然后把这些选择数组合起来。就像工厂流水线：如果每道工序的产品数量只取决于上一道的产出量，整条线的产量就是一个连乘积。
• 具体示例：一副 52 张牌中抽 5 张，一共多少种不同的手牌？我们不数牌，而是发现”抽牌”这个过程的每一步选择数依次是 $52, 51, 50, 49, 48$，再除以”同一手牌的重复计数次数” $5!$，得到 $2{,}598{,}960$。

第零法则：双射（Zeroth Rule of Counting / Bijection）

• 定义：若集合 $A$ 与集合 $B$ 之间存在一个双射 $f: A \to B$（既是单射又是满射，即存在可逆的一对映射），则 $\vert A\vert = \vert B\vert $。
• 直观解释（”它是什么意思？”）：这是”计数”这件事的真正心脏。它说的是：要数一个难数的集合，你完全可以换一个同样大小但好数的集合去数。把”选水果沙拉”翻译成”安排 0 和 1 的二进制串”，就是这一法则最漂亮的应用。它也是讲次 12（可数性）中”两个集合等势”思想的有限版本——只不过在有限世界里，双射直接保证基数相等，不需要讨论”能不能列完”。
• 具体示例：$\{1,2,3\}$ 的子集共有 8 个，而长度为 3 的 0/1 串也恰好有 8 个；把子集 $S$ 映射到串 $(b_1,b_2,b_3)$，其中 $b_j = 1 \iff j \in S$，这是一个双射，所以两边数目相同。

第一法则 / 乘法法则（First Rule of Counting / Product Rule）

• 定义：若一个对象由 $k$ 个相继的选择步骤构成，第 1 步有 $n_1$ 种选法，且对第 1 步的每一种选法第 2 步都有 $n_2$ 种选法，且对前两步的每一种选法第 3 步都有 $n_3$ 种选法……一直到第 $k$ 步有 $n_k$ 种选法，则能这样造出的不同对象总数为 $n_1 \times n_2 \times \cdots \times n_k$。
• 直观解释（”它是什么意思？”）：注意定义里那句啰嗦的”对每一种选法都有 $n_2$ 种选法”——这才是关键：后续步骤的选择数不能依赖于前面具体选了什么，只能依赖于”已经选了”。这就像一张管辖区域图：无论你走到哪一层，每一层的扇出（branching factor）都是固定的。整个决策过程形成一棵决策树（decision tree），从根到叶的路径与”造出的对象”一一对应，所以对象总数 = 叶子数 = 各层扇出之积。
• 具体示例：先选上衣（3 件），再选裤子（2 条），再选鞋（4 双），则搭配数是 $3 \times 2 \times 4 = 24$。但若”第 2 步有几条裤子可穿”取决于”第 1 步选了哪件上衣”（比如某件上衣不能配某条裤子），乘法法则在这么粗的粒度下就不适用了，必须先重新划分情形（这在”常见误区”一节会详细展开）。

和法则（Sum Rule）

• 定义：若集合 $A$ 被划分为若干两两不相交（pairwise disjoint）的部分 $A_1, A_2, \ldots, A_m$，即 $A = A_1 \cup A_2 \cup \cdots \cup A_m$ 且 $A_i \cap A_j = \emptyset$ 对一切 $i \ne j$ 成立，则 \(\vert A\vert = \vert A_1\vert + \vert A_2\vert + \cdots + \vert A_m\vert .\)
• 直观解释（”它是什么意思？”）：乘法法则管”步骤串联”（每一步都要做），和法则管”情形并列”（只发生其中一种）。用分情形证明时（讲次 2 的分情形证明），我们实际上一直在用和法则——只要各情形互不重叠。所以和法则真正的技术含量不在公式，而在”互不相交“这四个字。
• 具体示例：$1$ 到 $20$ 中能被 $4$ 整除的数有 $5$ 个（$\{4,8,12,16,20\}$），能被 $6$ 整除的数有 $3$ 个（$\{6,12,18\}$），但两者之并不是 $5+3=8$ 个，因为 $12$ 被数了两次，实际只有 $7$ 个。修正公式就是容斥原理（本讲 §5）。

第二法则 / 除法法则（Second Rule of Counting / Division Rule）

• 定义：设 $A$ 是”有序对象”的集合，$B$ 是相应的”无序对象”的集合。若存在一个 $m$-对-$1$ 的函数 $f: A \to B$（即每个 $B$ 中元素恰好有 $m$ 个 $A$ 中元素映射到它），则 $\vert B\vert = \vert A\vert / m$。
• 直观解释（”它是什么意思？”）：先”假装顺序重要”把有序对象数出来，再除以”每个无序对象被重复数的次数”。可以想象成往抽屉里放东西：每个无序结果对应一个抽屉，每个抽屉里恰好装着 $m$ 个有序结果，那么抽屉数就是 $\vert A\vert /m$。前提极其重要：每个抽屉里的东西必须一样多。CS70 官方 Note 10 把它称作”第二法则”（本讲沿用它），而把上面那条”互不相交才能相加”称作和法则；两者名称容易混淆，读者只要记住内容即可。
• 具体示例：从 5 张牌中”有序地”取 2 张有 $5 \times 4 = 20$ 种；同一个 2 张牌的手牌被数了 $2! = 2$ 次，所以手牌数 $= 20/2 = 10 = \binom{5}{2}$。

排列（Permutation）与组合（Combination）

• 定义：设 $S$ 是 $n$ 元集合。$S$ 的 $k$-排列是从 $S$ 中取 $k$ 个不同元素排成一个有序序列，其数目记作 $P(n,k)$；$S$ 的 $k$-组合是从 $S$ 中取 $k$ 个不同元素组成一个集合（无序），其数目记作 $\binom{n}{k}$。
• 直观解释（”它是什么意思？”）：排列关心”顺序”，组合不关心。发牌时”先发到 ♠A 再发到 ♥K”与”先 ♥K 再 ♠A”是同一手牌，但作为发牌序列是两个不同的结果。这两个量的差别恰好是”同一组 $k$ 个东西内部有多少种排列方式”，即 $k!$。
• 具体示例：$n = 5, k = 2$：$P(5,2) = 5 \times 4 = 20$，$\binom{5}{2} = 20 / 2 = 10$。$n=52,k=5$：$P(52,5)=311{,}875{,}200$，$\binom{52}{5}=2{,}598{,}960$。

星棒法（Stars and Bars）

• 定义：方程 $x_1 + x_2 + \cdots + x_k = n$ 的非负整数解的个数为 $\binom{n+k-1}{k-1}$。
• 直观解释（”它是什么意思？”）：把 $n$ 个”星”（★）和 $k-1$ 根”棒”（\|）排成一行。棒是 $k$ 个变量之间的分隔符：第一根棒左边有几颗星，就是 $x_1$ 的值；第 $i-1$ 根与第 $i$ 根棒之间有 $x_i$ 颗星；最后一根棒右边是 $x_k$。于是”一个解”与”一个含 $n$ 颗星、$k-1$ 根棒的序列”构成双射，数序列就是”从 $n+k-1$ 个位置中选 $k-1$ 个放棒”。
• 具体示例：$x_1+x_2+x_3 = 6$ 的串 ★★\|★\|★★★ 对应 $(2,1,3)$；串 \|★★★★\|★★ 对应 $(0,4,2)$（允许某个箱子为空）；串 ★★★★★★\|\| 对应 $(6,0,0)$。三种都是合法的多重集。

四种采样情形（Four Sampling Schemes）的对照

Note 10 的骨架实际上是一张 $2 \times 2$ 的表：有放回 / 无放回 与 有序 / 无序 两个维度交叉，得到四类基本的计数对象。把它们列在一起，是为了让读者看到”同一个方法论（第一法则 → 除法法则 / 双射）如何产出全部四个公式”：

值得强调：右下角那一格是唯一不能靠”乘一乘、除一除”得到答案的，它必须通过第零法则（双射）翻译成”从 $n+k-1$ 个位置里选 $k$ 个”，也就是星棒法。Note 10 特意把这一格放在最后并大费周章地用二进制串来建模，正是要说明：当乘除法则失灵时，换视角（双射）是唯一出路。这张表也是讲次 15 的入场券——Note 13 一开篇就说”随机实验就是从 $n$ 元集合 $S$ 中有放回/无放回地抽 $k$ 个元素，其可能结果恰好就是上一讲数过的那些对象”，因此讲次 15 的样本空间大小直接抄这张表的右列。

（自检） 用 $n = 3, k = 2$ 的小规模手工核对：4 种情形依次给出 $P(3,2) = 6$（$12,13,21,23,31,32$）、$\binom{3}{2} = 3$（$\{1,2\},\{1,3\},\{2,3\}$）、$3^2 = 9$（$11,12,13,21,22,23,31,32,33$）、$\binom{3+2-1}{2} = \binom{4}{2} = 6$（多重集 $11,12,13,22,23,33$）。三与六、三与九之间的差异必须能一一对上元素名，这是检验自己是否真懂了这四个公式的试金石。

完整证明与推导（核心）

定理 14.1（第一法则 / 乘法法则）：设造一个对象需要相继做 $k$ 个选择，第 $i$ 步的选择数恒为 $n_i$（与前面具体选了什么无关，只与”已经选了”有关），则这样造出的不同对象总数为 $n_1 n_2 \cdots n_k$。

证明策略：对步数 $k$ 做归纳法（讲次 3 的工具），同时用决策树叶子计数作为几何直观。选归纳法是因为命题本身就是”对一切 $k$ 成立”的形式，且 $k+1$ 步的情形可以自然地拆成”前 $k$ 步”+”最后一步”，这正是归纳法的标准适用形态。

逐步推导：

• 基础情形 $k = 1$：只有一步，对象与第一步的选择一一对应，因此对象数为 $n_1$，而乘积 $n_1$ 也等于 $n_1$。命题成立。
• 归纳假设：设对任意 $k \ge 1$，$k$ 步过程的对象数恰为 $n_1 n_2 \cdots n_k$。
• 归纳步骤：考虑 $k+1$ 步过程。把每个对象的”前 $k$ 步”看成一个部分对象；由归纳假设，部分对象共有 $N_k := n_1 n_2 \cdots n_k$ 个。
• 对每一个部分对象 $p$，按题设，第 $k+1$ 步有恰好 $n_{k+1}$ 种选法（题设保证这个数目不依赖 $p$ 是什么）。于是每个部分对象向下”分叉”出恰好 $n_{k+1}$ 个完整对象。
• 由和法则，把全体部分对象的贡献相加：由于不同的部分对象所生成的完整对象互不相同（前 $k$ 步就不同），这些 $N_k$ 组之间两两不相交，故 \(\#\{\text{完整对象}\} = \underbrace{n_{k+1} + n_{k+1} + \cdots + n_{k+1}}_{N_k\ \text{项}} = N_k \cdot n_{k+1} = n_1 n_2 \cdots n_k n_{k+1}.\)
• 由归纳原理，命题对一切 $k \ge 1$ 成立。$\blacksquare$

另一种等价视角（决策树 / 笛卡尔积）：把第 $i$ 步的选择集合记作 $C_i$，$\vert C_i\vert = n_i$。则”造出的对象”的集合与笛卡尔积 $C_1 \times C_2 \times \cdots \times C_k$ 存在自然双射（对象 $\mapsto$ 它每一步的选择序列）。由第零法则，两类对象数目相同；而笛卡尔积的基数由定义即为 $\vert C_1\vert \cdot\vert C_2\vert \cdots\vert C_k\vert $。这正是决策树中”叶子数 = 各层扇出之积”的代数版本。

                            根
              /-------------|-------------\
          第 1 步：n1 个分支
            a1            a2            a3        <- 第 1 层（n1 = 3）
           /|\           /|\           /|\
         b1 b2           b1 b2         b1 b2      <- 第 2 层：每点扇出 n2 = 2
        /|\ /|\         /|\ /|\       /|\ /|\
       c c c c c c  ...                            <- 第 3 层：每点扇出 n3 = 3
     叶子总数 = n1 · n2 · n3 = 3 · 2 · 3 = 18 条根到叶的路径
     每条路径 <-> 一种"造对象"的选择序列  =>  对象总数 18

【证明机制解说】：整个证明的”灵光一现”在于把”造对象”看成”走路径”。一旦建立了”对象 ↔ 根到叶路径”的双射，计数就变成了纯粹的树结构算术：一棵每层扇出分别固定为 $n_1,\ldots,n_k$ 的树，其叶子数是各层扇出之积。归纳法的归纳步骤则把这棵”宽树”递归地看成”先造一棵 $k$ 层的树，再给每个叶子挂 $n_{k+1}$ 个孩子”——递归结构与乘积结构同构，这是所有乘法型组合恒等式的共同底色。

反例（说明”选择数必须不依赖前序选择”不可省）：设要从 $\{1,2,3\}$ 中选两个不同的数，第 1 步有 3 种选法。若天真地认为”第 2 步也总有 3 种选法”，就会得到 $3 \times 3 = 9$；但正确的无重复选法只有 $3 \times 2 = 6$ 种（$12,13,21,23,31,32$）。问题在于：第 2 步的”可选项”是 $\{1,2,3\} \setminus \{\text{第 1 步选的}\}$，其大小依赖于第 1 步的具体选择（虽然总是 2，但集合本身变了）。乘法法则允许”数目相同”，要求的是”对每一个前序选择，后续选择数目都一样”——本反例中数目确实都是 2，所以 $3\times 2=6$ 正确；而把第 2 步写成 3 则是彻底无视了”不能重复”这个约束。更危险的情形是数目本身都不同：见下一个反例。

定理 14.0（第二法则 / 除法法则）：设 $A, B$ 是有限集，$f: A \to B$ 满足：对每个 $b \in B$，$\vert f^{-1}(b)\vert = m$（同一个 $m$，与 $b$ 无关），则 $\vert B\vert = \vert A\vert / m$。

证明策略：双计数（double counting）——把 $\vert A\vert $ 用两种方式算出来。选择这个策略是因为命题本身就是关于”两套计数系统之间的关系”，双计数是最自然、也最不容易出错的路子。

逐步推导：

• 一方面，$A$ 是全体有序对象，由定义 $\vert A\vert $ 就是有序对象的数目。
• 另一方面，按像点 $b \in B$ 把 $A$ 分块：$A = \bigcup_{b \in B} f^{-1}(b)$。由于每个元素在 $f$ 下只有一个像，不同 $b$ 对应的原像集互不相交（若 $a \in f^{-1}(b_1) \cap f^{-1}(b_2)$，则 $f(a)$ 同时等于 $b_1$ 与 $b_2$，矛盾）。
• 由和法则，$\vert A\vert = \sum_{b \in B} \vert f^{-1}(b)\vert $。
• 代入题设 $\vert f^{-1}(b)\vert = m$，得 $\vert A\vert = \sum_{b \in B} m = m \cdot \vert B\vert $。
• 两边同除以 $m$（$m \ge 1$，因为每个 $b$ 至少有一个原像；若 $B = \emptyset$ 则 $A = \emptyset$，结论平凡）得 $\vert B\vert = \vert A\vert /m$。$\blacksquare$

【证明机制解说】：这个证明把”能不能除”的问题转化成了”每个原像集是否等大“的问题。注意它的结构：用和法则把 $\vert A\vert $ 按纤维（fiber）展开，再要求每个纤维等大——于是”求和”变成”乘法”，除法才被允许。一旦纤维大小不齐（水果沙拉的情形：纤维大小从 1 到 30 不等），和法则仍然是对的（$\sum_b \vert f^{-1}(b)\vert = \vert A\vert $ 恒成立），但”求和”无法坍缩成”乘以常数”，除法法则就失效了。所以除法法则的真正前提不是”顺序不重要”，而是”纤维等大”。

定理 14.2（组合数公式 / 除法法则）：对 $0 \le k \le n$， \(\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!\,(n-k)!}.\)

证明策略：双计数 + 除法法则。先用第一法则数出”有序”版本 $P(n,k)$（这个容易），再构造一个 $k!$-对-$1$ 的映射到”无序”版本，然后除以 $k!$。选这个策略是因为”有序版”天然适配乘法法则，而”有序”与”无序”之间的桥梁就是一个可显式写出的映射。

逐步推导：

• 第 1 步：数有序的。要形成一个由 $S$ 中 $k$ 个不同元素组成的有序序列：第 1 位有 $n$ 种选法；无论第 1 位选了谁，剩下的 $n-1$ 个元素都可以放在第 2 位，故第 2 位有 $n-1$ 种选法；依此类推，第 $i$ 位（从 1 开始编号）有 $n-i+1$ 种选法。由第一法则（定理 14.1）： \(P(n,k) = n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!}.\)
• 第 2 步：构造”有序 → 无序”的映射。定义 $f$ 把每个有序序列 $(a_1,\ldots,a_k)$ 映到它作为集合 $\{a_1,\ldots,a_k\}$。因为序列里的元素互不相同，这个集合恰好有 $k$ 个元素，是一个合法的 $k$ 元子集，所以 $f$ 确实把”有序对象”映到”无序对象”。
• 第 3 步：验证每个原像恰有 $k!$ 个元素。固定一个 $k$ 元子集 $T$。所有满足 $f(\text{序列}) = T$ 的序列，就是把 $T$ 的 $k$ 个元素排成一列的全体排列。$k$ 个不同元素的全排列数由第一法则为 $k!$（第 1 位 $k$ 选，第 2 位 $k-1$ 选，……，第 $k$ 位 1 选），即 $\vert f^{-1}(T)\vert = k!$。关键点：这个数目对每个 $T$ 都相同，与 $T$ 具体是什么无关——除法法则的前提在此得到满足。
• 第 4 步：套用除法法则。$f$ 是 $k!$-对-$1$ 的，$\vert A\vert = P(n,k)$，$\vert B\vert = $ 无序对象数 $= \binom{n}{k}$。于是 \(\binom{n}{k} = \frac{\vert A\vert }{k!} = \frac{n!}{k!\,(n-k)!}. \qquad \blacksquare\)
• 数值校验：$n=52,k=5$：$P(52,5) = 52 \times 51 \times 50 \times 49 \times 48 = 311{,}875{,}200$，除以 $5! = 120$ 得 $\binom{52}{5} = 2{,}598{,}960$。（脚本验算：$\binom{52}{5}=2598960$ ✓）

补充：为什么下降乘积恰好是 $n!/(n-k)!$ 而不是别的。把定理 14.1 用在排列上，得到 $P(n,k) = n(n-1)\cdots(n-k+1)$，共 $k$ 个因子。把它改写： \(n(n-1)\cdots(n-k+1) = \frac{n(n-1)\cdots(n-k+1)\cdot\underbrace{(n-k)(n-k-1)\cdots 1}_{(n-k)!}}{(n-k)!} = \frac{n!}{(n-k)!}.\) 这里我们看到”为什么是递减相乘、为什么恰好 $k$ 个因子”：第 $i$ 个位置（$i = 1,\ldots,k$）的可用元素个数是 $n - (i-1)$，因为前面已经用掉了 $i-1$ 个互不相同的元素。“互不相同”这一条是递减的根源：若允许重复，可用元素个数就恒为 $n$，乘积退化为 $n^k$。这也顺带回答了”为什么 $\binom{n}{k}$ 的分母是 $k!(n-k)!$”：分子 $n!$ 是全部 $n$ 个元素的全排列数，除以 $k!$（同一手牌内部的顺序）再除以 $(n-k)!$（没被选中的那些元素的顺序——在”排列 $k$ 个元素”的原始问题里它们根本没有位置，但 $P(n,k) = n!/(n-k)!$ 的推导把它们”虚拟地排列”了，所以要在分母里除回来）。

【证明机制解说】：这个证明的灵魂是“先数有序，再除以 $k!$”。它把”难数的无序对象”约化为”好数的有序对象”，代价只是”要能算出每个无序对象被重复数了几次”。两个必须检查的地方：(1) 每个 $k$ 元子集恰好对应 $k!$ 个有序序列（不是”至少”或”至多”）；(2) 这个 $k!$ 对所有子集都一样。若把”选 5 个不同元素”换成”取 5 个允许重复的元素”（即多重集），第二个条件就崩了：$(5,0,0)$ 这个多重集只对应 1 个有序序列，而 $(4,1,0)$ 对应 5 个（见下面的反例）。这正是为什么多重集需要星棒法而不是简单除法。

反例（除法法则的前提不可省）：有无限多的苹果、香蕉、橘子，要选 5 个水果做沙拉（只看种类数量，不看顺序）。天真做法：有序取法有 $3^5 = 243$ 种，除以”每个无序结果对应多少个有序序列”。但除数不是常数：若沙拉是 5 个香蕉，只有 $1$ 个有序序列 BBBBB；若是 4 个香蕉 + 1 个苹果，则有 $5$ 个有序序列（ABBBB, BABBB, BBABB, BBBAB, BBBB A）。$243$ 无法被任何单一的 $m$ 整除得到正确答案。正确做法是星棒法：$x_1 + x_2 + x_3 = 5$ 的非负解数 $= \binom{5+3-1}{3-1} = \binom{7}{2} = 21$。（脚本验算：$\binom{7}{5}=21$，且按”箱大小分布”暴力分类后各分布对应的有序序列数分别为 $1,5,10,20,30,\dots$，各不相同 ✓）

定理 14.3（二项式定理 / Binomial Theorem）：对一切 $n \in \mathbb{N}$， \((x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}.\)

证明策略：组合式证明（combinatorial proof）——不靠代数恒等式变形，而是”把等号两边的项都解释成同一个东西的计数”。这里两边数的都是”展开 $(x+y)^n$ 时得到的项”。

逐步推导：

• 把左边写成 $n$ 个因子的连乘：$(x+y)(x+y)\cdots(x+y)$，并把它们标记为 $f_1, f_2, \ldots, f_n$。
• 展开时，我们从每个因子 $f_i$ 中恰好取出一个字母（$x$ 或 $y$），然后把取出的 $n$ 个字母相乘，得到一个单项式；最后把所有这样的乘积相加。
• 由第一法则，取法总数为 $\underbrace{2 \times 2 \times \cdots \times 2}_{n} = 2^n$，恰好对应展开式的 $2^n$ 个单项式（未合并同类项时）。
• 现在固定 $k$，考察形如 $x^k y^{n-k}$ 的单项式：它由”从 $k$ 个因子里取 $x$、从其余 $n-k$ 个因子里取 $y$”产生。反过来，只要指定哪 $k$ 个因子贡献 $x$，这个单项式就被完全确定。
• 因此 $x^k y^{n-k}$ 在合并同类项前的出现次数 $=$ 从 $\{f_1,\ldots,f_n\}$ 中选 $k$ 个因子的方案数 $= \binom{n}{k}$（定理 14.2）。
• 合并同类项即得 $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$。$\blacksquare$
• 小规模验证：$n=2$ 时展开得 $x^2 + xy + yx + y^2$，其中 $x^2$ 来自”两个因子都取 $x$”（$\binom{2}{2}=1$ 种），$xy$ 型项来自”一个取 $x$ 一个取 $y$”（$\binom{2}{1}=2$ 种：$xy$ 和 $yx$），$y^2$ 来自 $\binom{2}{0}=1$ 种。合并得 $x^2 + 2xy + y^2$ ✓。
• 小规模验证：$n=3$ 时 $\sum_{k=0}^3 \binom{3}{k} = 1+3+3+1 = 8 = 2^3$ ✓。

【证明机制解说】：组合式证明与代数证明的最大区别在于”每一项都有故事“。$\binom{n}{k}$ 在这里不是”某个公式算出来的数”，而是”在 $n$ 个因子里挑 $k$ 个贡献 $x$ 的方案数”。一旦接受了这个解释，很多恒等式就不需要算了，直接”讲故事”即可——本讲后面四条恒等式全部沿用这个套路。

定理 14.4（组合恒等式四则）：

(a) 对称性：$\displaystyle\binom{n}{k} = \binom{n}{n-k}$。

证明策略：构造显式双射。

逐步推导：定义 $f$ 把每个 $k$ 元子集 $S \subseteq \{1,\ldots,n\}$ 映到它的补集 $\bar S = \{1,\ldots,n\} \setminus S$。因为 $\vert \bar S\vert = n - k$，所以 $f$ 确实把 $k$ 元子集映到 $(n-k)$ 元子集。它是单射（$\bar S$ 唯一确定 $S$）也是满射（任何 $(n-k)$ 元子集 $T$ 都是 $\bar T$ 的像，且 $\bar T$ 是 $k$ 元）。故 $f$ 是双射，由第零法则两边数目相等。$\blacksquare$

(b) Pascal 法则：$\displaystyle\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$。

证明策略：固定一个元素，分”含它 / 不含它”两种情形，再用和法则（两部分互不相交）。

逐步推导：设 $S = \{1,\ldots,n\}$，特别关注元素 $n$。把 $S$ 的全部 $k$ 元子集按”是否包含 $n$”分成两类：

• 含 $n$ 的：选定 $n$ 后，还需从剩下的 $n-1$ 个元素中选出 $k-1$ 个，方案数 $\binom{n-1}{k-1}$。
• 不含 $n$ 的：全部 $k$ 个元素都来自 $\{1,\ldots,n-1\}$，方案数 $\binom{n-1}{k}$。

这两类互不相交（一个含 $n$ 一个不含），且并起来正好是全部 $k$ 元子集，故由和法则总数 $= \binom{n-1}{k-1} + \binom{n-1}{k}$。$\blacksquare$

数值校验：$n=6,k=3$：$\binom{6}{3} = 20$，$\binom{5}{2} + \binom{5}{3} = 10 + 10 = 20$ ✓（脚本验算）。

(c) 行和：$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$。

证明策略：给出两种证明——代数式（二项式定理代入）与双射式（子集 ↔ 比特串）。

逐步推导（代数式）：在定理 14.3 中取 $x = 1, y = 1$，得 $(1+1)^n = \sum_{k=0}^n \binom{n}{k} 1^k 1^{n-k} = \sum_{k=0}^n \binom{n}{k}$，左边是 $2^n$。$\blacksquare$

逐步推导（双射式，更贴近”计数”本意）：左边 $\sum_k \binom{n}{k}$ 按定义是”大小恰为 $k$ 的子集的个数”对 $k$ 求和；由于不同大小 $k$ 的子集互不相交，由和法则，左边 $=$ $S$ 的全部子集（任意大小）的个数。右边：把每个子集 $T \subseteq S$ 对应到一个 $n$ 比特串 $(b_1,\ldots,b_n)$，规定 $b_j = 1 \iff j \in T$。这是一个双射（给定串能唯一还原 $T$，给定 $T$ 能唯一写出串），而 $n$ 比特串共有 $2^n$ 个（每位 2 种选择，第一法则）。由第零法则，全体子集数 $= 2^n$。$\blacksquare$

小规模验证：$S=\{1,2,3\}$，$n=3$。8 个子集为 $\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$，对应的 3 比特串依次为 $000,100,010,001,110,101,011,111$。左边 $=\binom{3}{0}+\binom{3}{1}+\binom{3}{2}+\binom{3}{3}=1+3+3+1=8$ ✓。

(d) 交错和：$\displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$（对 $n \ge 1$）。

证明策略：代数式（二项式定理代入 $x=-1,y=1$）+ 组合式（偶子集与奇子集之间的符号反转双射）。

逐步推导（代数式）：在定理 14.3 中取 $x = -1, y = 1$，得 $\sum_{k=0}^n \binom{n}{k}(-1)^k 1^{n-k} = (-1+1)^n = 0^n = 0$（$n \ge 1$）。$\blacksquare$

逐步推导（组合式，直接证明）：左边 $= \#\{\text{偶大小子集}\} - \#\{\text{奇大小子集}\}$。设 $S$ 非空，固定元素 $a \in S$。定义映射 $\varphi(T) = T \triangle \{a\}$（对称差，即”含 $a$ 就去掉，不含就加入”）。$\varphi$ 把偶大小子集映到奇大小子集（大小改变 $\pm 1$，奇偶性翻转），且 $\varphi$ 是自身的逆（$\varphi(\varphi(T)) = T$），因此是双射。由第零法则，偶子集与奇子集一样多，两者之差为 0。$\blacksquare$

数值校验：$n=4$：$\binom{4}{0}-\binom{4}{1}+\binom{4}{2}-\binom{4}{3}+\binom{4}{4} = 1-4+6-4+1 = 0$ ✓（脚本对 $n=1,\ldots,10$ 全部验证为 0）。

(e)〔补充〕曲棍球棒恒等式（Hockey-stick Identity）：对 $0 \le k < n$， \(\binom{n}{k+1} = \binom{n-1}{k} + \binom{n-2}{k} + \cdots + \binom{k}{k}.\)

证明策略：按”最小元素是谁”分情形（和法则），这是 Note 10 给出的组合式证明。

逐步推导：左边数的是 $\{1,\ldots,n\}$ 的大小为 $k+1$ 的子集 $X$。对每个这样的 $X$，记 $m = \min X$ 为它的最小元素。按 $m$ 的取值把全体 $X$ 分类：

• $m = 1$：还需从 $\{2,\ldots,n\}$ 中选 $k$ 个，方案数 $\binom{n-1}{k}$；
• $m = 2$：还需从 $\{3,\ldots,n\}$ 中选 $k$ 个，方案数 $\binom{n-2}{k}$；
• $m = 3$：方案数 $\binom{n-3}{k}$；
• ……
• $m = n-k$：还需从 $\{n-k+1,\ldots,n\}$ 中选 $k$ 个（恰好 $k$ 个元素，只能全选），方案数 $\binom{k}{k} = 1$。

最小元素不可能超过 $n-k$，因为要选出 $k+1$ 个互不相同的元素。各类互不相交（最小元素不同），由和法则即得右式。$\blacksquare$

数值校验：$n=6,k=2$：$\binom{5}{2}+\binom{4}{2}+\binom{3}{2}+\binom{2}{2} = 10+6+3+1 = 20$，而 $\binom{6}{3}=20$ ✓。

定理 14.5（星棒法 / Stars and Bars）：设 $k \ge 1$，$n \ge 0$。方程 \(x_1 + x_2 + \cdots + x_k = n, \qquad x_i \in \mathbb{Z}_{\ge 0}\) 的非负整数解的个数为 \(\binom{n+k-1}{k-1} = \binom{n+k-1}{n}.\)

证明策略：构造双射，把”解”翻译成”符号串”。这正是第零法则的教科书级应用——原问题看起来和”数集合”完全不同，但换个视角就能用已知工具解决。

逐步推导：

• 把解编码成串。给定一个解 $(x_1,\ldots,x_k)$，写下一行由 $n$ 个 ★ 和 $k-1$ 个 \| 组成的串，规则是：先写 $x_1$ 个 ★，再写 1 个 \|，再写 $x_2$ 个 ★，再写 1 个 \|，……，写 $x_k$ 个 ★ 收尾。因为 $\sum_i x_i = n$，串中恰好有 $n$ 个 ★；因为分隔符是 $k-1$ 个，串长为 $n + k - 1$。
• 验证这是双射。给定这样的串，反过来读：数第一根 \| 之前的 ★ 个数就是 $x_1$，第 $i-1$ 与第 $i$ 根 \| 之间（对 $i = 2,\ldots,k-1$）的 ★ 个数是 $x_i$，最后一根 \| 之后的 ★ 个数是 $x_k$（可能是 0）。由此唯一还原出 $(x_1,\ldots,x_k)$，且它自动满足 $\sum_i x_i = n$、$x_i \ge 0$。因此”解”与”串”一一对应。
• 数串。只需决定”$n+k-1$ 个位置中，哪 $k-1$ 个位置放 \|“，其余位置自动都是 ★。选择时不能重复选同一位置（无放回），且选位置的顺序无关（先选位置 3 再选位置 7 与反过来结果同一串），所以方案数是组合数 \(\binom{n+k-1}{k-1}.\)
• 由第零法则，解的个数就等于这个组合数。由定理 14.2 的对称性 $\binom{n+k-1}{k-1} = \binom{n+k-1}{(n+k-1)-(k-1)} = \binom{n+k-1}{n}$。$\blacksquare$

变体（要求 $x_i \ge 1$ 即每个变量至少为 1）：令 $y_i = x_i - 1 \ge 0$，则 $\sum_i y_i = n - k$。于是解的个数为 $\binom{(n-k)+k-1}{k-1} = \binom{n-1}{k-1}$。注意：这个公式要求 $n \ge k$，否则无解（个数为 0），而 $\binom{n-1}{k-1}$ 在 $n < k$ 时按约定也为 0，公式仍然自洽。另一种等价视角：$x_i \ge 1$ 意味着”第一根棒之前至少有 1 颗星、相邻棒之间至少 1 颗星、最后一根棒之后至少 1 颗星”，即把 $k-1$ 根棒插进 $n$ 颗星之间的 $n-1$ 个空隙里，每处最多插一根，方案数正是 $\binom{n-1}{k-1}$。

   n = 6, k = 3 的编码示例（3 个变量，需要 2 根棒）：

   ★ ★ | ★ | ★ ★ ★      <->  (x1, x2, x3) = (2, 1, 3)
   | ★ ★ ★ ★ | ★ ★      <->  (x1, x2, x3) = (0, 4, 2)   [x1 为 0 也合法]
   ★ ★ ★ ★ ★ ★ | |      <->  (x1, x2, x3) = (6, 0, 0)   [两个箱子为空也合法]

   串长 = n + (k-1) = 6 + 2 = 8；只需挑 2 个位置放 "|"
   解的个数 = C(8, 2) = C(n+k-1, k-1) = C(6+3-1, 3-1) = 28

数值校验：$\binom{8}{2} = 28$。$n=10, k=5$：非负解数 $\binom{14}{4} = 1001$（脚本暴力枚举得 1001 ✓）；正解数 $\binom{9}{4} = 126$（暴力枚举得 126 ✓）。$n=10,k=3$：非负解 $\binom{12}{2}=66$，正解 $\binom{9}{2}=36$ ✓（脚本均验证）。

【证明机制解说】：星棒法的关键一步是选择”用什么符号编码”。原问题是”给 $k$ 个变量分配总数 $n$”，看起来和组合数毫无关系；但把分配方案写成一串 ★ 与 \| 之后，”分配方案”就变成了”在固定长度串中选若干位置”，立刻落回定理 14.2 的射程。这也是 CS70 反复强调的方法论：计数问题的困难往往不在算，而在找对视角。注意 Note 10 用 0 表示元素、用 1 表示分隔符，与本文的 ★/\| 是同一个双射，只是记号不同。

定理 14.6（容斥原理 / Principle of Inclusion-Exclusion）：设 $A_1, A_2, \ldots, A_n$ 是同一个有限全集 $U$ 的任意子集，则 \(\left\vert \bigcup_{i=1}^{n} A_i \right\vert = \sum_{k=1}^{n} (-1)^{k-1} \sum_{\substack{S \subseteq \{1,\ldots,n\} \\ \vert S\vert = k}} \left\vert \bigcap_{i \in S} A_i \right\vert .\)

写成展开式更直观： \(\vert A_1 \cup \cdots \cup A_n\vert = \sum_i \vert A_i\vert - \sum_{i<j} \vert A_i \cap A_j\vert + \sum_{i<j<k} \vert A_i \cap A_j \cap A_k\vert - \cdots + (-1)^{n-1} \vert A_1 \cap \cdots \cap A_n\vert .\)

三个集合的特例（$n=3$）： \(\vert A \cup B \cup C\vert = \vert A\vert + \vert B\vert + \vert C\vert - \vert A \cap B\vert - \vert A \cap C\vert - \vert B \cap C\vert + \vert A \cap B \cap C\vert .\)

证明策略：“逐元素计次”证明（元素计数法）。Note 10 特意避开了标准的”对 $n$ 归纳”，改用组合式论证，理由是后者更直接地揭示了”为什么要交替加减”。核心思路是：不去数集合，而是固定一个元素，数它在右式里被算了多少次，并证明这个次数恰好是 1（在并集里的元素）或 0（不在并集里的元素）。

逐步推导：

• 情形 1：$a \notin A_1 \cup \cdots \cup A_n$。此时对一切 $i$ 都有 $a \notin A_i$，于是对任何子集 $S \subseteq \{1,\ldots,n\}$，$\bigcap_{i \in S} A_i$ 也不含 $a$（因为它被每个 $A_i$ 排除）。所以 $a$ 在右式中的每一项都不被计入，贡献为 $0$。这与左边”$a$ 不在并集中”一致。
• 情形 2：$a \in A_1 \cup \cdots \cup A_n$。定义指标集 \(M = \{\, i \in \{1,\ldots,n\} : a \in A_i \,\}, \qquad m := \vert M\vert \ge 1.\) 即”包含 $a$ 的那些集合”的下标。
• 由定义，$a \in \bigcap_{i \in S} A_i \iff S \subseteq M$（且 $S \ne \emptyset$）。若 $S$ 里含有不在 $M$ 中的下标 $j$，则 $a \notin A_j$，交集自然不含 $a$。
• 因此 $a$ 在右式中被计入的次数为 \(\sum_{k=1}^{m} (-1)^{k-1} \sum_{\substack{S \subseteq M \\ \vert S\vert = k}} 1 = \sum_{k=1}^{m} (-1)^{k-1} \binom{m}{k}.\) 第一个等号用到”内层求和就是在数 $M$ 的 $k$ 元子集个数”，即 $\binom{m}{k}$。
• 由定理 14.4(d)（交错和为零）：$\sum_{k=0}^{m} (-1)^k \binom{m}{k} = 0$，把 $k=0$ 项（等于 1）移过去得 \(\sum_{k=1}^{m} (-1)^{k-1} \binom{m}{k} = 1.\) 所以 $a$ 被计入恰好 1 次。
• 合并：不在并集中的元素贡献 0，在并集中的元素贡献 1，故右式之和恰等于 $\vert \bigcup_i A_i\vert $。$\blacksquare$

【证明机制解说】：这个证明最漂亮的地方是把集合问题转化成”每个元素的权重”问题。右式的交替加减不是随便凑出来的系数，而是”让每个被数了 $m$ 次的元素，最后净计数恰为 1”的唯一配方。这也解释了为什么符号必须是 $-+-+\cdots$：因为 $\sum_{k=1}^m (-1)^{k-1}\binom{m}{k} = 1$ 对一切 $m \ge 1$ 成立，而与 $m$ 无关——容斥公式对所有元素”一视同仁”，不需要知道任何元素的 $m$ 是多少。这个”交错和恒为 1”的现象与定理 14.4(c)、14.4(d) 是同一枚硬币的两面。

具体算例（容斥）：$1$ 到 $100$ 中能被 $2$、$3$ 或 $5$ 整除的数的个数

设 $U = \{1,2,\ldots,100\}$，$A_2, A_3, A_5$ 分别为其中能被 $2$、$3$、$5$ 整除的数。则 $\vert A_d\vert = \lfloor 100/d \rfloor$，且 $\vert A_d \cap A_{d^{\prime}}\vert = \lfloor 100 / \mathrm{lcm}(d,d^{\prime}) \rfloor$。

• 单个：$\vert A_2\vert = \lfloor 100/2 \rfloor = 50$，$\vert A_3\vert = 33$，$\vert A_5\vert = 20$。
• 两两交集：$\vert A_2 \cap A_3\vert = \lfloor 100/6 \rfloor = 16$，$\vert A_2 \cap A_5\vert = \lfloor 100/10 \rfloor = 10$，$\vert A_3 \cap A_5\vert = \lfloor 100/15 \rfloor = 6$。
• 三重交集：$\vert A_2 \cap A_3 \cap A_5\vert = \lfloor 100/30 \rfloor = 3$（即 $30, 60, 90$）。
• 代入三集公式： \(\vert A_2 \cup A_3 \cup A_5\vert = (50 + 33 + 20) - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74.\)
• 脚本验算：直接循环 $i = 1..100$ 判断 i%2===0 \|\| i%3===0 \|\| i%5===0 计数得 $74$ ✓，与公式完全一致。同理对 $1$ 到 $1000$：暴力计数 $734$，公式 $\lfloor 1000/2\rfloor+\lfloor 1000/3\rfloor+\lfloor 1000/5\rfloor-\lfloor 1000/6\rfloor-\lfloor 1000/10\rfloor-\lfloor 1000/15\rfloor+\lfloor 1000/30\rfloor = 500+333+200-166-100-66+33 = 734$ ✓。

  容斥的"两集"图景：

        ┌──────────────────────────────────────────────┐
        │                 U （全集）                    │
        │     ┌───────────────┐   ┌───────────────┐    │
        │     │       A       │   │       B       │    │
        │     │        ┌──────┼───┼──────┐        │    │
        │     │        │    A ∩ B  │      │        │    │
        │     │        └──────┼───┼──────┘        │    │
        │     └───────────────┘   └───────────────┘    │
        └──────────────────────────────────────────────┘

    |A| + |B| 时：A∩B 内的元素被数了 2 次，A\B 与 B\A 内各被数 1 次
    减去 |A∩B| 后：A∩B 内净计数 2 - 1 = 1  ✓
    若有第三个集合，三重交集在 +A+B+C 中被数 3 次，
    在 -AB-AC-BC 中被减 3 次 => 净 0 次，必须再 +ABC 补回 1 次

应用：用容斥重证错排公式（Derangements）

定义 14.1（错排 / Derangement）：设 $\pi = (\pi_1,\ldots,\pi_n)$ 是 $\{1,\ldots,n\}$ 的一个排列。若指标 $i$ 满足 $\pi_i = i$，称 $i$ 为 $\pi$ 的一个不动点（fixed point）。没有不动点的排列称为错排，其数目记作 $D_n$。

直观背景（”它是什么意思？”）：$n$ 个学生交作业，老师随机打乱后发回。排列 $\pi$ 中 $\pi_i$ 表示”第 $i$ 个学生拿到的作业编号”。学生 $i$ 拿回自己作业 $\iff \pi_i = i$。$D_n$ 就是”没有一个人拿到自己作业“的发法数。一个自然的问题是：平均有多少人拿到自己的作业？本讲先把 $D_n$ 算出来，讲次 20（期望的线性性）会几行给出答案：平均值恰好是 $1$，与 $n$ 无关。

用容斥求 $D_n$：令 $A_i$ = “第 $i$ 个位置是不动点”的全部排列的集合，即 $A_i = \{\pi : \pi_i = i\}$。

• $\vert A_i\vert = (n-1)!$：固定 $\pi_i = i$，其余 $n-1$ 个元素任意排列。
• 更一般地，对 $\vert S\vert = k$，$\vert \bigcap_{i \in S} A_i\vert = (n-k)!$：固定这 $k$ 个位置，其余 $n-k$ 个元素任意排列。
• 这样的 $k$ 元下标集有 $\binom{n}{k}$ 个，所以由容斥 \(\vert A_1 \cup \cdots \cup A_n\vert = \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} (n-k)! = \sum_{k=1}^{n} (-1)^{k-1} \frac{n!}{k!}.\)
• “至少有一个不动点”的排列数为 $\vert A_1 \cup \cdots \cup A_n\vert $，故 \(D_n = n! - \sum_{k=1}^{n} (-1)^{k-1} \frac{n!}{k!} = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.\)
• 数值校验：$D_1 = 0$，$D_2 = 1$（唯一的错排 $(2,1)$），$D_3 = 2$（$(2,3,1)$ 与 $(3,1,2)$），$D_4 = 9$，$D_5 = 44$，$D_6 = 265$，$D_7 = 1854$（脚本按公式 $n!\sum_{k=0}^{n}(-1)^k/k!$ 与按递推 $D_n = (n-1)(D_{n-1}+D_{n-2})$ 两种方式算出的 $n=1..10$ 序列完全一致 ✓）。
• 有趣推论：$D_n / n! = \sum_{k=0}^n (-1)^k / k! \to e^{-1} \approx 0.36788$。脚本给出的序列 $D_3/3! = 0.3333$，$D_5/5! = 0.3667$，$D_8/8! = 0.367882$，$D_{10}/10! = 0.367879$ 迅速收敛到 $1/e$。也就是说：无论 $n$ 多大，”没有一个人拿到自己作业”的概率约为 36.8%。

（补充）错排的递推式及组合证明：可以只用双射得到不用容斥的递推 \(D_n = (n-1)\left( D_{n-1} + D_{n-2} \right), \qquad n \ge 3,\) 边界 $D_1 = 0, D_2 = 1$。逐步推导：在错排 $\pi$ 中考察 $\pi_n = j \in \{1,\ldots,n-1\}$（$j = n$ 不可能，否则 $n$ 是不动点），共 $n-1$ 种选择，这就是乘子 $(n-1)$ 的来源。固定 $j$ 后分两种情形：

• 情形 1：$\pi_j = n$。此时 $j$ 与 $n$ 互换，剩下 $\{1,\ldots,n\} \setminus \{j,n\}$ 这 $n-2$ 个元素上的限制恰好是”错排”条件（每个元素都不能映到自己），故方案数 $D_{n-2}$。
• 情形 2：$\pi_j \ne n$。此时可以”把 $j$ 看成新的 $n$”：在集合 $\{1,\ldots,j-1,j+1,\ldots,n\}$（把 $j$ 换成标签 $n$）上，限制是”任何元素都不能映到自己”，这恰好是一一对应的 $D_{n-1}$ 个错排。方案数 $D_{n-1}$。

两类都乘以 $n-1$ 种 $j$，相加得递推式。脚本验证：由 $D_1=0,D_2=1$ 递推得 $0,1,2,9,44,265,1854,14833,133496,1334961$，与闭式完全一致 ✓。

计数中的常见陷阱（具体反例集）

1. 双重计数（overcounting）：把 $\vert A_1 \cup A_2\vert $ 写成 $\vert A_1\vert + \vert A_2\vert $ 而漏掉 $\vert A_1 \cap A_2\vert $。具体反例：掷一个骰子，$A = \{$偶数$\} = \{2,4,6\}$，$B = \{x \ge 4\} = \{4,5,6\}$。$(\vert A\vert +\vert B\vert )/6 = 6/6 = 1$，即”必然事件”——荒谬。正确的 $\vert A \cup B\vert = 3+3-2 = 4$，概率 $= 4/6 = 2/3$（脚本验算 ✓）。作为对照，$A = \{$偶数$\}$ 与 $C = \{$奇数$\}$ 确实互斥，$\vert A \cup C\vert = 3+3 = 6$ 正确——互斥性不是装饰，是前提。
2. 把无序当有序 / 把有序当无序：从 52 张牌中抽 5 张，若误用有序计数 $P(52,5) = 311{,}875{,}200$ 作为样本空间大小（见讲次 15 的用法），则计算概率时分子分母的计数方式必须一致；如果分子是按”手牌（无序）”数出来的，就会得到小 $5! = 120$ 倍的错误答案。黄金法则：分子分母必须用同一种计数约定。
3. 误用除法法则（除数不是常数）：本讲定理 14.2 的反例——水果沙拉问题中每个多重集对应的有序序列数从 1 到 30 不等，$3^5/m$ 无解。必须改用星棒法。
4. 星棒法忘记”非负 / 正”的差别：$x_1+x_2+x_3 = 10$ 的非负解数是 $\binom{12}{2} = 66$；而”每个变量至少为 1”的解数是 $\binom{9}{2} = 36$。两者差 30，脚本暴力枚举分别为 66 与 36 ✓。若题目说”分给 3 个小朋友每人至少一颗糖”，却用了非负公式，就会多算 30 种。
5. 星棒法误用于”上界约束”问题：星棒法处理的是无上界的非负整数解。若要求 $x_i \le 5$，直接套 $\binom{n+k-1}{k-1}$ 会把 $x_i = 8$ 这种非法解算进去。正确做法是先算无约束解数，再用容斥减去”某个 $x_i \ge 6$”的解（令 $y_i = x_i - 6$，变回无约束问题）。
6. 乘法法则用于”有依赖的步骤”：如”从 $\{1,2,3\}$ 中不重复地取 2 个数”，若写成 $3 \times 3$ 得 9，忽略了”第 2 步不能取已取的数”。

本讲全部关键数值的集中验算表（全部由 node 脚本跑出，供自查）

与经典问题的联系

（1）哈希表与负载均衡（讲次 20 的前置）：把 $m$ 个球投入 $n$ 个箱子、球与箱都可区分，所有投法的总数是 $n^m$（第一法则：每个球独立地有 $n$ 种落点）。这是”随机哈希”的标准模型：$m$ 个键被哈希到 $n$ 个槽位。”某槽位为空”的方案数是 $(n-1)^m$，”两个给定键碰撞”的方案数是 $n$（它们落入同一槽位，剩下 $m-2$ 个球自由）$= n^{m-1}$。一旦给这些方案配上均匀概率（讲次 15），就能算出碰撞概率——讲次 20 会用期望的线性性直接给出”期望碰撞对数 $= \binom{m}{2}/n$”。以 $m = 1000$ 个键、$n = 10^6$ 个槽位为例，期望碰撞对数 $= \binom{1000}{2}/10^6 = 499500/10^6 = 0.4995$（脚本验算 ✓）——这正是”生日悖论”在哈希中的化身。

（2）随机化素性测试（讲次 6 RSA 的配套）：RSA 需要生成大素数 $p,q$。Miller–Rabin 之类的随机化测试对合数输入错误输出”素数”的失败概率极低。要计算或界定这个失败概率，第一步是把测试的所有随机选择建模成一个有限样本空间并数出其中的坏选择个数——这正是本讲的组合计数（以及讲次 23 的 union bound）的用武之地。Note 13 所举的典型陈述”这个随机素性测试算法在输入为合数时输出 prime 的概率至多一万亿分之一”，其分子分母都是计数结果。

（3）纠错码与秘密共享（讲次 7–8）：Reed–Solomon 码的纠错能力论证需要数”通过 $k$ 个点的不超过 $k-1$ 次多项式有多少个”。多项式由它在 $k$ 个点的取值唯一确定（讲次 7 的插值定理），这一”唯一性”本质上是把”多项式”与”$k$ 元组”建立双射；而 Berlekamp–Welch 译码的正确性论证则用到”若两个次数 $\le k-1$ 的多项式在 $\ge k$ 个点相同则恒等”——数点、数自由度，全是计数。

（4）稳定匹配（讲次 11）：Gale–Shapley 算法运行时间的分析需要统计”提议”的总次数上界为 $n^2$（因为每一对 $(m,w)$ 至多提议一次）；”至多一次”这个断言本身就是对 $n \times n$ 个有序对的计数。配对方案的潜在总数是 $n!$（$n$ 个人与 $n$ 个人的完美匹配数），这解释了为什么不能靠枚举找稳定匹配。

（5）可计算性与对角化（讲次 12–13）：可数性的核心工具是”把集合与 $\mathbb{N}$ 或其子集建立双射”，即本讲的第零法则在无限世界的推广；停机问题的证明又用到”把程序编码成字符串/整数”的编码计数。理解有限双射是理解无限双射的第一步。

与其他讲次的关联

• 讲次 3（归纳法）：定理 14.1（乘法法则）的证明就是对步数 $k$ 做归纳，基础情形 $k=1$ 与归纳步骤的结构与讲次 3 的模板完全一致。若只证归纳步骤而漏掉基础情形，$k=1$ 的正确性就无从谈起。
• 讲次 12（可数性）与讲次 13（可计算性）：第零法则（双射保基数）是讲次 12 中”等势”概念的有限版本；讲次 12 用它证明 $\vert \mathbb{N}\vert = \vert \mathbb{Z}\vert = \vert \mathbb{Q}\vert $，而讲次 13 用”不存在双射”证明停机问题不可判定。本讲则用它把”数水果沙拉”化为”数二进制串”。
• 讲次 15（概率基础）：本讲的直接下游。当样本空间是等概率的（uniform）时，概率公式退化为 $\Pr[A] = \vert A\vert /\vert \Omega\vert $，于是”算概率”就是”算两个计数结果之商”。Note 13 中”掷 4 次硬币恰好 2 次正面”要算 $\binom{4}{2}/2^4$，葫芦概率要算 $13\binom{4}{3}\cdot 12\binom{4}{2} / \binom{52}{5}$——全部依赖本讲的组合数。
• 讲次 16（组合证明）：本讲定理 14.3–14.6 已经大量使用组合式证明与双计数，讲次 16 会把”同一个集合用两种方法计数”提升为独立的证明方法论（含双计数恒等式、双射技巧与生成函数思想的雏形）。
• 讲次 19（随机变量）与讲次 20（期望的线性性）：二项分布的概率质量函数 $\Pr[X = k] = \binom{n}{k}p^k(1-p)^{n-k}$ 直接来自本讲的”选 $k$ 个位置放正面”计数；讲次 20 用错排的 $D_n$ 与容斥的结果计算”拿到自己作业的人数的期望恰为 1”。
• 讲次 23（集中不等式）：Chernoff 界的推导需要计数”偏差超过阈值的比特串有多少个”，即对 $\sum_k \binom{n}{k}$ 这类和做精细估计；本讲的二项式定理与行和恒等式是起点。
• 讲次 5（Euclid / FLT / CRT）：容斥算例中”能被 $d$ 与 $d^{\prime}$ 同时整除”要求 $\mathrm{lcm}(d,d^{\prime})$，而 $\mathrm{lcm}(a,b) = ab/\gcd(a,b)$，把本讲的容斥算例与讲次 5 的 $\gcd$ 工具连接起来。
• 讲次 0–2（证明工具箱）：反证法、分情形、构造性证明在本讲中反复出现；分情形证明之所以合法，正是因为各情形互不相交、可用和法则相加——和法则是”分情形”的计数版本。

关键要点

1. 第零法则是一切的地基：$A$ 与 $B$ 之间存在双射 $\Rightarrow \vert A\vert = \vert B\vert $。数不出来的东西，就找一个能数出来的东西与之双射。”编码成 ★ 与 \| 的串”是这一思想的招牌应用。
2. 乘法法则（第一法则）要求”后续选择数不依赖前序具体选择”；它对应决策树的叶子数 = 各层扇出之积。和法则要求各部分互不相交；不互斥时必须用容斥而不是直接相加。
3. 先数有序，再除以 $k!$：$\binom{n}{k} = P(n,k)/k! = n!/(k!(n-k)!)$。能除的前提是”每个无序对象对应的有序对象数恰好相同且等于 $k!$”。多重集不满足此前提，故必须改用星棒法。
4. 二项式定理 $\sum_k \binom{n}{k} x^k y^{n-k}$ 是组合恒等式的母机：代 $x=y=1$ 得 $\sum_k \binom{n}{k} = 2^n$（子集总数）；代 $x = -1, y = 1$ 得 $\sum_k (-1)^k \binom{n}{k} = 0$（偶子集数 = 奇子集数）。Pascal 法则 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ 则是”固定一个元素，看含不含它”。
5. 星棒法：$x_1 + \cdots + x_k = n$（$x_i \ge 0$）的解数 $= \binom{n+k-1}{k-1}$；若要求 $x_i \ge 1$，令 $y_i = x_i - 1$ 化为 $\binom{n-1}{k-1}$。两者不可混用。
6. 容斥原理 $\vert \bigcup_i A_i\vert = \sum_k (-1)^{k-1} \sum_{\vert S\vert =k} \vert \bigcap_{i \in S} A_i\vert $，其正确性的本质是”任意被 $m \ge 1$ 个集合包含的元素，净计数为 $\sum_{k=1}^m (-1)^{k-1}\binom{m}{k} = 1$”——与 $m$ 无关，所以公式对全体元素统一成立。
7. 错排 $D_n = n!\sum_{k=0}^n (-1)^k / k! \approx n!/e$，且 $D_n = (n-1)(D_{n-1}+D_{n-2})$。$D_n/n! \to 1/e \approx 0.3679$。”没有人拿到自己作业”的概率几乎恒为 36.8%。

常见误区与注意事项

1. 滥用除法法则：看见”顺序不重要”就想去除以某个数。必须先验证”每个无序对象对应的有序对象数是否相同”。水果沙拉（多重集）中从 1 到 30 不等，除法法则彻底失效。判断标准：先问”有没有重复元素”——一旦允许重复，$k!$ 就不再是常数。
2. 把乘法法则用在”数目依赖于前序选择”的地方：若第 2 步有多少种选择取决于第 1 步具体选了哪个（不只是”已经选了”这个事实），乘法法则的连乘形式不适用，必须先分情形。经典错误：”从 $\{1,\ldots,n\}$ 中取两个不同元素，有 $n \times n$ 种”（应为 $n(n-1)$）。
3. 容斥中漏项，尤其是漏掉三重交集：三集合公式必须凑齐 7 项（3 个单 + 3 个两两 + 1 个三重）。只写 $\vert A\vert +\vert B\vert +\vert C\vert - \vert A\cap B\vert - \vert A\cap C\vert - \vert B\cap C\vert $ 会少算三重交集里的元素（它们被多减了 1 次）。用 $2,3,5$ 整除的算例自查：$103 - 32 = 71 \ne 74$，差的正是 $\vert A_2 \cap A_3 \cap A_5\vert = 3$。
4. 星棒法搞错”非负 / 正”以及”有没有上界”：非负用 $\binom{n+k-1}{k-1}$，正用 $\binom{n-1}{k-1}$，差一个”先给每个变量各扣 1”。有上界（如 $x_i \le 5$）时星棒法本身不够，必须叠加容斥。$n=10,k=3$ 的两个数值 $66$ 与 $36$ 差 30，务必记住这个对照。
5. 分子分母计数约定不一致：概率计算中，若分母用无序手牌数 $\binom{52}{5}$，分子也必须按无序数；若分母用有序 $P(52,5)$，分子也必须有序列。混用会造成 $5! = 120$ 倍的错误——同花概率 $5148/2598960 \approx 0.001981$（正确）与按有序约定误算的结果有天壤之别。
6. 把 $\binom{n}{k}$ 的 $n < k$ 或 $k < 0$ 当作有定义：约定上 $\binom{n}{k} = 0$（当 $k < 0$ 或 $k > n$）。Pascal 法则、星棒法变体（$n < k$ 时正解数为 0）都依赖这个约定保持自洽。写代码验算时若用”循环乘 $k$ 项”的实现，$k > n$ 会算出 0 但 $k<0$ 可能出错，需要显式处理。
7. 混淆”排列”与”组合”的中文语感：中文里”选 5 个”既可指有序也可指无序。做题时先明确问自己：交换两个元素的先后，是否得到”同一个结果”？ 是则用组合，否则用排列。

思考题（带答案）

Q1.（计算题） 一位咖啡店老板有 4 种糖浆口味（香草、焦糖、榛果、肉桂），无限供应。他要调制 6 杯饮料，每杯恰好加 1 泵糖浆。若只关心”每种口味各用了几泵”（即只看 $4$ 元组 $(x_1,x_2,x_3,x_4)$），共有多少种配方？若要求每种口味至少用 1 泵，又有多少种？进一步，若老板规定香草最多用 2 泵（其他不限），有多少种？

Q2.（证明题） 用组合式论证证明：对 $n \ge 1$， \(\sum_{k=1}^{n} k \binom{n}{k} = n \cdot 2^{n-1}.\)

Q3.（概念理解题） 下面这段”证明”错在哪里？请指出并给出正确的数值。

命题：从 $1$ 到 $100$ 中随机取一个整数，它能被 $2$、$3$ 或 $5$ 整除的概率是 $\frac{50}{100} + \frac{33}{100} + \frac{20}{100} = 1.03 > 1$，所以……

“修正”：既然超过 1 了，那说明这些事件几乎覆盖了所有数，概率约为 $1$。