贝尔数
贝尔数以埃里克·坦普尔·贝尔命名,是组合数学中的一组整数数列,开首是 ( OEIS A000110 ):
是基数为 的集合的划分方法的数目。集合 的一个划分是定义为 的两两不相交的非空子集的族,它们的并是 。例如 因为 3 个元素的集合 有 5 种不同的划分方法:
是 1 因为空集正好有 1 种划分方法。
公式
贝尔数适合递推公式:
证明:
是含有 个元素集合的划分个数,设 的集合为 , 的集合为 ,那么可以认为 是有 增添了一个 而产生的,考虑元素 。
假如它被单独分到一类,那么还剩下 个元素,这种情况下划分数为 ;
假如它和某 1 个元素分到一类,那么还剩下 个元素,这种情况下划分数为 ;
假如它和某 2 个元素分到一类,那么还剩下 个元素,这种情况下划分数为 ;
以此类推就得到了上面的公式。
每个贝尔数都是相应的第二类 斯特林数 的和。 因为第二类斯特林数是把基数为 的集合划分为正好 个非空集的方法数目。
贝尔三角形
用以下方法构造一个三角矩阵(形式类似杨辉三角形):
- 第一行第一项为 1 ;
- 对于 ,第 行第一项等于第 行的第 项 ;
- 对于 ,第 行的第 项等于它左边和左上角两个数之和
部分结果如下:
每行的首项是贝尔数。可以利用这个三角形来递推求出 Bell 数。
参考实现
| const int maxn = 2000 + 5;
int bell[maxn][maxn];
void f(int n) {
bell[1][1] = 1;
for (int i = 2; i <= n; i++) {
bell[i][1] = bell[i - 1][i - 1];
for (int j = 2; j <= i; j++)
bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1];
}
}
|
参考文献
https://en.wikipedia.org/wiki/Bell_number
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用