第6章特殊数 (Special Numbers)

一、导读

6.1 本章学习目标

在本章结束时，你将能够：

理解斯特林数的第一类和第二类定义及其组合意义
掌握欧拉数的定义和在排列统计中的应用
计算调和数并理解其渐近行为
应用伯努利数进行求和计算
理解斐波那契数的性质和黄金比例的关系
使用卡特兰数解决括号匹配等问题
掌握特殊数之间的相互关系
了解贝尔数和集合划分问题

6.2 为什么本章如此重要

特殊数是组合数学和离散分析中的基本构建块。它们不仅出现在纯数学问题中，在计算机科学中也有广泛应用：

斯特林数：集合划分、哈希表分析、动态规划优化

欧拉数：排序算法的比较次数分析、排列统计

调和数：快速排序、随机算法的期望分析、搜索引擎排名

伯努利数：数值积分、级数展开、黎曼ζ函数

斐波那契数：数据结构（斐波那契堆）、算法分析、自然现象建模

卡特兰数：二叉树计数、括号匹配、栈操作、表达式解析

贝尔数：聚类分析、等价关系计数

《具体数学》用大量篇幅讨论这些特殊数，因为它们是连接离散与连续、有限与无限的桥梁。掌握这些数的性质和计算方法，是成为优秀算法分析师的必备技能。

这些特殊数之间存在着深刻的联系。例如，斯特林数可以将普通幂转换为下降幂，伯努利数用于幂和公式，而调和数出现在许多算法的平均情况分析中。理解这些联系能够帮助你在面对新问题时快速找到合适的数学工具。

6.3 核心问题引导

第一类斯特林数和第二类斯特林数有什么区别？

如何将普通幂表示为下降幂的线性组合？

欧拉数如何描述排列的"上升"结构？

调和数 H_n 为什么没有闭合形式？它的渐近近似是什么？

伯努利数如何用于幂和公式？

斐波那契数列的通项公式（比内公式）是如何推导的？

卡特兰数有哪些组合解释？

贝尔数与斯特林数有什么关系？

二、核心概念详解

6.1 斯特林数

第二类斯特林数

定义：第二类斯特林数 $\left\{ {n \atop k} \right\}$ 表示将 n 个不同元素划分为 k 个非空子集的方案数。

递推关系：

$$\left\{ {n \atop k} \right\} = k\left\{ {n-1 \atop k} \right\} + \left\{ {n-1 \atop k-1} \right\}$$

组合解释：考虑第 n 个元素：

如果它单独构成一个子集，剩下 n-1 个元素分为 k-1 个子集：$\left\{ {n-1 \atop k-1} \right\}$ 种
如果它加入已有的某个子集，先分好 n-1 个元素为 k 个子集（$\left\{ {n-1 \atop k} \right\}$ 种），再将第 n 个元素放入 k 个子集中的任意一个：$k\left\{ {n-1 \atop k} \right\}$ 种

边界条件：

$\left\{ {0 \atop 0} \right\} = 1$
$\left\{ {n \atop 0} \right\} = 0$（n > 0）
$\left\{ {n \atop n} \right\} = 1$
$\left\{ {n \atop 1} \right\} = 1$
$\left\{ {n \atop 2} \right\} = 2^{n-1} - 1$

