1. 数学符号规范
在数学中，通常使用以下符号： * 第一类斯特林数（无符号）：$\begin{bmatrix} n \ k \end{bmatrix}$，读作 "n 轮换 k" (n cycle k)。 * 第二类斯特林数：$$\begin{smallmatrix} { \end{smallmatrix} \begin{smallmatrix} n \ k \end{smallmatrix} \begin{smallmatrix} } \end{smallmatrix}$$，读作 "n 子集 k" (n subset k)。
2. 第一类斯特林数：无符号 vs 有符号
你笔记中给出的是无符号第一类斯特林数（Unsigned Stirling numbers of the first kind）。 在某些数学推导中，会有“有符号”的版本，记为 $s(n, k)$： * 关系：$s(n, k) = (-1)^{n-k} \begin{bmatrix} n \ k \end{bmatrix}$ * 物理意义：有符号数是下降阶乘幂展开式的系数。
一个非常重要的性质： 所有第一类斯特林数 $\begin{bmatrix} n \ k \end{bmatrix}$ 对 $k$ 求和，等于 $n$ 的阶乘： $$\sum_{k=0}^n \begin{bmatrix} n \ k \end{bmatrix} = n!$$ 解释：这代表将 $n$ 个元素拆成任意数量环的方案数，等同于 $n$ 个元素的所有置换数。
3. 第二类斯特林数：扩展性质
与贝尔数（Bell Number）的关系： 将 $n$ 个不同物体拆分成任意数量非空集合的方案总数称为贝尔数 $B_n$： $$B_n = \sum_{k=0}^n \begin{Bmatrix} n \ k \end{Bmatrix}$$
与“球盒模型”的对应关系： * $n$ 个不同球，$k$ 个相同盒，不能有空：$\begin{Bmatrix} n \ k \end{Bmatrix}$ * $n$ 个不同球，$k$ 个不同盒，不能有空：$k! \cdot \begin{Bmatrix} n \ k \end{Bmatrix}$（因为盒子有了名字，所以要乘盒子的全排列）
4. 核心：斯特林反演与幂转换（进阶考点）
斯特林数最强大的地方在于它们能把通常幂（$x^n$）和阶乘幂（$x^{\underline{n}}$）互相转换。
-
通常幂转下降阶乘幂（用第二类）： $$x^n = \sum_{k=0}^n \begin{Bmatrix} n \ k \end{Bmatrix} x^{\underline{k}}$$ 其中 $x^{\underline{k}} = x(x-1)(x-2)\dots(x-k+1)$。 这个公式在求 $\sum i^k$ 这种自然数幂和的题目中非常管用。
-
上升阶乘幂转通常幂（用第一类）： $$x^{\overline{n}} = \sum_{k=0}^n \begin{bmatrix} n \ k \end{bmatrix} x^k$$ 其中 $x^{\overline{n}} = x(x+1)(x+2)\dots(x+n-1)$。
5. 第二类斯特林数的 C++ 代码实现
逻辑与你写的第一类相似，只是倍率不同：
// 第二类斯特林数递推实现
void init\_stirling2(int n) {
S2[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
// 状态转移：当前球单独开一个盒子 + 当前球放入已有的j个盒子
S2[i][j] = (S2[i - 1][j - 1] + (long long)j * S2[i - 1][j]) % MOD;
}
}
}
总结对比表
| 特性 | 第一类斯特林数 $\begin{bmatrix} n \ k \end{bmatrix}$ | 第二类斯特林数 $\begin{Bmatrix} n \ k \end{Bmatrix}$ |
|---|---|---|
| 形象理解 | $n$ 个人坐 $k$ 张圆桌 | $n$ 个球放 $k$ 个盒子 |
| 递推式差异 | 乘以 $(i-1)$ (插入间隙) | 乘以 $j$ (选择盒子) |
| 行和 | $n!$ (阶乘) | $B_n$ (贝尔数) |
| 主要用途 | 置换群、上升幂展开 | 幂和计算、集合划分 |
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
