第6章计数 (Counting)

一、导读

1.1 本章学习目标

完成本章学习后，你将能够：

掌握基本计数原理：加法原理和乘法原理

理解排列和组合的定义、公式及其应用场景

熟练计算带重复元素的排列和组合问题

掌握二项式定理及其在展开式和系数计算中的应用

理解鸽巢原理并能用它证明存在性命题

掌握容斥原理计算集合并集的大小

能够识别和解决常见的计数陷阱（如重复计数）

将计数技术应用于算法复杂度分析和概率计算

理解生成函数在计数问题中的高级应用

掌握递推关系与计数的联系

1.2 为什么本章如此重要

计数是计算机科学中的基础技能，从分析算法效率到评估系统安全性都离不开它。

在算法分析中：比较排序的次数、图的边数、哈希表的冲突概率都需要计数技术。例如，快速排序的平均比较次数为 $2n\ln n$，这需要通过计数和概率分析得出。归并排序的递归树有 $\log_2 n$ 层，每层需要 $n$ 次比较，总比较次数为 $n\log_2 n$。

在密码学中：密钥空间的大小决定了暴力破解的难度。一个8位字符密码（大小写字母+数字）有 $62^8 \approx 2\times10^{14}$ 种可能。如果攻击者每秒可以尝试 $10^9$ 个密码，仍需要约6年才能穷举所有可能。AES-128的密钥空间为 $2^{128} \approx 3.4\times10^{38}$，即使使用地球上所有计算机也需要远超宇宙年龄的时间才能破解。

在数据结构中：二叉树的数量、图的数量、合法括号序列的数量都与计数密切相关。n个节点的不同二叉树数量为卡特兰数 $C_n = \frac{1}{n+1}\binom{2n}{n}$。n个节点的无向简单图有 $2^{\binom{n}{2}}$ 种可能。

在概率论中：计算事件概率需要知道有利结果数和总结果数。古典概型中，如果样本空间有N个等可能结果，事件A包含M个结果，则 $P(A) = M/N$。

在编译器设计中：语法分析需要考虑所有可能的解析树数量。歧义文法可能产生指数级数量的解析树，导致编译时间爆炸。

在日常编程中：生成测试用例、枚举配置组合、优化缓存策略都涉及计数。例如，如果有5个布尔配置项，共有 $2^5 = 32$ 种配置组合需要测试。

在机器学习中：特征组合的数量随特征数指数增长。如果有100个二元特征，两两组合就有 $\binom{100}{2} = 4950$ 种可能，这被称为"维度灾难"。

1.3 核心问题引导

在学习本章之前，请思考以下问题：

从5个人中选3个人组成委员会，有多少种选法？如果还要选主席呢？

为什么"生日悖论"中说23个人中就有50%的概率两人同生日？

有多少种方式将n个不同的球放入k个相同的盒子？

二项式系数 C(n,k) 为什么等于 C(n, n-k)？

鸽巢原理看似显然，它能证明什么有趣的结论？

如何计算至少满足多个条件之一的事物数量？

卡特兰数出现在哪些看似不相关的问题中？

为什么计数问题容易出错？如何避免重复或遗漏？

什么是"星与棒"方法？它如何解决分配问题？

错排问题（Derangement）有什么实际应用？

二、核心概念详解

6.1 基本计数原理

加法原理

如果完成一件事有m种方法，另一件事有n种方法，且这两件事不能同时做，则完成其中一件事共有 m + n 种方法。

形式化：如果A和B是不相交的有限集合，则 |A ∪ B| = |A| + |B|。

示例：从北京到上海，可以坐高铁（5个班次）或飞机（3个航班），共有 5 + 3 = 8 种选择。

推广：对于两两不相交的集合 A₁, A₂, ..., Aₙ：

$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i=1}^{n} |A_i|$$

关键要点：加法原理适用于"互斥选择"的情况。如果选择之间有重叠，需要使用容斥原理。

实际例子：某大学有计算机系学生120人，数学系学生80人，双学位学生30人。问至少修读其中一个专业的学生人数是多少？

解：设A为计算机系学生集合，B为数学系学生集合。|A| = 120, |B| = 80, |A∩B| = 30。

由容斥原理：|A ∪ B| = |A| + |B| - |A∩B| = 120 + 80 - 30 = 170人。

乘法原理

如果完成一件事需要两个步骤，第一步有m种方法，第二步有n种方法，则完成这件事共有 m × n 种方法。

形式化：如果|A| = m, |B| = n，则 |A × B| = mn。

示例：一个密码由1个大写字母和2个数字组成，共有 26 × 10 × 10 = 2600 种可能。

推广：对于n个步骤，第i步有kᵢ种方法，则总方法数为 k₁ × k₂ × ... × kₙ。

关键区别：加法原理用于"或"的情况（选择其一），乘法原理用于"且"的情况（依次完成）。

深入理解：乘法原理的本质是笛卡尔积的基数。如果任务可以分解为独立的子任务，总方案数是各子任务方案数的乘积。

实际例子：一个餐厅提供3种主菜、5种配菜和2种饮料。顾客需要选择一份主菜、一份配菜和一份饮料。共有多少种不同的套餐组合？

解：由乘法原理，共有 3 × 5 × 2 = 30 种套餐组合。

复杂例子：考虑一个4位PIN码，每位可以是0-9的数字。如果要求至少有一位是重复的，有多少种可能？

解：总PIN码数量为 $10^4 = 10000$。没有重复数字的PIN码数量为 $P(10,4) = 10 \times 9 \times 8 \times 7 = 5040$。因此至少有一位重复的PIN码数量为 $10000 - 5040 = 4960$。

