贝尔数

貝爾數（英語：Bell number）是組合數學中的一組整數數列，以埃里克·坦普尔·贝尔命名，首幾個貝爾數為：

Bell Number

${\displaystyle 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 }$ （OEIS數列A000110）

性質

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

${\displaystyle \{\{a\},\{b\},\{c\}\}}$

${\displaystyle \{\{a\},\{b,c\}\}}$

${\displaystyle \{\{b\},\{a,c\}\}}$

${\displaystyle \{\{c\},\{a,b\}\}}$

${\displaystyle \{a,b,c\}}$;

${\displaystyle B_{0}=1}$因為空集正好有1種劃分方法。空集的每個成員都是非空集合（这是Vacuous truth，因为空集实际上没有成員），而它們的並是空集本身。所以空集是它的唯一劃分。

貝爾數滿足遞推公式：

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{{n \choose k}B_{k}}.}$

上述组合公式的证明：

可以这样来想，${\displaystyle B_{n+1}}$是含有n+1个元素集合的划分的个数，考虑元素${\displaystyle b_{n+1}.}$

假设他被单独划分到一类，那么还剩下n个元素，这种情况下划分个数为${\displaystyle {n \choose n}B_{n}}$；

假设他和某一个元素被划分为一类，那么还剩下n-1个元素，这种情况下划分个数为 ${\displaystyle {n \choose n-1}B_{n-1}}$；

假设他和某两个元素被划分为一类，那么还剩下n-2个元素，这种情况下划分个数为 ${\displaystyle {n \choose n-2}B_{n-2}}$；

依次类推，得到了上述组合公式

它們也適合「Dobinski公式」：

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

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

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

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

${\displaystyle B_{n}=\sum _{k=0}^{n}S(n,k).}$

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

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

貝爾數的指數母函數是

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=e^{e^{x}-1}.}$

貝爾三角形

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

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

結果如下：（OEIS:A011971）

${\displaystyle {\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&&&&\\\end{array}}}$

每行首項是貝爾數。每行之和是第二類Stirling數。

這個三角形稱為貝爾三角形、Aitken陣列或Peirce三角形（Bell triangle, Aitken's array, Peirce triangle）。

參考

• http://planetmath.org/?op=getobj&from=objects&id=9059