示例：$\left\{ {3 \atop 2} \right\} = 3$。将 {1,2,3} 分为 2 个子集：{{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}。

与普通幂的关系：

$$x^n = \sum_{k=0}^{n} \left\{ {n \atop k} \right\} x^{\underline{k}}$$

其中 $x^{\underline{k}} = x(x-1)\cdots(x-k+1)$ 是下降幂。这个公式说明第二类斯特林数是将普通幂转换为下降幂的系数。

证明：对 n 归纳。n=0 时显然。假设对 n-1 成立，则：

$$x^n = x \cdot x^{n-1} = x \sum_{k=0}^{n-1} \left\{ {n-1 \atop k} \right\} x^{\underline{k}}$$

利用 $x \cdot x^{\underline{k}} = x^{\underline{k+1}} + k x^{\underline{k}}$，整理后得到递推关系。✓

显式公式：

$$\left\{ {n \atop k} \right\} = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$$

这可以通过容斥原理推导：先将 n 个元素分配到 k 个有标签的盒子中（允许空盒），然后减去至少有一个空盒的情况。

第一类斯特林数

定义：第一类斯特林数 $\left[ {n \atop k} \right]$（无符号）表示 n 个元素的排列中恰好有 k 个循环的个数。

递推关系：

$$\left[ {n \atop k} \right] = (n-1)\left[ {n-1 \atop k} \right] + \left[ {n-1 \atop k-1} \right]$$

组合解释：考虑第 n 个元素在排列中的位置：

如果它自己形成一个长度为1的循环，剩下 n-1 个元素形成 k-1 个循环：$\left[ {n-1 \atop k-1} \right]$ 种
如果它插入到某个现有循环中，先排好 n-1 个元素为 k 个循环（$\left[ {n-1 \atop k} \right]$ 种），然后将 n 插入到任意一个循环的任意位置。每个循环总共有 n-1 个插入位置：$(n-1)\left[ {n-1 \atop k} \right]$ 种

边界条件：

$\left[ {0 \atop 0} \right] = 1$
$\left[ {n \atop 0} \right] = 0$（n > 0）
$\left[ {n \atop n} \right] = 1$
$\left[ {n \atop 1} \right] = (n-1)!$（n 个元素形成一个循环的排列数）

示例：n=3 的排列：

(1)(2)(3): 3个循环 → 贡献给 $\left[ {3 \atop 3} \right]$
(12)(3), (13)(2), (23)(1): 2个循环 → 贡献给 $\left[ {3 \atop 2} \right]$
(123), (132): 1个循环 → 贡献给 $\left[ {3 \atop 1} \right]$

所以 $\left[ {3 \atop 1} \right] = 2$, $\left[ {3 \atop 2} \right] = 3$, $\left[ {3 \atop 3} \right] = 1$。

与上升阶乘的关系：

$$x^{\overline{n}} = x(x+1)(x+2)\cdots(x+n-1) = \sum_{k=0}^{n} \left[ {n \atop k} \right] x^k$$

两类斯特林数的互逆关系

斯特林数构成了一个互逆变换对：

$$x^n = \sum_{k} \left\{ {n \atop k} \right\} x^{\underline{k}}$$

$$x^{\underline{n}} = \sum_{k} (-1)^{n-k} \left[ {n \atop k} \right] x^k$$

这意味着：

$$\sum_{k} (-1)^{n-k} \left[ {n \atop k} \right] \left\{ {k \atop m} \right\} = \delta_{nm}$$

其中 δₙₘ 是克罗内克δ函数。

应用：这个互逆关系可以用于在普通幂和下降幂之间转换，从而简化某些求和问题。

贝尔数

贝尔数 Bₙ 定义为 n 个元素的集合的所有可能划分的总数：

$$B_n = \sum_{k=0}^{n} \left\{ {n \atop k} \right\}$$

前几个贝尔数：B₀=1, B₁=1, B₂=2, B₃=5, B₄=15, B₅=52, B₆=203。

递推关系：

$$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$$

组合解释：考虑包含元素 n+1 的那个块。如果这个块的大小为 n-k+1（即除了 n+1 外还有 n-k 个其他元素），则从剩下的 n 个元素中选 n-k 个与 n+1 同组，有 $\binom{n}{n-k} = \binom{n}{k}$ 种选法，剩下的 k 个元素有 Bₖ 种划分方式。

生成函数：贝尔数的指数生成函数为：

$$\hat{B}(x) = e^{e^x - 1}$$

6.2 欧拉数

定义

欧拉数（Eulerian Number）$\left\langle {n \atop k} \right\rangle$ 表示 n 个元素的排列中恰好有 k 个"上升"的个数。

上升的定义：在排列 π = π₁π₂...πₙ 中，如果 πᵢ < πᵢ₊₁，则称位置 i 是一个上升。

注意：有些文献定义欧拉数为有 k+1 个上升的排列数，索引略有不同。这里采用《具体数学》的约定。

递推关系：

$$\left\langle {n \atop k} \right\rangle = (k+1)\left\langle {n-1 \atop k} \right\rangle + (n-k)\left\langle {n-1 \atop k-1} \right\rangle$$

推导思路：考虑将 n 插入到 n-1 个元素的排列中。根据插入位置和原排列的上升结构，可以推导出上述递推关系。

边界条件：

$\left\langle {0 \atop 0} \right\rangle = 1$
$\left\langle {n \atop 0} \right\rangle = 1$（只有递减排列没有上升）
$\left\langle {n \atop n-1} \right\rangle = 1$（只有递增排列有 n-1 个上升）

示例：n=3 的所有排列：

123: 2个上升（位置1和2）→ 贡献给 $\left\langle {3 \atop 2} \right\rangle$
132: 1个上升（位置1）→ 贡献给 $\left\langle {3 \atop 1} \right\rangle$
213: 1个上升（位置2）→ 贡献给 $\left\langle {3 \atop 1} \right\rangle$
231: 1个上升（位置1）→ 贡献给 $\left\langle {3 \atop 1} \right\rangle$
312: 1个上升（位置2）→ 贡献给 $\left\langle {3 \atop 1} \right\rangle$
321: 0个上升 → 贡献给 $\left\langle {3 \atop 0} \right\rangle$

所以 $\left\langle {3 \atop 0} \right\rangle = 1$, $\left\langle {3 \atop 1} \right\rangle = 4$, $\left\langle {3 \atop 2} \right\rangle = 1$。

验证：总和为 1+4+1 = 6 = 3!。✓

欧拉数的性质

对称性：

$$\left\langle {n \atop k} \right\rangle = \left\langle {n \atop n-1-k} \right\rangle$$

解释：将排列反转，上升变为下降，下降变为上升。n-1 个位置中，如果有 k 个上升，则有 n-1-k 个下降。

显式公式：

$$\left\langle {n \atop k} \right\rangle = \sum_{j=0}^{k+1} (-1)^j \binom{n+1}{j} (k+1-j)^n$$

欧拉数的生成函数

欧拉多项式定义为：

$$A_n(t) = \sum_{k=0}^{n-1} \left\langle {n \atop k} \right\rangle t^k$$

生成函数为：

$$\sum_{n=0}^{\infty} A_n(t) \frac{x^n}{n!} = \frac{1-t}{e^{(t-1)x} - t}$$

特殊值：

Aₙ(1) = n!（所有排列的总数）
Aₙ(-1) 与正切数和正割数有关

6.3 调和数

定义回顾

调和数：

$$H_n = \sum_{k=1}^{n} \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$$

前几个调和数：

H₁ = 1
H₂ = 3/2 = 1.5
H₃ = 11/6 ≈ 1.833
H₄ = 25/12 ≈ 2.083
H₅ = 137/60 ≈ 2.283

广义调和数

广义调和数：

$$H_n^{(r)} = \sum_{k=1}^{n} \frac{1}{k^r}$$

当 r = 1 时就是普通调和数。当 r = 2 时：

$$H_n^{(2)} = \sum_{k=1}^{n} \frac{1}{k^2}$$

当 n → ∞ 时，$H_\infty^{(2)} = \frac{\pi^2}{6}$（巴塞尔问题，由欧拉解决）。

一般地，$H_\infty^{(r)} = \zeta(r)$，其中 ζ 是黎曼ζ函数。

调和数的恒等式

恒等式1：

$$\sum_{k=1}^{n} H_k = (n+1)H_n - n$$

证明：交换求和顺序：

$$\sum_{k=1}^{n} H_k = \sum_{k=1}^{n} \sum_{j=1}^{k} \frac{1}{j} = \sum_{j=1}^{n} \sum_{k=j}^{n} \frac{1}{j} = \sum_{j=1}^{n} \frac{n-j+1}{j} = (n+1)H_n - n$$

恒等式2：

$$\sum_{k=1}^{n} \frac{H_k}{k} = \frac{H_n^2 + H_n^{(2)}}{2}$$

证明思路：考虑 $(H_n)^2 = (\sum_{i=1}^n \frac{1}{i})(\sum_{j=1}^n \frac{1}{j})$，展开后分离对角线项和非对角线项。

恒等式3：

$$\sum_{k=1}^{n} \frac{(-1)^{k-1}}{k} \binom{n}{k} = H_n$$

这个恒等式将调和数与二项式系数联系起来。

渐近展开

$$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \cdots$$

其中 γ ≈ 0.5772156649 是欧拉-马斯刻若尼常数。

推导：使用欧拉-麦克劳林求和公式，将求和近似为积分加上修正项。

近似精度：即使对于较小的 n，这个近似也非常精确。例如，n=10 时：

精确值：H₁₀ = 7381/2520 ≈ 2.928968
近似（取前三项）：ln(10) + γ + 1/20 ≈ 2.3026 + 0.5772 + 0.05 ≈ 2.9298

误差小于 0.001。

6.4 伯努利数

定义

伯努利数 Bₙ 由以下生成函数定义：

$$\frac{x}{e^x - 1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}$$

前几个伯努利数：

B₀ = 1
B₁ = -1/2
B₂ = 1/6
B₃ = 0
B₄ = -1/30
B₅ = 0
B₆ = 1/42
B₇ = 0
B₈ = -1/30
B₁₀ = 5/66
B₁₂ = -691/2730

性质：所有奇数下标大于1的伯努利数都为0。这是因为 $\frac{x}{e^x-1} + \frac{x}{2}$ 是偶函数。

伯努利数与幂和

伯努利数最著名的应用是计算幂和：

$$\sum_{k=1}^{n} k^m = \frac{1}{m+1} \sum_{j=0}^{m} \binom{m+1}{j} B_j n^{m+1-j}$$

示例：m = 1 时，

$$\sum_{k=1}^{n} k = \frac{1}{2} \left[\binom{2}{0}B_0 n^2 + \binom{2}{1}B_1 n^1\right] = \frac{1}{2}[n^2 + 2(-\frac{1}{2})n] = \frac{n^2-n}{2} + \frac{n}{2} = \frac{n(n+1)}{2}$$

这正是高斯公式！

示例：m = 2 时，

$$\sum_{k=1}^{n} k^2 = \frac{1}{3} \left[B_0 n^3 + 3B_1 n^2 + 3B_2 n^1\right] = \frac{1}{3}\left[n^3 - \frac{3}{2}n^2 + \frac{1}{2}n\right] = \frac{n(n+1)(2n+1)}{6}$$

示例：m = 3 时，

$$\sum_{k=1}^{n} k^3 = \frac{1}{4}\left[n^4 - 2n^3 + n^2\right] = \left[\frac{n(n+1)}{2}\right]^2$$

这正是著名的结论：前 n 个立方数之和等于前 n 个整数之和的平方。

伯努利数的计算

递推关系：

$$\sum_{k=0}^{m} \binom{m+1}{k} B_k = 0 \quad \text{for } m \geq 1$$

由此可得：

$$B_m = -\frac{1}{m+1}\sum_{k=0}^{m-1} \binom{m+1}{k} B_k$$

Akiyama-Tanigawa 算法：一种数值稳定的计算方法。

6.5 斐波那契数

定义

斐波那契数列：

$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ for } n \geq 2$$