这里使用了补集思想：直接计算"至少有一个重复"比较困难，但计算"没有重复"很容易，然后用总数减去即可。

6.2 排列

定义

排列是从n个不同元素中取出r个元素并按顺序排列的方式数。

记作 P(n, r) 或 ⁿPᵣ。

公式

$$P(n, r) = n \times (n-1) \times (n-2) \times ... \times (n-r+1) = \frac{n!}{(n-r)!}$$

推导：第一个位置有n种选择，第二个位置有n-1种选择，...，第r个位置有n-r+1种选择。由乘法原理，总数为 n(n-1)...(n-r+1)。

示例：从5个人中选3人排成一排，有 P(5,3) = 5×4×3 = 60 种方式。

特殊情况

全排列：r = n，P(n, n) = n!
圆排列：n个元素围成一圈，有 (n-1)! 种方式（因为旋转等价）
项链排列：n个元素串成项链，有 (n-1)!/2 种方式（因为翻转也等价）

圆排列的解释：固定一个人的位置作为参考点，剩下n-1个人的排列方式为 (n-1)!。这是因为圆排列中，旋转后的排列被视为相同。

项链排列的解释：在圆排列的基础上，翻转也被视为相同，所以需要再除以2。

带重复元素的排列

如果n个元素中有n₁个相同类型1，n₂个相同类型2，...，nₖ个相同类型k，则不同排列数为：

$$\frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}$$

示例："MISSISSIPPI"有11个字母，其中M:1, I:4, S:4, P:2。不同排列数为 11!/(1!×4!×4!×2!) = 34650。

推导过程：如果所有字母都不同，有11!种排列。但由于I重复4次，每种实际排列被计算了4!次；S重复4次，被计算了4!次；P重复2次，被计算了2!次。所以需要除以这些重复因子。

另一个例子：用数字1,1,2,2,3能组成多少个不同的5位数？

解：共有5个数字，其中1重复2次，2重复2次。不同排列数为 $5!/(2! \times 2!) = 120/4 = 30$。

循环排列

定义：将n个不同元素分成若干个循环的排列方式数由第一类斯特林数 s(n,k) 给出，表示将n个元素分成k个非空循环的方式数。

性质：$\sum_{k=1}^{n} s(n,k) = n!$（所有循环排列的总数等于全排列数）

递推关系：$s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)$

解释：考虑第n个元素，要么单独形成一个循环（贡献s(n-1,k-1)），要么插入到已有的某个循环中（有n-1个插入位置，贡献(n-1)s(n-1,k)）。

6.3 组合

定义

组合是从n个不同元素中取出r个元素的方式数，不考虑顺序。

记作 C(n, r)、ⁿCᵣ 或 $\binom{n}{r}$（二项式系数）。

公式

$$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

推导：从n个元素中选r个并排列有 P(n,r) 种方式。但每种组合对应 r! 种排列（r个元素的排列数）。所以 C(n,r) = P(n,r)/r! = n!/[r!(n-r)!]。

性质

性质	公式
对称性	$\binom{n}{r} = \binom{n}{n-r}$
帕斯卡恒等式	$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$
边界值	$\binom{n}{0} = \binom{n}{n} = 1$
总和	$\sum_{r=0}^{n} \binom{n}{r} = 2^n$
交替和	$\sum_{r=0}^{n} (-1)^r \binom{n}{r} = 0$（当n>0时）
平方和	$\sum_{r=0}^{n} \binom{n}{r}^2 = \binom{2n}{n}$

对称性解释：从n个元素中选r个留下，等价于选n-r个拿走。这个性质在计算时可以减少工作量，例如计算 $\binom{100}{98}$ 时，可以改为计算 $\binom{100}{2}$。

帕斯卡恒等式解释：考虑某个特定元素x。包含x的组合有 C(n-1, r-1) 种（从剩下n-1个中选r-1个）；不包含x的组合有 C(n-1, r) 种。两者之和为 C(n, r)。这个恒等式也是杨辉三角（帕斯卡三角形）的构造原理。

总和的解释：从n个元素中选择任意子集的方式数等于 $2^n$（每个元素可选或不选）。这也等于所有可能的选择大小的组合数之和。

平方和的证明思路：考虑从2n个元素（n个红球和n个蓝球）中选n个球的方式数。可以选0个红球和n个蓝球，或1个红球和n-1个蓝球，...，或n个红球和0个蓝球。总方式数为 $\sum_{r=0}^{n} \binom{n}{r}\binom{n}{n-r} = \sum_{r=0}^{n} \binom{n}{r}^2$，这也等于 $\binom{2n}{n}$。

组合恒等式

范德蒙德恒等式：

$$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$

解释：从m个红球和n个蓝球中选r个球。可以选k个红球和r-k个蓝球，k从0到r求和。

证明：考虑 $(1+x)^{m+n} = (1+x)^m (1+x)^n$ 的展开式中 $x^r$ 的系数。左边 $x^r$ 的系数为 $\binom{m+n}{r}$。右边 $x^r$ 的系数为 $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$。因此两者相等。

吸收恒等式：

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

证明：$k\binom{n}{k} = k \cdot \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = n \cdot \frac{(n-1)!}{(k-1)!(n-k)!} = n\binom{n-1}{k-1}$

应用：这个恒等式在计算期望值时非常有用。例如，二项分布的期望值 $E[X] = \sum_{k=0}^{n} k\binom{n}{k}p^k(1-p)^{n-k} = np$。

"星与棒"方法（Stars and Bars）

问题：将n个相同的球放入k个不同的盒子，允许空盒，有多少种方式？

解法：使用n个星（★）表示球，k-1个棒（|）分隔盒子。例如，★★|★||★★表示第1盒2个、第2盒1个、第3盒0个、第4盒2个。

