贝尔数 Bell NumbersOI 中的集合划分计数与高效计算【免费下载链接】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_22,B_35,B_415,B_552,B_6203,\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_{n1}\sum_{k0}^n\binom{n}{k}B_{k} $$证明组合意义设 $B_n$ 对应的集合为 ${b_1,b_2,b_3,\dots,b_n}$$B_{n1}$ 对应的集合为 ${b_1,b_2,b_3,\dots,b_n,b_{n1}}$即 $B_{n1}$ 是在 $B_n$ 的基础上增添了一个新元素 $b_{n1}$。围绕新元素 $b_{n1}$ 的归属分类讨论若它被单独分到一类剩余 $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_{k0}^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_{i0}^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_{n1}}{(n 1)!}x^{n 1} \ \hat B(x) \sum_{n 0}^{\infty}\frac{B_{n1}}{n!}x^{n} \end{aligned} $$由贝尔数的递推公式 $B_{n1}\sum_{k0}^n\binom{n}{k}B_k$两边同除以 $n!$ 可得$$ \frac{B_{n1}}{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}}$比较系数后使用Newtons 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_01, B_11, B_22, B_35, B_415, B_552, B_6203$ 可见其增长速度远超指数级实际应用中 $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），仅供参考