贝尔数
贝尔数以埃里克·坦普尔·贝尔命名,是组合数学中的一组整数数列,开首是 (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 个元素,这种情况下划分数为 \binom{n}{n}B_{n};
假如它和某 1 个元素分到一类,那么还剩下 n-1 个元素,这种情况下划分数为 \binom{n}{n-1}B_{n-1};
假如它和某 2 个元素分到一类,那么还剩下 n-2 个元素,这种情况下划分数为 \binom{n}{n-2}B_{n-2};
以此类推就得到了上面的公式。
每个贝尔数都是相应的第二类 斯特林数 的和。 因为第二类斯特林数是把基数为 n 的集合划分为正好 k 个非空集的方法数目。
B_{n} = \sum_{k=0}^nS(n,k)
贝尔三角形¶
用以下方法构造一个三角矩阵(形式类似杨辉三角形):
- 第一行第一项为 1 (a_{1,1}=1);
- 对于 n>1,第 n 行第一项等于第 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})
部分结果如下:
\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}
每行的首项是贝尔数。可以利用这个三角形来递推求出 Bell 数。
参考实现
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 |
|
参考文献¶
https://en.wikipedia.org/wiki/Bell_number
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用