跳转至

贝尔数

贝尔数 以埃里克·坦普尔·贝尔命名,是组合数学中的一组整数数列,开首是(OEIS A000110):

是基数为 的集合的划分方法的数目。集合 的一个划分是定义为 的两两不相交的非空子集的族,它们的并是 。例如 因为 3 个元素的集合 有 5 种不同的划分方法:

是 1 因为空集正好有 1 种划分方法。

递推公式

贝尔数适合递推公式:

证明:

是含有 个元素集合的划分个数,设 的集合为 的集合为 ,那么可以认为 是有 增添了一个 而产生的,考虑元素

  • 假如它被单独分到一类,那么还剩下 个元素,这种情况下划分数为 ;

  • 假如它和某 1 个元素分到一类,那么还剩下 个元素,这种情况下划分数为

  • 假如它和某 2 个元素分到一类,那么还剩下 个元素,这种情况下划分数为

  • ……

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

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

贝尔三角形

用以下方法构造一个三角矩阵(形式类似杨辉三角形):

  • 对于 ,第 行首项等于上一行的末项,即
  • 对于 ,第 行第 项等于它左边和左上角两个数之和,即

部分结果如下:

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

参考实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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];
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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]

指数生成函数

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

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

这是一个卷积的式子,因此有:

这是一个微分方程,解得:

最后当 ,带入后解得 ,得到贝尔数指数生成函数的封闭形式:

预处理出 的前 项后做一次 多项式 exp 即可得出贝尔数前 项,时间复杂度瓶颈在多项式 exp,可做到 的时间复杂度。

参考文献

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