总共有n个星和k-1个棒，共n+k-1个位置。选择k-1个位置放棒（或选择n个位置放星）的方式数为 $\binom{n+k-1}{k-1} = \binom{n+k-1}{n}$。

变体1：不允许空盒。先给每个盒子放1个球，剩下n-k个球自由分配。方式数为 $\binom{n-1}{k-1}$。

变体2：每个盒子至少有aᵢ个球。先满足最低要求，剩下的自由分配。

示例：方程 x₁ + x₂ + x₃ = 10 的非负整数解有多少个？

解：这是将10个相同的球放入3个不同盒子的问题。方式数为 $\binom{10+3-1}{3-1} = \binom{12}{2} = 66$。

示例：方程 x₁ + x₂ + x₃ = 10 的正整数解（xᵢ ≥ 1）有多少个？

解：令 yᵢ = xᵢ - 1 ≥ 0，则 y₁ + y₂ + y₃ = 7。方式数为 $\binom{7+3-1}{3-1} = \binom{9}{2} = 36$。

6.4 二项式定理

定理

$$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$$

证明思路

展开 (x+y)ⁿ 时，每项是从n个因子中各选x或y相乘。选k个y和n-k个x的方式数是 C(n,k)，对应项为 C(n,k)x^(n-k)y^k。

详细证明：考虑 $(x+y)^n = (x+y)(x+y)\cdots(x+y)$（共n个因子）。展开时，每一项都是从每个因子中选择x或y然后相乘。如果从k个因子中选择y，从n-k个因子中选择x，得到的项为 $x^{n-k}y^k$。选择k个因子的方式数为 $\binom{n}{k}$。对所有可能的k求和即得定理。

特例

令 x = y = 1：$2^n = \sum_{k=0}^{n} \binom{n}{k}$
令 x = 1, y = -1：$0 = \sum_{k=0}^{n} \binom{n}{k}(-1)^k$
令 x = 1, y = 1：$2^n = \sum_{k=0}^{n} \binom{n}{k}$（同上）
令 x = 2, y = 1：$3^n = \sum_{k=0}^{n} \binom{n}{k} 2^{n-k}$

第二个特例的解释：$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ 表明奇数项组合数之和等于偶数项组合数之和，都等于 $2^{n-1}$。

应用

示例：展开 (x+2)⁴

$$(x+2)^4 = \binom{4}{0}x^4 + \binom{4}{1}x^3(2) + \binom{4}{2}x^2(2^2) + \binom{4}{3}x(2^3) + \binom{4}{4}(2^4)$$

$$= x^4 + 8x^3 + 24x^2 + 32x + 16$$

示例：求 $(1+x)^{10}$ 展开式中 $x^3$ 的系数。

解：系数为 $\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$。

示例：证明 $\sum_{k=0}^{n} k\binom{n}{k} = n2^{n-1}$。

证明：对 $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k}x^k$ 两边关于x求导：

$n(1+x)^{n-1} = \sum_{k=1}^{n} k\binom{n}{k}x^{k-1}$

令 x = 1：

$n \cdot 2^{n-1} = \sum_{k=1}^{n} k\binom{n}{k} = \sum_{k=0}^{n} k\binom{n}{k}$

多项式定理（二项式定理的推广）：

$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} \frac{n!}{k_1!k_2!\cdots k_m!} x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}$$

其中求和遍历所有满足 $k_1 + k_2 + \cdots + k_m = n$ 的非负整数组合。

6.5 鸽巢原理

简单形式

如果将 n+1 个物体放入 n 个盒子，则至少有一个盒子包含至少 2 个物体。

证明（反证法）：假设每个盒子最多有1个物体，则总物体数最多为n，与有n+1个物体矛盾。∎

推广形式

如果将 N 个物体放入 n 个盒子，则至少有一个盒子包含至少 ⌈N/n⌉ 个物体。

证明（反证法）：假设每个盒子最多有 ⌈N/n⌉ - 1 个物体。由于 ⌈N/n⌉ - 1 < N/n，总物体数最多为 n × (N/n - 1) < N，矛盾。∎

示例：367人中至少有2人生日相同（因为只有366天）。

示例：在1到100中任选51个数，必有两个数互质。

证明：将1到100分为50对：(1,2), (3,4), ..., (99,100)。选51个数，由鸽巢原理，必有一对中的两个数都被选中。相邻的两个数互质（因为它们的最大公约数整除它们的差1）。∎

应用示例

问题：证明在任何6个人中，要么有3个人互相认识，要么有3个人互不认识。

证明：考虑某个人A。A与其他5个人的关系要么是"认识"要么是"不认识"。由鸽巢原理，A至少认识⌈5/2⌉=3人，或至少不认识3人。

假设A认识B、C、D三人。如果B、C、D中有任何两人互相认识（如B和C），则A、B、C三人互相认识。如果B、C、D互不认识，则B、C、D三人互不认识。

另一种情况类似。因此命题成立。∎

这是拉姆齐理论的一个简单例子。拉姆齐数 R(3,3) = 6 表示在6个顶点的完全图中，无论如何着色边，必然存在单色三角形。

更多应用：

哈希冲突：如果有n个桶和n+1个键，必然发生冲突。这就是为什么哈希表需要动态扩容。

文件压缩的下界：任何无损压缩算法都不能将所有文件压缩得更小。因为如果所有n位文件都能压缩成少于n位，则由鸽巢原理，两个不同文件会压缩成相同结果，无法无损解压。

子集和问题：从{1,2,...,2n}中任选n+1个数，必有两个数，其中一个整除另一个。

