贝尔数

淩亂°似流年 2022-05-31 08:35 1141阅读 0赞

# [转载博主][Link 1]    #

# [贝尔数（来自维基百科）& Stirling数][Link 1] #

# [贝尔数][Link 2] #

贝尔数以[埃里克·坦普尔·贝尔][Link 3]（Eric Temple Bell）为名，是[组合数学][Link 4]中的一组[整数][Link 5][数列][Link 6]，开首是（[OEIS][]的A000110数列）：

[![220px-Bell_Number.png][]][220px-Bell_Number.png 1]

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][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]

Bn是[基数][Link 7]为n的集合的[划分][Link 8]方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合\{ a, b, c\}有5种不同的划分方法：

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

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

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

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

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

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

贝尔数适合递推公式：

![B\_\{n+1\}=\\sum\_\{k=0\}^\{n\}\{\{n \\choose k\}B\_k\}.][B_n_1_sum_k_0_n_n _choose k_B_k_.]

上述组合公式的证明：

可以这样来想，B\_\{n+1\}是含有n+1个元素集合的划分的个数，考虑元素![b\_\{n+1\}.][b_n_1_.]

假设他被单独划分到一类，那么还剩下n个元素，这种情况下划分个数为![\{n \\choose n\}B\_\{n\}][n _choose n_B_n]；

假设他和某一个元素被划分为一类，那么还剩下n-1个元素，这种情况下划分个数为 ![\{n \\choose n-1\}B\_\{n-1\}][n _choose n-1_B_n-1]；

假设他和某两个元素被划分为一类，那么还剩下n-2个元素，这种情况下划分个数为 ![\{n \\choose n-2\}B\_\{n-2\}][n _choose n-2_B_n-2]；

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

它们也适合“Dobinski公式”：

![B\_n=\\frac\{1\}\{e\}\\sum\_\{k=0\}^\\infty \\frac\{k^n\}\{k!\}][B_n_frac_1_e_sum_k_0_infty _frac_k_n_k] [期望值][Link 9]为1的 [泊松分数][Link 10]的 n次矩。

它们也适合“Touchard同余”：若p是任意[质数][Link 11]，那么

![B\_\{p+n\}\\equiv B\_n+B\_\{n+1\}\\ (\\operatorname\{mod\}\\ p).][B_p_n_equiv B_n_B_n_1_ _operatorname_mod_ p_.]

每个贝尔数都是"第二类[Stirling数][Stirling]"的和

![B\_n=\\sum\_\{k=1\}^n S(n,k).][B_n_sum_k_1_n S_n_k_.]

Stirling数S（n, k）是把基数为n的集划分为正好k个非空集的方法的数目。

把任一[概率分布][Link 12]的n次[矩][Link 13]以首n个[累积量][Link 14]表示的多项式，其系数和正是第n个贝尔数。这种数划分的方法不像用Stirling数那个方法粗糙。

贝尔数的[指数母函数][Link 15]是

![\\sum\_\{n=0\}^\\infty \\frac\{B\_n\}\{n!\} x^n = e^\{e^x-1\}.][sum_n_0_infty _frac_B_n_n_ x_n _ e_e_x-1_.]

## 贝尔三角形\[[编辑][Link 16]\] ##

用以下方法建构一个三角矩阵（形式类似[杨辉三角形][Link 17]）：

*  第一行第一项是1（![a\_\{1,1\} = 1][a_1_1_ _ 1]）
 *  对于n>1，第n行第一项等同第n-1行最后一项。（![a\_\{n,1\} = a\_\{n-1,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\}][a_n_m_ _ a_n_m-1_ _ a_n-1_m-1]）

结果如下：（[OEIS:A011971][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\}][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]

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

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