前几项：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

比内公式

比内公式（Binet's Formula）给出了斐波那契数的闭合形式：

$$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$$

其中 $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ 是黄金比例，$\psi = \frac{1-\sqrt{5}}{2} \approx -0.618$。

推导：设 Fₙ = rⁿ，代入递推关系 rⁿ = rⁿ⁻¹ + rⁿ⁻²，得到特征方程 r² = r + 1，即 r² - r - 1 = 0。解得 $r = \frac{1\pm\sqrt{5}}{2}$，即 φ 和 ψ。

通解为 $F_n = A\phi^n + B\psi^n$。由初始条件 F₀=0, F₁=1 解得 $A = \frac{1}{\sqrt{5}}, B = -\frac{1}{\sqrt{5}}$。

由于 |ψ| < 1，当 n 很大时，ψⁿ → 0，所以 $F_n \approx \frac{\phi^n}{\sqrt{5}}$。更精确地，$F_n = \left\lfloor \frac{\phi^n}{\sqrt{5}} + \frac{1}{2} \right\rfloor$。

重要恒等式

恒等式1（求和）：

$$\sum_{k=0}^{n} F_k = F_{n+2} - 1$$

证明：归纳法或利用 Fₖ = Fₖ₊₂ - Fₖ₊₁ telescoping。