证明：每个数可以写成 $2^k \times m$ 的形式，其中m是奇数。{1,2,...,2n}中有n个奇数（1,3,5,...,2n-1）。选n+1个数，由鸽巢原理，必有两个数有相同的奇数部分m。设这两个数为 $2^{k_1}m$ 和 $2^{k_2}m$。如果 $k_1 < k_2$，则前者整除后者。∎

中国剩余定理的应用：在任意n+1个整数中，必有两个数的差能被n整除。

证明：考虑这n+1个数模n的余数。余数只能是0,1,...,n-1共n种。由鸽巢原理，必有两个数有相同的余数，它们的差能被n整除。∎

6.6 容斥原理

两个集合

解释：直接相加会重复计算交集部分，需要减去一次。

三个集合

模式解释：单个集合的和（加）- 两两交集的和（减）+ 三三交集的和（加）。符号交替变化。

一般形式

对于n个集合：

$$\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| - ... + (-1)^{n+1}\left|\bigcap_{i=1}^{n} A_i\right|$$

模式：单个集合的和 - 两两交集的和 + 三三交集的和 - ...

记忆技巧：符号由交集中集合数量的奇偶性决定。奇数个集合的交集为正，偶数个为负。

证明思路：考虑元素x属于k个集合。x在左边的并集中被计算1次。在右边，x在单个集合的和中被计算k次，在两两交集中被计算 $\binom{k}{2}$ 次，...。总的计算次数为：

$$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots + (-1)^{k+1}\binom{k}{k} = 1 - (1-1)^k = 1$$

（当k ≥ 1时）

应用示例

问题：1到100中有多少个数能被2、3或5整除？

解：设A=被2整除的数，B=被3整除的数，C=被5整除的数。

|A| = ⌊100/2⌋ = 50

|B| = ⌊100/3⌋ = 33

|C| = ⌊100/5⌋ = 20

|A∩B| = ⌊100/6⌋ = 16

|A∩C| = ⌊100/10⌋ = 10

|B∩C| = ⌊100/15⌋ = 6

|A∩B∩C| = ⌊100/30⌋ = 3

|A ∪ B ∪ C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74

相关问题：1到100中有多少个数不能被2、3或5整除？

解：100 - 74 = 26个。

更复杂的例子：欧拉函数 φ(n) 表示不超过n且与n互质的正整数个数。

如果 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，则：

$$\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_k}\right)$$

推导：设Aᵢ为1到n中能被pᵢ整除的数。我们要求不在任何Aᵢ中的数的个数。

由容斥原理：

$$\phi(n) = n - \sum_i |A_i| + \sum_{i<j} |A_i \cap A_j| - \cdots$$

$$= n - \sum_i \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_i p_j} - \cdots$$

$$= n \left(1 - \sum_i \frac{1}{p_i} + \sum_{i<j} \frac{1}{p_i p_j} - \cdots\right)$$

$$= n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$$

示例：φ(60) = φ(2²×3×5) = 60 × (1-1/2) × (1-1/3) × (1-1/5) = 60 × 1/2 × 2/3 × 4/5 = 16。

验证：1到60中与60互质的数为 1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59，共16个。✓

错排问题（Derangement）

问题：n封信装入n个信封，每封信都装错的装法有多少种？

解：设Dₙ为错排数。设Aᵢ为第i封信装对的排列集合。我们要求不在任何Aᵢ中的排列数。

由容斥原理：

$$D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n \binom{n}{n}0!$$

$$= n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$$

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

当n很大时，$D_n \approx \frac{n!}{e}$（因为 $e^{-1} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!}$）。

前几个错排数：D₀=1, D₁=0, D₂=1, D₃=2, D₄=9, D₅=44, D₆=265。

递推关系：$D_n = (n-1)(D_{n-1} + D_{n-2})$

解释：考虑第1封信。它可以装入第2,3,...,n号信封中的任意一个（n-1种选择）。假设装入第k号信封。有两种情况：

第k封信装入第1号信封：剩下n-2封信的错排数为D_{n-2}
第k封信不装入第1号信封：这等价于n-1封信的错排（将第1号信封视为第k封信的"正确"信封），错排数为D_{n-1}

应用：错排问题在实际中有多种应用，如秘密圣诞老人游戏（每个人给别人送礼，但不能给自己）、匹配问题等。

6.7 特殊计数序列

卡特兰数

卡特兰数 Cₙ = $\frac{1}{n+1}\binom{2n}{n}$ 出现在许多看似不相关的问题中：

n对括号的合法匹配方式数
n+1个叶子的满二叉树数量
凸n+2边形的三角剖分数
栈的合法操作序列数
从(0,0)到(n,n)不越过对角线的格路路径数
1,2,...,n的栈可排序排列数

前几个卡特兰数：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

递推关系：$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$，其中 C₀ = 1。

解释：考虑n对括号的合法序列。第一个左括号必须与某个右括号匹配。假设它与第2k+2个位置的右括号匹配（k从0到n-1）。则中间有k对括号，后面有n-1-k对括号。总方式数为 $\sum_{k=0}^{n-1} C_k C_{n-1-k}$。

格路路径解释：从(0,0)到(n,n)，只能向右或向上走，且不越过对角线y=x的路径数为Cₙ。

证明：总路径数为 $\binom{2n}{n}$。越过对角线的路径数等于从(0,0)到(n-1,n+1)的路径数（通过反射原理），即 $\binom{2n}{n-1}$。因此不越过对角线的路径数为 $\binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n} = C_n$。

示例：4对括号的合法序列有C₄=14种：

()()()(), ()()(()) , ()(()()), ()((())), (())()(), (())(()) , (()()()), (()(())), ((()))(), ((())()), ((()())), (((())))

