把 k 个球放入 n 个盒子时，答案总是 n^k。
这只在球可区分且盒子可区分时成立。若球不可区分，应用 stars and bars 得 \(\binom{k+n-1}{n-1}\)。模型前提决定公式。
CS70 · 第 8 讲
本讲在基础计数之上，系统处理三类进阶主题：其一是带约束与对称性的计数——从 stars and bars 到容斥原理再到商计数；其二是网格路径的反射原理与 Catalan 型递推，并揭示其与有序树计数的同构；其三是 Fibonacci 计数模型及其组合证明。核心方法论是双射与两种计数法。
计数问题中最基本的模型之一是：把 \(k\) 个不可区分的对象分配到 \(n\) 个可区分容器中，每个容器可以接收零个或多个对象。等价地，我们求非负整数解的个数：
\[ x_1 + x_2 + \cdots + x_n = k, \quad x_i \in \mathbb{Z}_{\ge 0}. \]
Stars and Bars 方法。 将 \(k\) 个不可区分的小球排成一行（"星"），在它们之间插入 \(n-1\) 个隔板（"棍"）来划分出 \(n\) 个容器。整个序列由 \(k\) 个星和 \(n-1\) 个棍组成，共 \(k + n - 1\) 个位置。只需从中选出 \(n-1\) 个位置放棍（或等价地选 \(k\) 个位置放星），即得：
\[ \#\{\text{分配方式}\} = \binom{k + n - 1}{n - 1} = \binom{k + n - 1}{k}. \]
这个等式的组合本质是：在 \(k+n-1\) 个位置中选择哪些放棍，其余自动放星。
常见变体。 若要求每个容器至少一个对象，则先给每个容器一个，剩余 \(k-n\) 个自由分配（要求 \(k \ge n\)），答案为 \(\binom{k-1}{n-1}\)。
一家甜品店提供 5 种口味的冰淇淋。一位顾客要买 8 个球装在同一只杯中，口味可以重复、顺序不计。问有多少种不同的选购方案？
这里球不可区分（只关心每种口味各要几个），口味有 5 种（可区分容器）。设 \(x_i\) 为第 \(i\) 种口味要的球数，需计数：
\[ x_1 + x_2 + x_3 + x_4 + x_5 = 8, \quad x_i \in \mathbb{Z}_{\ge 0}. \]
由 stars and bars：
\[ \# = \binom{8 + 5 - 1}{5 - 1} = \binom{12}{4} = 495. \]
若顾客要求每种口味至少要一个球，则先给每种口味一个，剩余 3 个球自由分配：
\[ \# = \binom{3 + 5 - 1}{5 - 1} = \binom{7}{4} = 35. \]
当直接计数"至少满足某性质"或"不满足任何禁止性质"的对象时，容斥原理（Principle of Inclusion-Exclusion, PIE）是核心工具。
定理（PIE）。 设 \(A_1, A_2, \ldots, A_n\) 是有限全集 \(U\) 的子集，则
\[ \left|\bigcup_{i=1}^n A_i\right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap \cdots \cap A_n|. \]
补集形式。 更常用的是计数"避开所有性质"的对象：
\[ \left|U \setminus \bigcup_{i=1}^n A_i\right| = |U| - \sum_i |A_i| + \sum_{i<j} |A_i \cap A_j| - \cdots + (-1)^n |A_1 \cap \cdots \cap A_n|. \]
每项交集的符号由 \((-1)^{|S|+1}\) 决定（并集情形）或 \((-1)^{|S|}\)（补集情形），其中 \(|S|\) 是涉及的集合数。关键是"逐层修正"：先加单集合，减两两交（因为被加了两次），加三三交（因为被减了过多），依此类推。
计数 1 到 300 中能被 2、3 或 5 中至少一个整除的正整数个数。
设 \(A_p = \{m \in \{1,\ldots,300\} : p \mid m\}\)。则：
\[ |A_2| = \lfloor 300/2 \rfloor = 150, \quad |A_3| = 100, \quad |A_5| = 60. \]
两两交（即被最小公倍数整除）：
\[ |A_2 \cap A_3| = |A_6| = 50, \quad |A_2 \cap A_5| = |A_{10}| = 30, \quad |A_3 \cap A_5| = |A_{15}| = 20. \]
三者交：
\[ |A_2 \cap A_3 \cap A_5| = |A_{30}| = 10. \]
由 PIE：
\[ |A_2 \cup A_3 \cup A_5| = (150+100+60) - (50+30+20) + 10 = 310 - 100 + 10 = 220. \]
组合证明（combinatorial proof） 的核心思想是：对一个有限集合用两种不同方式计数，得到两个表达式，它们必相等。它不依赖代数展开，而是给出组合直觉。
标准技术： 1. 两种计数法：为同一组合对象构造两种计数过程。 2. 双射法：在两个集合间建立双射，说明它们等势。
Pascal 恒等式。 对 \(1 \le k \le n\)：
\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. \]
组合解释：从 \(n\) 人中选 \(k\) 人组队。固定某人 Alice，分两类：含 Alice 的队（再从其余 \(n-1\) 人选 \(k-1\) 人）和不含 Alice 的队（从其余 \(n-1\) 人选 \(k\) 人）。
Hockey-stick 恒等式。 对 \(0 \le k \le n\)：
\[ \sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1}. \]
用组合证明验证 hockey-stick 恒等式。 设 \(n=5, k=2\)：
\[ \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} = 1 + 3 + 6 + 10 = 20 = \binom{6}{3}. \]
一般证明。 考虑集合 \(\{1, 2, \ldots, n+1\}\) 的所有 \(k+1\) 元子集。右边 \(\binom{n+1}{k+1}\) 直接计数。
对左边，按子集的最大元分类。若最大元为 \(i+1\)（其中 \(i \ge k\)），则其余 \(k\) 个元素必须从 \(\{1, \ldots, i\}\) 中选取，有 \(\binom{i}{k}\) 种。\(i\) 的取值范围是 \(k\) 到 \(n\)，因此：
\[ \sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1}. \]
两种计数法结果相同，恒等式得证。
在整数格点 \(\mathbb{Z}^2\) 上，从 \((0,0)\) 移动到 \((m,n)\)，每步只能向右 \((x+1,y)\) 或向上 \((x,y+1)\)。最短路径恰好含 \(m\) 步右移和 \(n\) 步上移，共 \(m+n\) 步。
路径数公式。 在 \(m+n\) 步中选出哪 \(n\) 步为上移（或哪 \(m\) 步为右移）：
\[ \#\{\text{最短路径 } (0,0) \to (m,n)\} = \binom{m+n}{n} = \binom{m+n}{m}. \]
跨越对角线的路径。 考虑从 \((0,0)\) 到 \((n,n)\) 且始终满足 \(y \le x\)（不跨越对角线 \(y=x\)）的路径。这类"合法路径"的计数需要反射原理。
计算从 \((0,0)\) 到 \((4,4)\) 的最短路径总数，以及其中跨越对角线 \(y=x\) 的路径数。
总路径数：\(\binom{8}{4} = 70\)。
反射原理指出：跨越对角线的路径与从 \((0,0)\) 到 \((3,5)\) 的路径之间存在双射。构造如下：对一条跨越 \(y=x\) 的路径，设首次跨越发生在从 \((i,i)\) 走到 \((i,i+1)\) 的那一步；将此后所有步做反射（右移↔上移），则终点变为 \((n-1,n+1) = (3,5)\)。反之，任给一条到 \((3,5)\) 的路径，它必跨越 \(y=x\)，做同样的反射即回到跨越路径。这是一个双射。
因此跨越路径数 = 到 \((3,5)\) 的路径数 = \(\binom{8}{3} = 56\)。
n-legal 路径。 在 \(n\times n\) 网格中从 \((0,0)\) 到 \((n,n)\)、始终满足 \(y \le x\) 的最短路径，称为 n-legal 路径。设其数目为 \(F_n\)。
由反射原理，跨越对角线的路径数等于 \(\binom{2n}{n-1}\)，因此：
\[ F_n = \binom{2n}{n} - \binom{2n}{n-1}. \]
这正是第 \(n\) 个 Catalan 数 \(C_n = \frac{1}{n+1}\binom{2n}{n}\)。
递推关系。 设路径最后一次触及对角线 \(y=x\)（除终点外）的点是 \((i,i)\)，其中 \(0 \le i \le n-1\)。则：
从 \((0,0)\) 到 \((i,i)\) 的子路径是 i-legal 路径：\(F_i\) 种；
从 \((i+1,i)\) 到 \((n,n-1)\) 的子路径（平移后）是 \((n-1-i)\)-legal 路径：\(F_{n-1-i}\) 种。
因此这类路径数为 \(F_i \cdot F_{n-1-i}\)。对所有可能的 \(i\) 求和：
\[ F_n = \sum_{i=0}^{n-1} F_i \cdot F_{n-1-i}, \quad F_0 = 1. \]
与树的双射。 满足"非根节点度 ≤ 3、根节点度 ≤ 2"的 \(n\) 节点有序树，按左子树大小分类，恰好满足相同递推 \(T_n = \sum_{i=0}^{n-1} T_i T_{n-1-i}\)。这说明迷宫计数与树计数共享 Catalan 结构。
计算 \(F_0, F_1, F_2, F_3\) 并验证递推。
\(F_0 = 1\)（空路径）；
\(F_1 = 1\)：只有右→上；
\(F_2 = F_0 F_1 + F_1 F_0 = 1\cdot 1 + 1\cdot 1 = 2\)；
\(F_3 = F_0 F_2 + F_1 F_1 + F_2 F_0 = 1\cdot 2 + 1\cdot 1 + 2\cdot 1 = 5\)。
验证 \(F_3\)：总路径 \(\binom{6}{3}=20\)，跨越路径 \(\binom{6}{2}=15\)，合法路径 \(20-15=5\)。一致。
当对象具有对称性时，"不同"的计数需在等价关系下进行——两个对象若可通过对称变换互相得到，则视为相同。
立方体面染色。 用 6 种不同颜色涂立方体的 6 个面。不考虑对称有 \(6!\) 种。立方体的旋转群有 24 个元素（选哪一面朝下：6 种；绕该轴旋转：4 种）。由于 6 色互异，非恒等旋转不能保持染色不变，作用是自由的（free action），故不同染色数为：
\[ \frac{6!}{24} = 30. \]
手镯染色。 \(n\) 颗珠子用 \(n\) 种不同颜色，旋转等价下：\(n!/n = (n-1)!\)。若同时允许翻转（反射等价），则除以 2：\((n-1)!/2\)。
标号图计数。 \(n\) 个标号顶点的无向简单图：\(\binom{n}{2}\) 条可能的边，每条可选可不选：
\[ 2^{\binom{n}{2}}. \]
完全图中的圈。 \(K_n\) 中长度为 \(k\)（\(3 \le k \le n\)）的圈：先选有序 \(k\) 元顶点序列 \(\frac{n!}{(n-k)!}\)，再除以 \(k\)（旋转等价）和 2（翻转等价）：
\[ \sum_{k=3}^{n} \frac{n!}{(n-k)! \cdot 2k}. \]
将 4 颗颜色全不同的珠子串成手镯，旋转与翻转都视为相同。求不同手镯数。
不考虑对称有 \(4! = 24\) 种排列。二面体群 \(D_4\) 有 \(2n = 8\) 个元素（\(n\) 旋转 + \(n\) 翻转）。由于颜色全异，只有恒等变换保持排列不变，作用自由，故：
\[ \# = \frac{24}{8} = 3. \]
可枚举验证：固定一颗珠子的颜色，其对面有 3 种选色，剩下两颗互换由翻转等价，故恰 3 种。
无连续零的二进制串。 设 \(a_t\) 为长度为 \(t\)、不含两个连续 0 的二进制串个数。考虑末位：
末位为 1：前 \(t-1\) 位任意合法串，\(a_{t-1}\) 种；
末位为 0：倒数第二位必为 1，前 \(t-2\) 位任意合法串，\(a_{t-2}\) 种。
因此 \(a_t = a_{t-1} + a_{t-2}\)。初值 \(a_1 = 2\)（0, 1），\(a_2 = 3\)（01, 10, 11）。与 Fibonacci 数列 \(F_0=0, F_1=1\) 对比得：
\[ a_t = F_{t+2}. \]
Fashion 模型。 \(n\) 件配饰、\(t\) 天，要求同一配饰不能连续两天穿戴。对每件配饰 \(i\)，构造长度为 \(t\) 的二进制串：第 \(k\) 位为 0 表示第 \(k\) 天穿戴。"不连续穿戴" ⇔ "串中无连续 0"。各配饰独立，故总方案数：
\[ (F_{t+2})^n. \]
这与直接计数（逐步选子集）的结果一致，给出组合恒等式：
\[ \sum_{x_1,\ldots,x_t \ge 0} \binom{n}{x_1}\binom{n-x_1}{x_2}\cdots\binom{n-x_{t-1}}{x_t} = (F_{t+2})^n. \]
\(t=5\) 天、\(n=3\) 件配饰，求合法方案数。
先算 \(F_{t+2} = F_7\)：\(F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13\)。
每件配饰有 \(F_7 = 13\) 种合法穿戴模式（长度为 5 的无连续零二进制串），三件独立：
\[ 13^3 = 2197. \]
验证 \(t=5\) 时的串数：末位为 1 ⇒ \(a_4 = F_6 = 8\)；末位为 0 ⇒ \(a_3 = F_5 = 5\)；合计 \(8+5=13\)。正确。
这只在球可区分且盒子可区分时成立。若球不可区分，应用 stars and bars 得 \(\binom{k+n-1}{n-1}\)。模型前提决定公式。
仅加单集合会重复计数交集部分。PIE 要求交替加减各阶交集：加单集、减两两交、加三三交……直到 n 重交。
组合证明要求对同一有限集合给出两种独立的计数过程（或构造双射），而非代数操作。它的价值在于提供组合直觉。
反射只作用于首次跨越对角线之后的路径段，而非整条路径。整条反射会改变起点，无法保持 (0,0) 不动，也就不是 (0,0)→(n,n) 路径之间的映射。
除以对称数的前提是群作用是自由的（无不动点）。若某些对象有非平凡对称性（如某些染色在旋转下不变），则需用 Burnside 引理 \(\frac{1}{|G|}\sum_{g}|X^g|\) 而非简单除法。
问题：将 12 个完全相同的球放入 4 个不同的盒子，允许有空盒，共有多少种放法？
问题：1 到 100 中既不被 3 整除也不被 7 整除的正整数有多少个？
问题：从 (0,0) 到 (5,5) 的最短路径中，始终不跨越对角线 y=x 的路径数目为：
discussion/dis06b.pdf · 1 · confidence: high · This is a classic 'balls and bins' (also known as 'stars and bars') problem... k stars and n−1 bars, giving us C(k+1, 1)discussion/dis06b.pdf · 1 · confidence: high · If a number is not coprime to 100, this means that the number is either a multiple of 2 or a multiple of 5... By inclusion-exclusion, the total number... is 49 + 19 − 9 = 59discussion/dis06b.pdf · 2-3 · confidence: high · LHS: This is simply the number of ways to choose k crew members out of n candidates. RHS: ... First, Edward looks at the first candidate...homework/hw07.pdf · 2-3 · confidence: high · There are C(2n, n) paths, as there are total number of 2n moves, and n of them must be move 'right' commandhomework/hw07.pdf · 3 · confidence: high · Fn = ∑_{i=0}^{n-1} Fi · Fn−1−i ... Tn = ∑_{i=0}^{n-1} TiTn−i−1 ... a similar counting argument captures totally different objects (mazes and trees)!homework/hw07.pdf · 4 · confidence: high · Without considering symmetries there are 6! ways to color the faces of the cube... 24 = 6 × 4 ... 6!/24 = 30 distinct coloringshomework/hw07.pdf · 6-7 · confidence: high · For t ≥ 1, prove that there are F_{t+2} binary strings of length t with no consecutive zeros