贝尔数

维基百科，自由的百科全书

跳转到: 导航, 搜索

贝尔数以埃里克·坦普尔·貝尔(Eric Temple Bell)為名，是組合數學中的一組整數數列，開首是（OEIS的A000110數列）：

$B_0=1,\quad B_1=1,\quad B_2=2,\quad B_3=5,\quad B_4=15,\quad B_5=52,\quad B_6=203,\quad\dots$

B_n是基數為n的集合的劃分方法的數目。集合S的一個劃分是定義為S的兩兩不相交的非空子集的族，它們的並是S。例如B₃ = 5因為3個元素的集合{a, b, c}有5種不同的劃分方法：

{{a}, {b}, {c}}

{{a}, {b, c}}

{{b}, {a, c}}

{{c}, {a, b}}

B₀是1因為空集正好有1種劃分方法。空集的每個成員都是非空集合（這是空虛的真），而它們的並是空集本身。所以空集是它的唯一劃分。

貝爾數適合遞推公式：

$B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k}.$

它們也適合「Dobinski公式」：

$B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}=$ 期望值為1的泊松分數的n次矩。

它們也適合「Touchard同餘」：若p是任意質數，那麼

$B_{p+n}\equiv B_n+B_{n+1}\ (\operatorname{mod}\ p).$

每個貝爾數都是"第二類Stirling數"的和

$B_n=\sum_{k=1}^n S(n,k).$

Stirling數S(n, k)是把基數為n的集劃分為正好k個非空集的方法的數目。

把任一概率分佈的n次矩以首n個累積量表示的多項式，其係數和正是第n個貝爾數。這種數劃分的方法不像用Stirling數那個方法粗糙。

貝爾數的指數母函數是

$\sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.$

[编辑] 貝爾三角形

用以下方法建構一個三角矩陣（形式類似楊輝三角形）：

第一行第一項是1（a_{1,1} = 1）
對於n>1，第n行第一項等同第n-1行最後一項。（ $a n,1 = a n - 1, n - 1$ ）
對於m,n>1，第n行第m項等於它左邊和左上方的兩個數之和。（ $a n, m = a n, m - 1 + a n - 1, m - 1$ ）

結果如下：（OEIS:A011971）

$\begin{array}{cccccccccccccccccc} 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 & &\\ 877 & & 1080 & & 1335 & & 1657 & & 2066 & & 2589 & & 3263 & & 4140 &\\ & & & & &\vdots & & & & \vdots & & & & \vdots& & & & \\ \end{array}$