斯特林数

第一类斯特林数 s(n,k)：将n个元素分成k个非空循环排列的方式数。

性质：

s(n,1) = (n-1)!（n个元素的循环排列数）
s(n,n) = 1
s(n,n-1) = $\binom{n}{2}$
$\sum_{k=1}^{n} s(n,k) = n!$

递推关系：$s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)$

第二类斯特林数 S(n,k)：将n个不同元素分成k个非空不可区分集合的方式数。

性质：

S(n,1) = 1
S(n,n) = 1
S(n,2) = $2^{n-1} - 1$
S(n,n-1) = $\binom{n}{2}$

递推关系：$S(n,k) = kS(n-1,k) + S(n-1,k-1)$

解释：考虑第n个元素。要么它单独形成一个集合（贡献S(n-1,k-1)），要么它加入已有的k个集合中的一个（贡献kS(n-1,k)）。

与贝尔数的关系：$B_n = \sum_{k=0}^{n} S(n,k)$

显式公式：$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$

应用：第二类斯特林数出现在将n个不同的球放入k个相同的盒子（不允许空盒）的问题中。

贝尔数

Bₙ 是将n个元素划分为若干非空子集的方式数。

$B_n = \sum_{k=0}^{n} S(n, k)$

前几个贝尔数：1, 1, 2, 5, 15, 52, 203, 877, 4140, ...

递推关系：$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$

解释：考虑包含第n+1个元素的集合。假设有k个其他元素与它在同一个集合中（k从0到n）。选择这k个元素的方式数为 $\binom{n}{k}$，剩下n-k个元素的划分方式数为 $B_{n-k}$。重新索引后得到上述递推关系。

贝尔三角形：类似于帕斯卡三角形，可以用于计算贝尔数。

应用：贝尔数出现在集合聚类、等价关系计数等问题中。n个元素上的等价关系数等于Bₙ。

斐波那契数列

虽然斐波那契数列通常与递推关系关联，但它也是一个重要的计数序列。

Fₙ 表示：

1×n的棋盘用1×1和1×2的骨牌铺满的方式数
不含连续1的长度为n的二进制串的数量
n阶楼梯每次走1步或2步的走法数

通项公式（比内公式）：

$$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

6.8 生成函数入门

定义：序列 {aₙ} 的普通生成函数是形式幂级数 $A(x) = \sum_{n=0}^{\infty} a_n x^n$。

基本生成函数：

常数序列 1,1,1,...：$\frac{1}{1-x}$
自然数 1,2,3,...：$\frac{1}{(1-x)^2}$
二项式系数 $\binom{n}{0}, \binom{n}{1}, ...$：$(1+x)^n$
斐波那契数列：$\frac{x}{1-x-x^2}$

运算性质：

加法：对应序列逐项相加
乘法（卷积）：$[x^n]A(x)B(x) = \sum_{k=0}^{n} a_k b_{n-k}$
微分：$A'(x)$ 对应序列 $\{na_n\}$

应用示例：求掷两个六面骰子得到和为7的方式数。

单个骰子的生成函数为 $x + x^2 + x^3 + x^4 + x^5 + x^6$。

两个骰子的生成函数为 $(x + x^2 + \cdots + x^6)^2$。

$x^7$ 的系数即为所求。展开后可得系数为6，对应6种方式：(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)。

三、程序员的视角

3.1 在计算机科学中的应用

算法复杂度

冒泡排序的比较次数：C(n,2) = n(n-1)/2
完全图的边数：C(n,2)
二叉搜索树的数量：卡特兰数
快速排序的平均比较次数：约 $2n\ln n$
归并排序的递归深度：$\log_2 n$

密码学

密钥空间大小：

8位ASCII密码：256⁸ ≈ 10¹⁹
UUID v4：2¹²² ≈ 10³⁶
AES-128：2¹²⁸ ≈ 3.4×10³⁸
RSA-2048：约 2²⁰⁴⁸

生日攻击：找到哈希碰撞需要约 $\sqrt{2^n} = 2^{n/2}$ 次尝试。因此SHA-256的安全强度为128位（针对碰撞攻击）。

测试用例生成

组合测试：从n个参数中每次选k个进行组合测试。所需测试用例数为 C(n,k)。

配对测试（k=2）：确保每对参数的所有组合都被测试。如果有m个参数，每个参数有v个取值，则至少需要 $v^2$ 个测试用例。

数据库

连接操作的输出大小估计涉及计数。最坏情况下，两个大小为n和m的表的自然连接可能有 n×m 行。

查询优化：优化器需要估计不同执行计划的成本，这涉及基数估计（cardinality estimation）。

机器学习

特征工程：n个二元特征的两两交互产生 $\binom{n}{2}$ 个新特征。这可能导致维度灾难。

模型选择：如果有k个候选模型，使用交叉验证选择最佳模型需要考虑多重比较问题。

3.2 常见陷阱与误区

重复计数

计算"至少一个"的情况时，直接相加会重复计算重叠部分，应使用容斥原理。

例子：1到100中能被2或3整除的数。错误做法：50+33=83。正确做法：50+33-16=67。

顺序混淆

排列考虑顺序，组合不考虑。选委员会成员是组合，选主席和副主席是排列。

判断方法：问自己"交换两个被选中的元素会产生不同的结果吗？"如果是，用排列；否则用组合。

边界情况

C(n,0) = 1（空集是一种选择），不是0。

0! = 1（空乘积定义为1）。

常见错误：忘记考虑空集或全集的情况。

溢出问题

阶乘和组合数增长极快。C(100,50) ≈ 10²⁹，超出64位整数范围。

解决方案：

