贝尔数

贝尔数（英语：Bell number）是组合数学中的一组整数数列，以埃里克·坦普尔·贝尔命名，首几个贝尔数为：

Bell Number

$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）

性质

$B_{n}$是基数为$n$的集合的划分方法的数目。集合$S$的划分是$S$的两两不相交的非空子集的族，它们的并是$S$。例如，$B_{3}=5$，因为有3个元素的集合$\{a,b,c\}$有5种不同的划分方法： 。

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

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

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

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

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

$B_{0}=1$因为空集正好有1种划分方法。空集的每个成员都是非空集合（这是Vacuous truth，因为空集实际上没有成员），而它们的并是空集本身。所以空集是它的唯一划分。

贝尔数满足递推公式：

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

上述组合公式的证明：

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

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

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

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

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

它们也适合“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=0}^{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&&&&\\\end{array}}$

每行首项是贝尔数。每行之和是第二类Stirling数。

这个三角形称为贝尔三角形、Aitken阵列或Peirce三角形（Bell triangle, Aitken's array, Peirce triangle）。

参考

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