贝尔数 Bell Numbers：OI 中的集合划分计数与高效计算
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
贝尔数 $B_n$ 是组合数学中一组以数学家埃里克·坦普尔·贝尔（Eric Temple Bell）命名的整数数列，刻画的是「将 $n$ 个互不相同的元素划分为若干非空子集」的方案总数。本文围绕 docs/math/combinatorics/bell.md 的核心内容展开，系统梳理贝尔数的定义、递推公式、贝尔三角形构造以及基于指数生成函数与多项式 $\exp$ 的 $O(n\log n)$ 计算方法，并补充仓库中第二类斯特林数、EGF 与多项式运算的源码级依据，帮助读者在 OI/ICPC 竞赛中快速识别、推导并实现贝尔数相关问题。
定义：集合划分的计数
贝尔数$B_n$ 是基数为 $n$ 的集合的划分方法数目（OEIS A000110），数列开头为：
$$ B_0 = 1,B_1 = 1,B_2=2,B_3=5,B_4=15,B_5=52,B_6=203,\dots $$
所谓「集合 $S$ 的一个划分」，是指 $S$ 的两两不相交的非空子集的族，且它们的并恰好是 $S$。以 $B_3 = 5$ 为例：3 个元素的集合 ${a, b, c}$ 共有 5 种不同的划分方法：
$$ \begin{aligned} &{ {a},{b},{c}} \ &{ {a},{b,c}} \ &{ {b},{a,c}} \ &{ {c},{a,b}} \ &{ {a,b,c}} \ \end{aligned} $$
注意：划分中的子集之间互不区分，因此 ${{a},{b,c}}$ 与 ${{b,c},{a}}$ 被视为同一种划分；同时每个子集必须非空。$B_0 = 1$ 是因为空集恰好只有 1 种划分（即不划分任何子集的空族）。
递推公式及其组合证明
贝尔数满足如下的递推公式：
$$ B_{n+1}=\sum_{k=0}^n\binom{n}{k}B_{k} $$
证明（组合意义）：设 $B_n$ 对应的集合为 ${b_1,b_2,b_3,\dots,b_n}$，$B_{n+1}$ 对应的集合为 ${b_1,b_2,b_3,\dots,b_n,b_{n+1}}$，即 $B_{n+1}$ 是在 $B_n$ 的基础上增添了一个新元素 $b_{n+1}$。围绕新元素 $b_{n+1}$ 的归属分类讨论：
- 若它被单独分到一类，剩余 $n$ 个元素的划分数为 $\dbinom{n}{n}B_{n}$；
- 若它和某 1 个元素分到一类，先从 $n$ 个元素中选出这 1 个元素（$\binom{n}{n-1}$ 种选择，等价于选出与它同组的元素后剩余 $n-1$ 个元素自由划分），方案数为 $\dbinom{n}{n-1}B_{n-1}$；
- 若它和某 2 个元素分到一类，方案数为 $\dbinom{n}{n-2}B_{n-2}$；
- ……
对 $k$ 从 $0$ 到 $n$ 求和即得递推公式。该公式本质上是按新元素所在块的规模进行分类的计数，是贝尔数一切递推性质的基石。
与第二类斯特林数的关系
每个贝尔数都是相应第二类斯特林数之和：
$$ B_{n} = \sum_{k=0}^n{n\brace k} $$
这是因为第二类斯特林数 $\begin{Bmatrix}n\ k\end{Bmatrix}$（也称斯特林子集数，见 docs/math/combinatorics/stirling.md）恰好表示「将基数为 $n$ 的集合划分为正好 $k$ 个非空子集的方法数目」。由于集合的划分可以包含任意数量的非空块，把 $k = 0, 1, \dots, n$ 的所有方案数累加，就得到了不分块数的总划分数 $B_n$。
第二类斯特林数自身满足递推：
$$ \begin{Bmatrix}n\ k\end{Bmatrix}=\begin{Bmatrix}n-1\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\ k\end{Bmatrix} $$
其组合含义为：插入新元素时，要么单独放入一个新子集（$\begin{Bmatrix}n-1\ k-1\end{Bmatrix}$），要么放入某个已有的非空子集（$k\begin{Bmatrix}n-1\ k\end{Bmatrix}$）。借助该递推可以在 $O(nk)$ 时间内先算出同一行的斯特林数，再对 $k$ 求和得到贝尔数，这也为不引入生成函数时的朴素实现提供了思路。
贝尔三角形：逐行递推的实用构造
贝尔数还可以通过一种形式类似杨辉三角形的三角矩阵来递推求出。构造规则如下：
- $a_{0,0} = 1$；
- 对于 $n \ge 1$，第 $n$ 行首项等于上一行的末项，即 $a_{n,0}=a_{n-1,n-1}$；
- 对于 $m,n \ge 1$，第 $n$ 行第 $m$ 项等于它左边和左上角两个数之和，即 $a_{n,m}=a_{n,m-1}+a_{n-1,m-1}$。
部分结果如下：
$$ \begin{aligned} & 1 \ & 1\quad\qquad 2 \ & 2\quad\qquad 3\quad\qquad 5 \ & 5\quad\qquad 7\quad\qquad 10,,,\qquad 15 \ & 15,,,\qquad 20,,,\qquad 27,,,\qquad 37,,,\qquad 52 \ & 52,,,\qquad 67,,,\qquad 87,,,\qquad 114\qquad 151\qquad 203\ & 203\qquad 255\qquad 322\qquad 409\qquad 523\qquad 674\qquad 877 \ \end{aligned} $$
每行的首项 $a_{n,0}$ 就是贝尔数 $B_n$，因此利用该三角形可以从 $O(n)$ 的空间、$O(n^2)$ 的时间逐行推出前 $n$ 个贝尔数。注意每一行的末项恰好等于下一行的首项，这正是三角形「行首接行尾」的锯齿状衔接结构。
参考实现
来自 docs/math/combinatorics/bell.md 的参考实现（适用于 $n \le 2000$ 左右、值在所选类型范围内的情况；数值更大时需换用高精度或模意义下的写法）：
constexpr int MAXN = 2000 + 5; int bell[MAXN][MAXN]; void f(int n) { bell[0][0] = 1; for (int i = 1; i <= n; i++) { bell[i][0] = bell[i - 1][i - 1]; for (int j = 1; j <= i; j++) bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]; } }MAXN = 2000 + 5 bell = [[0 for i in range(MAXN + 1)] for j in range(MAXN + 1)] def f(n): bell[0][0] = 1 for i in range(1, n + 1): bell[i][0] = bell[i - 1][i - 1] for j in range(1, i + 1): bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]实现要点：外层循环第 $i$ 行先利用上一行末项确定行首，再逐列按「左 + 左上」递推；最终 $B_n$ 位于bell[n][0]。若只需输出一行，可将二维数组滚动优化为一维，但需注意行首值取自上一行末项，滚动时需暂存该值。
指数生成函数：封闭形式的推导
贝尔数求和式与 $\binom{n}{k}$ 的卷积结构暗示了使用**指数生成函数（EGF）**的动机——指数生成函数的定义与乘法性质参见 docs/math/poly/egf.md（序列 $\langle a_n\rangle$ 的 EGF 定义为 $\hat F(x)=\sum_n a_n \frac{x^n}{n!}$，其乘法对应二项卷积 $\sum_{i=0}^n\binom{n}{i}a_i b_{n-i}$）。
设贝尔数的指数生成函数为：
$$ \hat B(x) = \sum_{n = 0}^{+\infty}\frac{B_n}{n!}x^n $$
展开并求导得：
$$ \begin{aligned} \hat B(x) &= 1 + \sum_{n = 0}^{+\infty}\frac{B_{n+1}}{(n + 1)!}x^{n + 1} \ \hat B'(x) &= \sum_{n = 0}^{+\infty}\frac{B_{n+1}}{n!}x^{n} \end{aligned} $$
由贝尔数的递推公式 $B_{n+1}=\sum_{k=0}^n\binom{n}{k}B_k$，两边同除以 $n!$ 可得：
$$ \frac{B_{n+1}}{n!} = \sum_{k = 0}^{n}\frac{1}{(n-k)!}\frac{B_{k}}{k!} $$
右侧正是序列 $\left\langle \dfrac{1}{n!} \right\rangle$ 与 $\left\langle \dfrac{B_n}{n!} \right\rangle$ 的卷积，因此：
$$ \hat B'(x) = \mathrm{e}^x \hat B(x) $$
解这个一阶常微分方程：
$$ \hat B(x) = \exp\left(\mathrm{e}^x + C\right) $$
利用初值条件：当 $x = 0$ 时 $\hat B(0) = B_0 = 1$，代入得 $C = -1$，最终得到贝尔数指数生成函数的封闭形式：
$$ \boxed{\ \hat B(x) = \exp\left(\mathrm{e}^x - 1\right)\ } $$
高效计算：多项式 exp 与 O(n log n) 算法
由封闭形式 $\hat B(x)=\exp(\mathrm{e}^x-1)$ 可以得到一条计算贝尔数前 $n$ 项的高效路径：
- 预处理$\mathrm{e}^x - 1$ 的前 $n$ 项：即序列 $\langle 0, 1, \frac{1}{2!}, \frac{1}{3!}, \dots \rangle$（因为 $\mathrm{e}^x=\sum_{n\ge0}\frac{x^n}{n!}$，常数项 $1$ 减去后首项为 $0$——这恰好满足多项式 $\exp$ 对常数项必须为 $0$ 的收敛条件）；
- 对该多项式做一次多项式 $\exp$，得到 $\hat B(x)$ 的前 $n$ 项系数 $\dfrac{B_n}{n!}$；
- 逐项乘以 $n!$ 还原出 $B_0, B_1, \dots, B_{n-1}$。
其中多项式 $\exp$ 的实现可见 docs/math/poly/elementary-func.md：通过求导得到 $\frac{\mathrm{d} \exp{f(x)}}{\mathrm{d} x} \equiv \exp{f(x)}f'(x)\pmod{x^{n}}$，比较系数后使用Newton's Method（牛顿迭代）求解，时间复杂度为 $O(n\log n)$（普通分治 FFT 做法为 $O(n\log^2 n)$）。从该文档的参考实现可以看到，polyexp的核心是迭代式
$$ f = f_0\left(1 - \ln f_0 + h\right) $$
其中每一步需要调用一次多项式求 $\ln$（求导 + 求逆 + 卷积）。因此求贝尔数前 $n$ 项的时间复杂度瓶颈正是多项式 $\exp$，总复杂度可做到 $O(n\log n)$。
数值范围与竞赛实战提醒
- 贝尔数增长极快：从首项 $B_0=1, B_1=1, B_2=2, B_3=5, B_4=15, B_5=52, B_6=203$ 可见其增长速度远超指数级，实际应用中 $B_n$ 通常需要取模（OI 中常用模数如 $998244353$，其原根为 $3$，见 docs/math/combinatorics/stirling.md 中多项式类的取模设定）或使用高精度。
- 方法选型：$n$ 较小（如 $n \le 2000$）时，贝尔三角形递推 $O(n^2)$ 简单可靠；$n$ 较大（如 $n \ge 10^5$）时，应使用生成函数 + 多项式 $\exp$ 的 $O(n\log n)$ 做法。
- 与斯特林数的联动：题目若给出「恰好划分成 $k$ 个块」的约束，应转向第二类斯特林数；只有不限制块数时才退化为贝尔数。两者结合可覆盖绝大多数「集合划分」类计数问题。
参考文献
- docs/math/combinatorics/bell.md：贝尔数定义、递推、贝尔三角形与 EGF 推导的原始出处
- docs/math/combinatorics/stirling.md：第二类斯特林数的递推式、通项公式与同一行计算
- docs/math/poly/egf.md：指数生成函数的定义与乘法（二项卷积）性质
- docs/math/poly/elementary-func.md：多项式对数/指数函数的求解与牛顿迭代实现
- 维基百科 Bell number 词条（原文所引用的外部参考资料）
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