使用大整数库
在计算过程中进行约分
使用对数避免溢出

"至少"与"恰好"的混淆

"至少k个"通常比"恰好k个"更容易通过补集计算。

例子：抛10次硬币至少6次正面的概率 = 1 - (0到5次正面的概率之和)。

3.3 与其他层级的联系

硬件层：地址空间大小 = 2^(位数)；指令编码的组合数
操作系统层：进程调度排列数；内存页的组合分配
网络层：IP地址数量；路由表条目数
应用层：用户权限组合；配置选项的组合数

四、代码实战

6.1 计数工具实现

python

"""
计数工具：排列、组合、二项式系数
"""

import math
from functools import lru_cache


def factorial(n):
    """计算n的阶乘"""
    if n < 0:
        raise ValueError("阶乘未定义于负数")
    return math.factorial(n)


def permutation(n, r):
    """
    计算排列数 P(n, r)
    
    P(n, r) = n! / (n-r)!
    """
    if r > n or r < 0:
        return 0
    return factorial(n) // factorial(n - r)


def combination(n, r):
    """
    计算组合数 C(n, r) = binom(n, r)
    
    C(n, r) = n! / (r! * (n-r)!)
    """
    if r > n or r < 0:
        return 0
    return math.comb(n, r)


@lru_cache(maxsize=None)
def catalan(n):
    """
    计算第n个卡特兰数
    
    C_n = binom(2n, n) / (n+1)
    """
    if n <= 1:
        return 1
    return combination(2*n, n) // (n + 1)


def stirling_second_kind(n, k):
    """
    计算第二类斯特林数 S(n, k)
    
    将n个不同元素分成k个非空不可区分集合的方式数
    """
    if n == k == 0:
        return 1
    if n == 0 or k == 0:
        return 0
    if k > n:
        return 0
    
    # 递推关系: S(n,k) = k*S(n-1,k) + S(n-1,k-1)
    return k * stirling_second_kind(n-1, k) + stirling_second_kind(n-1, k-1)


def bell_number(n):
    """
    计算第n个贝尔数
    
    B_n = sum of S(n, k) for k = 0 to n
    """
    return sum(stirling_second_kind(n, k) for k in range(n + 1))


def derangement(n):
    """
    计算错排数 D_n
    
    D_n = n! * sum((-1)^k / k!, k=0..n)
    """
    if n == 0:
        return 1
    if n == 1:
        return 0
    
    # 使用递推关系: D_n = (n-1)(D_{n-1} + D_{n-2})
    d = [0] * (n + 1)
    d[0] = 1
    d[1] = 0
    
    for i in range(2, n + 1):
        d[i] = (i - 1) * (d[i-1] + d[i-2])
    
    return d[n]


def stars_and_bars(n, k, allow_empty=True):
    """
    星与棒方法：将n个相同的球放入k个不同的盒子
    
    参数:
        n: 球的数量
        k: 盒子的数量
        allow_empty: 是否允许空盒
    
    返回: 方式数
    """
    if allow_empty:
        # C(n+k-1, k-1)
        return combination(n + k - 1, k - 1)
    else:
        # 每个盒子至少1个球: C(n-1, k-1)
        if n < k:
            return 0
        return combination(n - 1, k - 1)


def demonstrate_counting():
    """演示计数函数"""
    
    print("=== 排列和组合 ===")
    
    n, r = 5, 3
    print(f"P({n}, {r}) = {permutation(n, r)}")
    print(f"C({n}, {r}) = {combination(n, r)}")
    print(f"验证: P({n},{r}) = C({n},{r}) × {r}! = {combination(n,r)} × {factorial(r)} = {combination(n,r) * factorial(r)}")
    
    print("\n=== 卡特兰数 ===")
    for n in range(10):
        print(f"  C_{n} = {catalan(n)}")
    
    print("\n=== 第二类斯特林数 ===")
    print("S(n, k) 表格:")
    print(f"{'n\\k':>4}", end="")
    for k in range(8):
        print(f"{k:>6}", end="")
    print()
    
    for n in range(8):
        print(f"{n:>4}", end="")
        for k in range(8):
            print(f"{stirling_second_kind(n, k):>6}", end="")
        print()
    
    print("\n=== 贝尔数 ===")
    for n in range(10):
        print(f"  B_{n} = {bell_number(n)}")
    
    print("\n=== 错排数 ===")
    for n in range(10):
        print(f"  D_{n} = {derangement(n)}")
    
    print("\n=== 星与棒 ===")
    print("将5个相同的球放入3个不同的盒子:")
    print(f"  允许空盒: {stars_and_bars(5, 3, True)}种")
    print(f"  不允许空盒: {stars_and_bars(5, 3, False)}种")


if __name__ == "__main__":
    demonstrate_counting()

6.2 鸽巢原理验证

python

"""
鸽巢原理应用和验证
"""

import random


def birthday_paradox_simulation(num_people=23, num_trials=10000):
    """
    模拟生日悖论
    
    返回: 至少两人生日相同的概率估计
    """
    matches = 0
    
    for _ in range(num_trials):
        birthdays = [random.randint(1, 365) for _ in range(num_people)]
        if len(birthdays) != len(set(birthdays)):  # 有重复
            matches += 1
    
    return matches / num_trials


