贝尔数
贝尔数 \(B_n\) 以埃里克·坦普尔·贝尔命名，是组合数学中的一组整数数列，开首是（OEIS A000110）：
\(B_n\) 是基数为 \(n\) 的集合的划分方法的数目。集合 \(S\) 的一个划分是定义为 \(S\) 的两两不相交的非空子集的族，它们的并是 \(S\)。例如 \(B_3 = 5\) 因为 3 个元素的集合 \({a, b, c}\) 有 5 种不同的划分方法：
\(B_0\) 是 1 因为空集正好有 1 种划分方法。
递推公式¶
贝尔数适合递推公式：
证明：
\(B_{n+1}\) 是含有 \(n+1\) 个元素集合的划分个数，设 \(D_n\) 的集合为 \(\{b_1,b_2,b_3,\dots,b_n\}\)，\(D_{n+1}\) 的集合为 \(\{b_1,b_2,b_3,\dots,b_n,b_{n+1}\}\)，那么可以认为 \(D_{n+1}\) 是有 \(D_{n}\) 增添了一个 \(b_{n+1}\) 而产生的，考虑元素 \(b_{n+1}\)。
-
假如它被单独分到一类，那么还剩下 \(n\) 个元素，这种情况下划分数为 \(\dbinom{n}{n}B_{n}\);
-
假如它和某 1 个元素分到一类，那么还剩下 \(n-1\) 个元素，这种情况下划分数为 \(\dbinom{n}{n-1}B_{n-1}\)；
-
假如它和某 2 个元素分到一类，那么还剩下 \(n-2\) 个元素，这种情况下划分数为 \(\dbinom{n}{n-2}B_{n-2}\)；
-
……
以此类推就得到了上面的公式。
每个贝尔数都是相应的 第二类斯特林数 的和。 因为第二类斯特林数是把基数为 \(n\) 的集合划分为正好 \(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}\)。
部分结果如下：
每行的首项是贝尔数。可以利用这个三角形来递推求出贝尔数。
参考实现
const 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]
指数生成函数¶
考虑贝尔数的指数生成函数及其导函数：
根据贝尔数的递推公式可以得到：
这是一个卷积的式子，因此有：
这是一个微分方程，解得：
最后当 \(x = 0\) 时 \(\hat B(x) = 1\)，带入后解得 \(C = -1\)，得到贝尔数指数生成函数的封闭形式：
预处理出 \(\mathrm{e}^x - 1\) 的前 \(n\) 项后做一次 多项式 exp 即可得出贝尔数前 \(n\) 项，时间复杂度瓶颈在多项式 exp，可做到 \(O(n \log n)\) 的时间复杂度。