[Link 1]: http://www.cnblogs.com/yuyixingkong/p/4480349.html
[Link 2]: http://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%95%B0
[Link 3]: http://zh.wikipedia.org/w/index.php?title=%E5%9F%83%E9%87%8C%E5%85%8B%C2%B7%E5%9D%A6%E6%99%AE%E5%B0%94%C2%B7%E8%B2%9D%E5%B0%94&action=edit&redlink=1
[Link 4]: http://zh.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E6%95%B8%E5%AD%B8
[Link 5]: http://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B8
[Link 6]: http://zh.wikipedia.org/wiki/%E6%95%B0%E5%88%97
[OEIS]: http://zh.wikipedia.org/wiki/OEIS
[220px-Bell_Number.png]: /images/20220531/d0d8a26e84f84c269650423ca7f5b2aa.png
[220px-Bell_Number.png 1]: http://zh.wikipedia.org/wiki/File:Bell_Number.png
[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]: /images/20220531/397b9d0dac1345c7ad0232eafb800a08.png
[Link 7]: http://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B8
[Link 8]: http://zh.wikipedia.org/w/index.php?title=%E9%9B%86%E7%9A%84%E5%8A%83%E5%88%86&action=edit&redlink=1
[Vacuous truth]: http://zh.wikipedia.org/w/index.php?title=Vacuous_truth&action=edit&redlink=1
[B_n_1_sum_k_0_n_n _choose k_B_k_.]: /images/20220531/42d4aa3d0a3f4f86a2d5dcc7edd1f1db.png
[b_n_1_.]: /images/20220531/2d2fddfddfbd425480383d1aa5500c62.png
[n _choose n_B_n]: /images/20220531/94bd0d357a684fa1ae876b06e5f7abb2.png
[n _choose n-1_B_n-1]: /images/20220531/1977900d6a364bb6835dae62d82bd5c2.png
[n _choose n-2_B_n-2]: /images/20220531/22d32221847f4d26af159eff0f7fa2fe.png
[B_n_frac_1_e_sum_k_0_infty _frac_k_n_k]: http://upload.wikimedia.org/math/1/1/a/11afe324b2aaf380ecd21d2e8bd38448.png
[Link 9]: http://zh.wikipedia.org/wiki/%E6%9C%9F%E6%9C%9B%E5%80%BC
[Link 10]: http://zh.wikipedia.org/w/index.php?title=%E6%B3%8A%E6%9D%BE%E5%88%86%E6%95%B8&action=edit&redlink=1
[Link 11]: http://zh.wikipedia.org/wiki/%E8%B3%AA%E6%95%B8
[B_p_n_equiv B_n_B_n_1_ _operatorname_mod_ p_.]: /images/20220531/93c619eb63ca483ab4f8a4f90f3afcff.png
[Stirling]: http://zh.wikipedia.org/wiki/Stirling%E6%95%B8
[B_n_sum_k_1_n S_n_k_.]: /images/20220531/186fe83a4c0d46c7bbab1f2fb8963797.png
[Link 12]: http://zh.wikipedia.org/wiki/%E6%A6%82%E7%8E%87%E5%88%86%E5%B8%83
[Link 13]: http://zh.wikipedia.org/wiki/%E7%9F%A9
[Link 14]: http://zh.wikipedia.org/wiki/%E7%B4%AF%E7%A9%8D%E9%87%8F
[Link 15]: http://zh.wikipedia.org/wiki/%E6%AF%8D%E5%87%BD%E6%95%B0
[sum_n_0_infty _frac_B_n_n_ x_n _ e_e_x-1_.]: /images/20220531/6ea8a04fb17b48b0927a2e3d68248dc6.png
[Link 16]: http://zh.wikipedia.org/w/index.php?title=%E8%B4%9D%E5%B0%94%E6%95%B0&action=edit&section=1
[Link 17]: http://zh.wikipedia.org/wiki/%E6%A5%8A%E8%BC%9D%E4%B8%89%E8%A7%92%E5%BD%A2
[a_1_1_ _ 1]: /images/20220531/653a9de027074338b41385bf22e4945c.png
[a_n_1_ _ a_n-1_n-1]: /images/20220531/59449ec936534ae09f9133ca2377f336.png
[a_n_m_ _ a_n_m-1_ _ a_n-1_m-1]: /images/20220531/86e06578d1624394b4ac054cbc564c96.png
[OEIS_A011971]: http://oeis.org/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]: /images/20220531/fb4350159da3423f99045a0ddc2657d5.png