贝尔数

贝尔数 $B_{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

$B_{n}$ 是基数为 $n$ 的集合的划分方法的数目。集合 $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}

$B_{0}$ 是 1 因为空集正好有 1 种划分方法。

递推公式

贝尔数适合递推公式：

B_{n + 1} = \sum_{k = 0}^{n} (\binom{n}{k}) B_{k}

证明：

$B_{n + 1}$ 是含有 $n + 1$ 个元素集合的划分个数，设 $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$ 个元素，这种情况下划分数为 $(\binom{n}{n}) B_{n}$ ;
假如它和某 1 个元素分到一类，那么还剩下 $n - 1$ 个元素，这种情况下划分数为 $(\binom{n}{n - 1}) B_{n - 1}$ ；
假如它和某 2 个元素分到一类，那么还剩下 $n - 2$ 个元素，这种情况下划分数为 $(\binom{n}{n - 2}) B_{n - 2}$ ；
……

以此类推就得到了上面的公式。

每个贝尔数都是相应的第二类斯特林数的和。因为第二类斯特林数是把基数为 $n$ 的集合划分为正好 $k$ 个非空集的方法数目。

B_{n} = \sum_{k = 0}^{n} {\binom{n}{k}}

贝尔三角形

用以下方法构造一个三角矩阵（形式类似杨辉三角形）：

$a_{0, 0} = 1$ ；
对于 $n \geq 1$ ，第 $n$ 行首项等于上一行的末项，即 $a_{n, 0} = a_{n - 1, n - 1}$ ；
对于 $m, n \geq 1$ ，第 $n$ 行第 $m$ 项等于它左边和左上角两个数之和，即 $a_{n, m} = a_{n, m - 1} + a_{n - 1, m - 1}$ 。

部分结果如下：

\begin{aligned} 1 \\ 1 2 \\ 2 3 5 \\ 5 7 10 15 \\ 15 20 27 37 52 \\ 52 67 87 114 151 203 \\ 203 255 322 409 523 674 877 \end{aligned}

每行的首项是贝尔数。可以利用这个三角形来递推求出贝尔数。

参考实现

C++Python

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]

指数生成函数

考虑贝尔数的指数生成函数及其导函数：

\begin{aligned} \hat{B} (x) & = \sum_{n = 0}^{+ \infty} \frac{B_{n}}{n!} x^{n} \\ = 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}

根据贝尔数的递推公式可以得到：

\frac{B_{n + 1}}{n!} = \sum_{k = 0}^{n} \frac{1}{(n - k)!} \frac{B_{k}}{k!}

这是一个卷积的式子，因此有：

{\hat{B}}^{'} (x) = e^{x} \hat{B} (x)

这是一个微分方程，解得：

\hat{B} (x) = \exp (e^{x} + C)

最后当 $x = 0$ 时 $\hat{B} (x) = 1$ ，带入后解得 $C = - 1$ ，得到贝尔数指数生成函数的封闭形式：

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

预处理出 $e^{x} - 1$ 的前 $n$ 项后做一次多项式 exp 即可得出贝尔数前 $n$ 项，时间复杂度瓶颈在多项式 exp，可做到 $O (n \log n)$ 的时间复杂度。

参考文献

https://en.wikipedia.org/wiki/Bell_number

本页面最近更新：2024/10/9 22:38:42，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, Xeonacid, ksyx, Tiphereth-A, Great-designer, iamtwz, Ir1d, LDlornd, Menci, Running-Turtle1, ShaoChenHeng, shawlleyw, StudyingFather, untitledunrevised
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用