def pigeonhole_principle_demo():
    """演示鸽巢原理的应用"""
    
    print("=== 生日悖论 ===")
    print("理论值和模拟值比较:")
    print(f"{'人数':>6} {'理论概率':>12} {'模拟概率':>12}")
    print("-" * 35)
    
    for n in [10, 20, 23, 30, 50]:
        # 理论概率: 1 - 365!/(365-n)!/365^n
        prob_no_match = 1.0
        for i in range(n):
            prob_no_match *= (365 - i) / 365
        theoretical_prob = 1 - prob_no_match
        
        simulated_prob = birthday_paradox_simulation(n, 5000)
        
        print(f"{n:>6} {theoretical_prob:>12.4f} {simulated_prob:>12.4f}")
    
    print("\n=== 鸽巢原理简单应用 ===")
    
    # 13个人中至少有2人生日在同一月份
    people = 13
    months = 12
    print(f"{people}个人，{months}个月")
    print(f"由鸽巢原理，至少有 ⌈{people}/{months}⌉ = {(people + months - 1) // months} 人生日在同一月份")
    
    # 验证
    for _ in range(3):
        birth_months = [random.randint(1, 12) for _ in range(people)]
        month_counts = {}
        for m in birth_months:
            month_counts[m] = month_counts.get(m, 0) + 1
        max_count = max(month_counts.values())
        print(f"  随机模拟: 最大同月人数 = {max_count}")
    
    print("\n=== 子集和整除问题 ===")
    print("从{1,2,...,20}中选11个数，必有两个数，其中一个整除另一个")
    
    # 验证
    for trial in range(5):
        subset = random.sample(range(1, 21), 11)
        subset.sort()
        
        found = False
        for i in range(len(subset)):
            for j in range(i+1, len(subset)):
                if subset[j] % subset[i] == 0:
                    print(f"  找到: {subset[i]} 整除 {subset[j]}")
                    found = True
                    break
            if found:
                break
        
        if not found:
            print(f"  未找到（理论上不可能）: {subset}")


if __name__ == "__main__":
    pigeonhole_principle_demo()

6.3 容斥原理实现

python

"""
容斥原理实现
"""

from itertools import combinations


def inclusion_exclusion(sets):
    """
    使用容斥原理计算多个集合并集的大小
    
    参数:
        sets: 集合列表
    
    返回: 并集的大小
    """
    n = len(sets)
    result = 0
    
    # 遍历所有非空子集
    for size in range(1, n + 1):
        for subset_indices in combinations(range(n), size):
            # 计算这些集合的交集
            intersection = sets[subset_indices[0]]
            for idx in subset_indices[1:]:
                intersection = intersection & sets[idx]
            
            # 根据子集大小加减
            if size % 2 == 1:
                result += len(intersection)
            else:
                result -= len(intersection)
    
    return result


def count_divisible_numbers(limit, divisors):
    """
    计算1到limit中能被divisors中至少一个数整除的数的个数
    
    使用容斥原理
    """
    # 构建集合：能被d整除的数
    sets = []
    for d in divisors:
        divisible_set = set(range(d, limit + 1, d))
        sets.append(divisible_set)
    
    return inclusion_exclusion(sets)


def euler_totient(n):
    """
    计算欧拉函数 φ(n)
    
    φ(n) = 不超过n且与n互质的正整数个数
    """
    if n <= 0:
        return 0
    
    result = n
    p = 2
    temp = n
    
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    
    if temp > 1:
        result -= result // temp
    
    return result


def demonstrate_inclusion_exclusion():
    """演示容斥原理"""
    
    print("=== 容斥原理示例 ===")
    
    # 示例1: 手动构造集合
    A = {1, 2, 3, 4, 5}
    B = {4, 5, 6, 7, 8}
    C = {6, 7, 8, 9, 10}
    
    print(f"A = {A}")
    print(f"B = {B}")
    print(f"C = {C}")
    
    union_size = inclusion_exclusion([A, B, C])
    actual_union = A | B | C
    
    print(f"|A ∪ B ∪ C| (容斥) = {union_size}")
    print(f"|A ∪ B ∪ C| (实际) = {len(actual_union)}")
    print(f"验证: {union_size == len(actual_union)}")
    
    print("\n=== 整除计数 ===")
    
    limit = 100
    divisors = [2, 3, 5]
    
    count = count_divisible_numbers(limit, divisors)
    print(f"1到{limit}中能被 {divisors} 中至少一个整除的数有 {count} 个")
    
    # 验证
    actual = sum(1 for i in range(1, limit+1) if any(i % d == 0 for d in divisors))
    print(f"验证: {actual}")
    
    print("\n=== 欧拉函数 ===")
    for n in [1, 2, 3, 4, 5, 6, 10, 12, 60, 100]:
        print(f"  φ({n}) = {euler_totient(n)}")
    
    print("\n=== 错排概率 ===")
    import math
    for n in [1, 2, 3, 4, 5, 10, 20]:
        from chapter_6_tools import derangement
        d_n = derangement(n)
        prob = d_n / math.factorial(n)
        print(f"  n={n}: D_n={d_n}, P={prob:.6f} (1/e ≈ {1/math.e:.6f})")


if __name__ == "__main__":
    demonstrate_inclusion_exclusion()

五、深入思考

5.1 历史背景

计数问题有着悠久的历史。帕斯卡三角形在中国称为杨辉三角，早在11世纪就被发现。雅各布·伯努利在《猜度术》中系统研究了组合数学。亚伯拉罕·棣莫弗和莱昂哈德·欧拉发展了生成函数方法。

乔治·波利亚的计数理论将群论应用于组合计数，解决了化学异构体计数等问题。他的《如何解题》成为数学教育的经典。

保罗·厄尔多斯对组合数学做出了巨大贡献，特别是极值组合学和概率方法。他与众多合作者发表了大量论文，形成了独特的"厄尔多斯风格"。

5.2 前沿方向