恒等式2（卡西尼恒等式）：

$$F_{n-1}F_{n+1} - F_n^2 = (-1)^n$$

证明：归纳法。n=1 时：F₀F₂ - F₁² = 0×1 - 1 = -1 = (-1)¹。假设对 n 成立，则：

$$F_n F_{n+2} - F_{n+1}^2 = F_n(F_{n+1}+F_n) - F_{n+1}^2 = F_n F_{n+1} + F_n^2 - F_{n+1}^2$$

$$= F_n^2 - F_{n+1}(F_{n+1}-F_n) = F_n^2 - F_{n+1}F_{n-1} = -(F_{n-1}F_{n+1} - F_n^2) = -(-1)^n = (-1)^{n+1}$$

恒等式3（加法公式）：

$$F_{m+n} = F_{m+1}F_n + F_m F_{n-1}$$

恒等式4（整除性）：

$$F_m | F_n \iff m | n$$

矩阵表示

斐波那契数列可以用矩阵幂表示：

$$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$$

这使得可以使用快速幂算法在 O(log n) 时间内计算 Fₙ。

卢卡斯数

卢卡斯数 Lₙ 定义为：L₀=2, L₁=1, Lₙ=Lₙ₋₁+Lₙ₋₂。

前几项：2, 1, 3, 4, 7, 11, 18, 29, ...

