跳转至

# 贝尔数

贝尔数 𝐵 𝑛 B n 以埃里克·坦普尔·贝尔命名，是组合数学中的一组整数数列，开首是（OEIS A000110）：

𝐵 0=1,𝐵 1=1,𝐵 2=2,𝐵 3=5,𝐵 4=1 5,𝐵 5=5 2,𝐵 6=2 0 3,…B 0=1,B 1=1,B 2=2,B 3=5,B 4=15,B 5=52,B 6=203,…

𝐵 𝑛 B n 是基数为 𝑛 n 的集合的划分方法的数目．集合 𝑆 S 的一个划分是定义为 𝑆 S 的两两不相交的非空子集的族，它们的并是 𝑆 S．例如 𝐵 3 =5 B 3=5 因为 3 个元素的集合 𝑎,𝑏,𝑐 a,b,c 有 5 种不同的划分方法：

{{𝑎},{𝑏},{𝑐}}{{𝑎},{𝑏,𝑐}}{{𝑏},{𝑎,𝑐}}{{𝑐},{𝑎,𝑏}}{{𝑎,𝑏,𝑐}}{{a},{b},{c}}{{a},{b,c}}{{b},{a,c}}{{c},{a,b}}{{a,b,c}}

𝐵 0 B 0 是 1 因为空集正好有 1 种划分方法．

## 递推公式

贝尔数适合递推公式：

𝐵 𝑛+1=𝑛∑𝑘=0(𝑛 𝑘)𝐵 𝑘 B n+1=∑k=0 n(n k)B k

证明：

𝐵 𝑛+1 B n+1 是含有 𝑛 +1 n+1 个元素集合的划分个数，设 𝐵 𝑛 B n 的集合为 {𝑏 1,𝑏 2,𝑏 3,…,𝑏 𝑛}{b 1,b 2,b 3,…,b n}，𝐵 𝑛+1 B n+1 的集合为 {𝑏 1,𝑏 2,𝑏 3,…,𝑏 𝑛,𝑏 𝑛+1}{b 1,b 2,b 3,…,b n,b n+1}，那么可以认为 𝐵 𝑛+1 B n+1 是有 𝐵 𝑛 B n 增添了一个 𝑏 𝑛+1 b n+1 而产生的，考虑元素 𝑏 𝑛+1 b n+1．

- 假如它被单独分到一类，那么还剩下 𝑛 n 个元素，这种情况下划分数为 (𝑛 𝑛)𝐵 𝑛(n n)B n;

- 假如它和某 1 个元素分到一类，那么还剩下 𝑛 −1 n−1 个元素，这种情况下划分数为 (𝑛 𝑛−1)𝐵 𝑛−1(n n−1)B n−1；

- 假如它和某 2 个元素分到一类，那么还剩下 𝑛 −2 n−2 个元素，这种情况下划分数为 (𝑛 𝑛−2)𝐵 𝑛−2(n n−2)B n−2；

- ……

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

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

𝐵 𝑛=𝑛∑𝑘=0{𝑛 𝑘}B n=∑k=0 n{n k}

## 贝尔三角形

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

- 𝑎 0,0 =1 a 0,0=1；
- 对于 𝑛 ≥1 n≥1，第 𝑛 n 行首项等于上一行的末项，即 𝑎 𝑛,0 =𝑎 𝑛−1,𝑛−1 a n,0=a n−1,n−1；
- 对于 𝑚,𝑛 ≥1 m,n≥1，第 𝑛 n 行第 𝑚 m 项等于它左边和左上角两个数之和，即 𝑎 𝑛,𝑚 =𝑎 𝑛,𝑚−1 +𝑎 𝑛−1,𝑚−1 a n,m=a n,m−1+a n−1,m−1．

部分结果如下：

1 1 2 2 3 5 5 7 1 0 1 5 1 5 2 0 2 7 3 7 5 2 5 2 6 7 8 7 1 1 4 1 5 1 2 0 3 2 0 3 2 5 5 3 2 2 4 0 9 5 2 3 6 7 4 8 7 7 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

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

参考实现
C++Python

     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]

## 指数生成函数

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

ˆ 𝐵(𝑥)=+∞∑𝑛=0 𝐵 𝑛 𝑛!𝑥 𝑛=1++∞∑𝑛=0 𝐵 𝑛+1(𝑛+1)!𝑥 𝑛+1 ˆ 𝐵′(𝑥)=+∞∑𝑛=0 𝐵 𝑛+1 𝑛!𝑥 𝑛 B^(x)=∑n=0+∞B n n!x n=1+∑n=0+∞B n+1(n+1)!x n+1 B^′(x)=∑n=0+∞B n+1 n!x n

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

𝐵 𝑛+1 𝑛!=𝑛∑𝑘=0 1(𝑛−𝑘)!𝐵 𝑘 𝑘!B n+1 n!=∑k=0 n 1(n−k)!B k k!

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

ˆ 𝐵′(𝑥)=e 𝑥 ˆ 𝐵(𝑥)B^′(x)=e x B^(x)

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

ˆ 𝐵(𝑥)=e x p⁡(e 𝑥+𝐶)B^(x)=exp⁡(e x+C)

最后当 𝑥 =0 x=0 时 ˆ 𝐵(𝑥) =1 B^(x)=1，带入后解得 𝐶 = −1 C=−1，得到贝尔数指数生成函数的封闭形式：

ˆ 𝐵(𝑥)=e x p⁡(e 𝑥−1)B^(x)=exp⁡(e x−1)

预处理出 e 𝑥 −1 e x−1 的前 𝑛 n 项后做一次 多项式 exp 即可得出贝尔数前 𝑛 n 项，时间复杂度瓶颈在多项式 exp，可做到 𝑂(𝑛 l o g⁡𝑛)O(n log⁡n) 的时间复杂度．

## 参考文献

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

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