代数组合学：使用代数方法解决计数问题，如表示论、对称函数
随机组合结构：研究大型随机结构的性质，如随机图、随机排列
量子计数算法：利用量子计算机加速计数，如近似计数#P问题
近似计数：对于#P完全问题，寻找多项式时间的近似算法，如马尔可夫链蒙特卡洛方法
枚举复杂性：研究生成所有解的效率，如常数延迟枚举

5.3 延伸阅读

《Concrete Mathematics》by Graham, Knuth, Patashnik
《Enumerative Combinatorics》by Richard P. Stanley
《The Art of Computer Programming, Vol. 4A》by Donald E. Knuth
《Combinatorial Problems and Exercises》by László Lovász
《Generatingfunctionology》by Herbert S. Wilf

六、实验笔记

实验1：计数问题求解器

目标：实现一个能够解决常见计数问题的程序。

任务：

支持排列、组合、带重复的排列/组合计算

实现二项式展开

计算卡特兰数、贝尔数等特殊序列

提供问题模板（如"从n个中选r个"）

可视化帕斯卡三角形

实现错排数计算

支持星与棒问题

提交物：源代码、用户界面、测试用例。

扩展挑战：

实现生成函数操作
自动识别问题类型并选择合适的公式
提供详细的解题步骤说明

实验2：蒙特卡洛计数

目标：使用随机采样估计难以精确计算的计数问题。

任务：

估计大规模组合问题的解数量

验证容斥原理的计算结果

模拟鸽巢原理的应用场景

分析估计精度与采样次数的关系

实现重要性采样提高估计效率

提交物：源代码、实验报告、精度分析。

扩展挑战：

比较不同采样方法的效率
实现置信区间计算
应用到实际的组合优化问题

实验3：组合枚举

目标：实现高效生成所有组合对象的算法。

任务：

生成所有排列（Heap算法或Steinhaus-Johnson-Trotter算法）

生成所有组合（格雷码顺序）

生成所有整数划分

生成所有二叉树

分析生成算法的时间复杂度

提交物：源代码、性能测试、可视化输出。

扩展挑战：

实现常数延迟枚举（每两个输出之间的时间为常数）
并行化枚举算法
支持按字典序生成

七、本章小结

本章介绍了基本的计数技术。加法原理和乘法原理是计数的基础，分别处理"或"和"且"的情况。正确识别问题是使用加法还是乘法是成功的关键。

排列考虑顺序，组合不考虑。二项式系数在展开式和概率计算中有广泛应用。理解对称性和帕斯卡恒等式有助于简化计算。

鸽巢原理虽然简单，却能证明令人惊讶的存在性结论。它是组合数学中最直观却最有力的工具之一。容斥原理通过系统地加减交集来避免重复计数，在处理"至少一个"的问题时特别有用。

特殊计数序列如卡特兰数、斯特林数、贝尔数出现在各种意想不到的场景中，展示了组合数学的统一美。卡特兰数尤其有趣，它在括号匹配、二叉树计数、格路路径等多个问题中出现。

错排问题是容斥原理的经典应用，其渐近行为与e密切相关。星与棒方法为解决分配问题提供了统一的框架。

计数需要细心和系统性思维，避免重复和遗漏是成功的关键。在实际应用中，常常需要结合多种技术，如先使用补集思想，再应用容斥原理。

八、习题

习题1（基础）：计算：

(a) P(10, 4)

(b) C(10, 4)

(d) 6!

(e) C(100, 98)

习题2（基础）：一个班级有30名学生。

(a) 选班长有多少种选法？

(b) 选班长和副班长有多少种选法？

(d) 选3人组成委员会并指定主席有多少种选法？

习题3（中等）：展开 (2x - 1)⁵。

习题4（中等）：证明 $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$。

习题5（中等）：1到200中有多少个数能被3或7整除但不能被21整除？

习题6（较难）：证明在任何n+1个不超过2n的正整数中，必有两个数互质。

习题7（较难）：计算n对括号的合法匹配方式数，验证它是卡特兰数。

习题8（挑战）：研究并证明范德蒙德恒等式。

习题9（挑战）：有多少种方式将n个相同的球放入k个不同的盒子，允许空盒？推导一般公式。

习题10（开放）：选择一个实际应用场景（如彩票、密码、游戏），分析其中的计数问题并撰写报告。包括：

问题描述
使用的计数技术
计算过程和结果
实际意义和应用

第6章 计数 (Counting)

一、导读

1.1 本章学习目标

1.2 为什么本章如此重要

1.3 核心问题引导

二、核心概念详解

6.1 基本计数原理

加法原理

乘法原理

6.2 排列

定义

公式

特殊情况

带重复元素的排列

循环排列

6.3 组合

定义

公式

性质

组合恒等式

"星与棒"方法（Stars and Bars）

6.4 二项式定理

定理

证明思路

特例

应用

6.5 鸽巢原理

简单形式

推广形式

应用示例

6.6 容斥原理

两个集合

三个集合

一般形式

应用示例

错排问题（Derangement）

6.7 特殊计数序列

卡特兰数

斯特林数

贝尔数

斐波那契数列

6.8 生成函数入门

三、程序员的视角

3.1 在计算机科学中的应用

算法复杂度

密码学

测试用例生成

数据库

机器学习

3.2 常见陷阱与误区

重复计数

顺序混淆

边界情况

溢出问题

"至少"与"恰好"的混淆

3.3 与其他层级的联系

四、代码实战

6.1 计数工具实现

6.2 鸽巢原理验证

6.3 容斥原理实现

五、深入思考

5.1 历史背景

5.2 前沿方向

5.3 延伸阅读

六、实验笔记

实验1：计数问题求解器

实验2：蒙特卡洛计数

实验3：组合枚举

七、本章小结

八、习题

第6章计数 (Counting)