与斐波那契数的关系：

$$L_n = \phi^n + \psi^n$$

$$L_n = F_{n-1} + F_{n+1}$$

6.6 卡特兰数

定义

卡特兰数（Catalan Numbers）Cₙ 定义为：

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$

前几项：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

组合解释

卡特兰数有超过200种组合解释，以下是几种经典的：

合法括号序列：n 对括号的合法排列数

- n=3: ()()(), ()(()), (())(), (()()), ((())) → C₃ = 5

二叉树计数：n+1 个叶子节点的满二叉树的数量，或 n 个内部节点的二叉树数量

栈操作序列：n 次push和n次pop的合法序列数

多边形三角剖分：凸 n+2 边形的三角剖分数

不穿越对角线的路径：从 (0,0) 到 (n,n) 只向右或向上走且不穿越 y=x 的路径数

非交叉划分：{1, 2, ..., 2n} 的非交叉完美匹配数

Dyck路径：从 (0,0) 到 (2n,0)，每步为 (1,1) 或 (1,-1)，且始终不低于 x 轴的路径数

递推关系

$$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$$

解释：考虑第一个左括号匹配的右括号的位置，将问题分解为两个子问题。

另一个递推关系：

$$C_n = \frac{2(2n-1)}{n+1} C_{n-1}$$

初始条件：C₀ = 1。

生成函数

卡特兰数的生成函数为：

$$C(x) = \sum_{n=0}^{\infty} C_n x^n = \frac{1-\sqrt{1-4x}}{2x}$$

推导：由递推关系 Cₙ = Σᵢ CᵢCₙ₋₁₋ᵢ，可知 C(x) = 1 + xC(x)²。解二次方程得到上述结果。

渐近行为

$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$

推导：使用斯特林公式近似 $\binom{2n}{n}$。

6.7 其他特殊数

三角形数

三角形数 Tₙ = 1 + 2 + ... + n = n(n+1)/2。

前几项：1, 3, 6, 10, 15, 21, ...

中心二项式系数

$$\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}$$

在随机游走和组合计数中经常出现。

三、程序员的视角

6.1 在算法分析中的应用

斯特林数的应用

哈希表分析：将 n 个键分配到 k 个桶中的方案数涉及第二类斯特林数
集合划分算法：Bell数（所有划分的总数）$B_n = \sum_{k} \left\{ {n \atop k} \right\}$
动态规划优化：某些DP问题的状态转移可以用斯特林数简化

卡特兰数的应用

