跳转至

貝爾數

貝爾數 \(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\) 個元素集合的劃分個數，設 \(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\) 個非空集的方法數目。

\[ B_{n} = \sum_{k=0}^n{n\brace 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} \]

每行的首項是貝爾數。可以利用這個三角形來遞推求出貝爾數。

參考實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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];
  }
}

1
2
3
4
5
6
7
8
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) = \mathrm{e}^x \hat B(x) \]

這是一個微分方程，解得：

\[ \hat B(x) = \exp\left(\mathrm{e}^x + C\right) \]

最後當 \(x = 0\) 時 \(\hat B(x) = 1\)，帶入後解得 \(C = -1\)，得到貝爾數指數生成函數的封閉形式：

\[ \hat B(x) = \exp\left(\mathrm{e}^x - 1\right) \]

預處理出 \(\mathrm{e}^x - 1\) 的前 \(n\) 項後做一次 多項式 exp 即可得出貝爾數前 \(n\) 項，時間複雜度瓶頸在多項式 exp，可做到 \(O(n \log n)\) 的時間複雜度。

參考文獻

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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用