二叉搜索树计数：n 个不同键能构成的BST数量是 Cₙ
矩阵链乘法：n 个矩阵相乘的不同加括号方式数是 Cₙ₋₁
表达式解析：合法表达式的数量
编译器设计：语法分析中的括号匹配

调和数的应用

快速排序分析：平均比较次数约为 2n ln n = 2n Hₙ
优惠券收集问题：收集 n 种优惠券的期望次数是 n Hₙ
PageRank算法：调和数出现在收敛性分析中

6.2 常见陷阱

陷阱1：大数溢出

特殊数增长非常快。例如，C₁₀₀ 是一个非常大的数。计算时应使用高精度库或模运算。

陷阱2：浮点精度

使用比内公式计算大斐波那契数时，浮点精度可能不足。应使用矩阵快速幂或递推。

陷阱3：递归深度

直接递归计算斐波那契数会导致指数级时间复杂度。应使用记忆化或迭代。

6.3 与其他领域的联系

量子物理：某些粒子统计涉及斯特林数
生物信息学：RNA二级结构预测涉及卡特兰数
金融数学：期权定价中的某些模型使用伯努利数
艺术与设计：黄金比例在美学中的应用

四、代码实战

6.1 特殊数计算库

python

class SpecialNumbers:
    """特殊数计算工具"""
    
    @staticmethod
    def stirling_second(n, k):
        """计算第二类斯特林数 {n \\ k}"""
        if n == 0 and k == 0:
            return 1
        if n == 0 or k == 0:
            return 0
        if k > n:
            return 0
        
        # DP表格
        S = [[0] * (k+1) for _ in range(n+1)]
        S[0][0] = 1
        for i in range(1, n+1):
            for j in range(1, min(i,k)+1):
                S[i][j] = j * S[i-1][j] + S[i-1][j-1]
        return S[n][k]
    
    @staticmethod
    def stirling_first(n, k):
        """计算第一类斯特林数 [n \\ k]（无符号）"""
        if n == 0 and k == 0:
            return 1
        if n == 0 or k == 0:
            return 0
        if k > n:
            return 0
        
        # DP表格
        S = [[0] * (k+1) for _ in range(n+1)]
        S[0][0] = 1
        for i in range(1, n+1):
            for j in range(1, min(i,k)+1):
                S[i][j] = (i-1) * S[i-1][j] + S[i-1][j-1]
        return S[n][k]
    
    @staticmethod
    def bell(n):
        """计算贝尔数 B_n"""
        # 使用三角形方法
        triangle = [[0] * (n+1) for _ in range(n+1)]
        triangle[0][0] = 1
        for i in range(1, n+1):
            triangle[i][0] = triangle[i-1][i-1]
            for j in range(1, i+1):
                triangle[i][j] = triangle[i][j-1] + triangle[i-1][j-1]
        return triangle[n][0]
    
    @staticmethod
    def eulerian(n, k):
        """计算欧拉数 <n \\ k>"""
        if n == 0 and k == 0:
            return 1
        if k < 0 or k >= n:
            return 0
        
        E = [[0] * n for _ in range(n+1)]
        E[0][0] = 1
        for i in range(1, n+1):
            for j in range(i):
                val1 = (j + 1) * E[i-1][j] if j < len(E[i-1]) else 0
                val2 = (i - j) * E[i-1][j-1] if j > 0 else 0
                E[i][j] = val1 + val2
        return E[n][k]
    
    @staticmethod
    def harmonic(n, r=1):
        """计算广义调和数 H_n^(r)"""
        return sum(1.0 / k**r for k in range(1, n+1))
    
    @staticmethod
    def bernoulli(n):
        """计算伯努利数 B_n"""
        if n == 0:
            return 1
        if n % 2 == 1 and n > 1:
            return 0
        
        # 使用递推关系
        B = [0] * (n + 1)
        B[0] = 1
        for m in range(1, n + 1):
            s = 0
            for k in range(m):
                s += math.comb(m + 1, k) * B[k]
            B[m] = -s / (m + 1)
        return B[n]
    
    @staticmethod
    def fibonacci(n):
        """计算斐波那契数 F_n（使用矩阵快速幂）"""
        if n <= 1:
            return n
        
        def matrix_mult(A, B):
            return [
                [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
                [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
            ]
        
        def matrix_pow(M, p):
            if p == 1:
                return M
            if p % 2 == 0:
                half = matrix_pow(M, p // 2)
                return matrix_mult(half, half)
            else:
                return matrix_mult(M, matrix_pow(M, p - 1))
        
        M = [[1, 1], [1, 0]]
        result = matrix_pow(M, n)
        return result[0][1]
    
    @staticmethod
    def catalan(n):
        """计算卡特兰数 C_n"""
        # 使用递推关系
        C = [0] * (n+1)
        C[0] = 1
        for i in range(1, n+1):
            for j in range(i):
                C[i] += C[j] * C[i-1-j]
        return C[n]
    
    @staticmethod
    def lucas(n):
        """计算卢卡斯数 L_n"""
        if n == 0:
            return 2
        if n == 1:
            return 1
        a, b = 2, 1
        for _ in range(2, n+1):
            a, b = b, a + b
        return b

import math

# 测试
sn = SpecialNumbers()
print("=== 特殊数测试 ===")

print("\n第二类斯特林数:")
for n in range(6):
    row = [sn.stirling_second(n, k) for k in range(n+1)]
    print(f"n={n}: {row}")

print("\n第一类斯特林数:")
for n in range(6):
    row = [sn.stirling_first(n, k) for k in range(n+1)]
    print(f"n={n}: {row}")

print("\n贝尔数:")
for n in range(8):
    print(f"B_{n} = {sn.bell(n)}")

print("\n欧拉数:")
for n in range(1, 6):
    row = [sn.eulerian(n, k) for k in range(n)]
    print(f"n={n}: {row}")

print("\n调和数:")
for n in [1, 2, 5, 10]:
    print(f"H_{n} = {sn.harmonic(n):.6f}")

print("\n伯努利数:")
for n in range(11):
    B = sn.bernoulli(n)
    if B != 0:
        print(f"B_{n} = {B}")

print("\n斐波那契数:")
for n in range(11):
    print(f"F_{n} = {sn.fibonacci(n)}")

print("\n卡特兰数:")
for n in range(8):
    print(f"C_{n} = {sn.catalan(n)}")

print("\n卢卡斯数:")
for n in range(10):
    print(f"L_{n} = {sn.lucas(n)}")

6.2 斐波那契数的多种计算方法比较

python

import time

def fibonacci_recursive(n):
    """朴素递归（指数时间）"""
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

def fibonacci_memo(n, memo={}):
    """记忆化递归"""
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

def fibonacci_iterative(n):
    """迭代方法"""
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

# 性能比较
n = 30
start = time.time()
r1 = fibonacci_iterative(n)
t1 = time.time() - start

start = time.time()
r2 = fibonacci_memo(n)
t2 = time.time() - start

print(f"\nF_{n} = {r1}")
print(f"迭代方法: {t1:.6f} 秒")
print(f"记忆化递归: {t2:.6f} 秒")

五、深入思考

5.1 历史背景

斯特林数以詹姆斯·斯特林命名，欧拉数以莱昂哈德·欧拉命名。伯努利数来自雅各布·伯努利的《猜度术》。斐波那契数列由印度数学家平加拉最早描述，后由斐波那契引入欧洲。卡特兰数以比利时数学家欧仁·查理·卡特兰命名，但实际上早在18世纪就被中国数学家明安图研究过。

5.2 未解决的问题

伯努利数的分布：伯努利数的分母有什么规律？Kummer同余式

斯特林数的渐近行为：当 n, k 都趋于无穷时的行为

卡特兰数的推广：更高维的卡特兰数、q-卡特兰数

斐波那契数的素性：有多少个斐波那契数是素数？

5.3 延伸阅读

《具体数学》第6章 - Graham, Knuth, Patashnik

《Concrete Mathematics》

《The Art of Computer Programming, Vol. 1》 - Donald Knuth

《Fibonacci and Lucas Numbers with Applications》 - Koshy

六、实验笔记

实验一：斯特林数的可视化

目标：绘制第二类斯特林数的三角形，观察规律。

步骤：

计算前15行的第二类斯特林数

用热力图可视化

观察最大值的位置和分布规律

实验二：卡特兰数的多种解释验证

目标：通过枚举验证卡特兰数的不同组合解释。

步骤：

枚举 n=4 时的所有合法括号序列

枚举 n=4 时的所有二叉树结构

验证数量都等于 C₄ = 14

实验三：调和数的渐近行为

目标：验证 Hₙ ≈ ln n + γ 的精度。

步骤：

计算不同 n 值的 Hₙ

计算 Hₙ - ln n

观察是否趋近于 γ

七、本章小结

关键公式：

第二类斯特林数：$\left\{ {n \atop k} \right\} = k\left\{ {n-1 \atop k} \right\} + \left\{ {n-1 \atop k-1} \right\}$
比内公式：$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$
卡特兰数：$C_n = \frac{1}{n+1}\binom{2n}{n}$
调和数渐近：$H_n = \ln n + \gamma + O(1/n)$
伯努利数幂和：$\sum_{k=1}^n k^m = \frac{1}{m+1}\sum_{j=0}^m \binom{m+1}{j}B_j n^{m+1-j}$

核心思想：

特殊数是组合结构的量化

递推关系提供高效计算

生成函数统一处理

渐近分析揭示增长行为

八、习题

基础题

习题 6.1：计算 $\left\{ {5 \atop 3} \right\}$。

提示：使用递推关系或直接枚举集合划分。

习题 6.2：计算 F₁₀。

提示：使用递推或比内公式。

习题 6.3：计算 C₅。

提示：使用公式 $C_n = \frac{1}{n+1}\binom{2n}{n}$。

习题 6.4：计算 H₆。

提示：直接求和。

进阶题

习题 6.5：[ME] 证明 $\sum_{k=0}^{n} F_k = F_{n+2} - 1$。

提示：使用归纳法或 telescoping 求和。

习题 6.6：[ME] 推导卡特兰数的递推关系 $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$。

提示：考虑括号序列中第一个左括号匹配的右括号位置。

习题 6.7：[ME] 证明卡西尼恒等式 $F_{n-1}F_{n+1} - F_n^2 = (-1)^n$。

提示：使用归纳法。

挑战题

习题 6.8：[HM25] 证明比内公式。

提示：求解特征方程 r² = r + 1。

习题 6.9：[HM30] 研究斯特林数的渐近行为。

提示：使用 saddle-point 方法或生成函数分析。

习题 6.10：[HM40] 推导伯努利数的生成函数 $\frac{x}{e^x-1}$。

提示：从幂和公式出发，构造指数生成函数。

本章完

第6章 特殊数 (Special Numbers)

一、导读

6.1 本章学习目标

6.2 为什么本章如此重要

6.3 核心问题引导

二、核心概念详解

6.1 斯特林数

第二类斯特林数

第一类斯特林数

两类斯特林数的互逆关系

贝尔数

6.2 欧拉数

定义

欧拉数的性质

欧拉数的生成函数

6.3 调和数

定义回顾

广义调和数

调和数的恒等式

渐近展开

6.4 伯努利数

定义

伯努利数与幂和

伯努利数的计算

6.5 斐波那契数

定义

比内公式

重要恒等式

矩阵表示

卢卡斯数

6.6 卡特兰数

定义

组合解释

递推关系

生成函数

渐近行为

6.7 其他特殊数

三角形数

中心二项式系数

三、程序员的视角

6.1 在算法分析中的应用

斯特林数的应用

卡特兰数的应用

调和数的应用

6.2 常见陷阱

陷阱1：大数溢出

陷阱2：浮点精度

陷阱3：递归深度

6.3 与其他领域的联系

四、代码实战

6.1 特殊数计算库

6.2 斐波那契数的多种计算方法比较

五、深入思考

5.1 历史背景

5.2 未解决的问题

5.3 延伸阅读

六、实验笔记

实验一：斯特林数的可视化

实验二：卡特兰数的多种解释验证

实验三：调和数的渐近行为

七、本章小结

八、习题

基础题

进阶题

挑战题

第6章特殊数 (Special Numbers)