本文主要是介绍贝尔数,两类斯特灵数的计算公式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
第一类斯特灵数:含正负值,其绝对值是包含n个元素的集合分作k个环排列的方法数目。
递推公式 s(n,0)=0,s(1,1)=1,s(n,k)=s(n-1,k-1)+(n-1)*s(n-1,k)
第二类斯特灵数:把包含n个元素的集合划分为正好k个非空子集的方法的数目。
递推公式 s(n,k)=s(n-1,k-1)+k*s(n-1,k)
贝尔数 Bn表示包含n个元素的集合的划分方法的数目
递推公式 B0=1 Bn+1=(n,0)*B0+(n,1)*B1+(n,2)*B2+...+(n,n)Bn
可见贝尔数是第二类斯特灵数的和,即 Bn=s(n,1)+s(n,2)+...s(n,n)
贝尔数和斯特灵数可以通过构建贝尔三角形a得到
建构方法如下:
1 第一行首项是1(a[1][1]=1)
2 对于n>1,第n行第一项等同第n-1行最后一项(a[n][1]=a[n-1][n-1])
3 对于m,n>1,第n行第m项等于它左边和左上方两个数之和(a[n][m]=a[n][m-1]+a[n-1][m-1]
结果如下
每行首项是Bell数
Bell数的大数计算模板
BigNum类大数模板在我的这篇博客中可以找到 点击打开链接
BigNum a[900 + 5][900 + 5]; //a[n]=Bn-1 Bell数下标从0开始
void marktable_Bell()
{BigNum t(1);a[1][1] = t;for (int i = 2; i <= N; i++)for (int j = 1; j <= i; j++)if (j == 1) a[i][j] = a[i - 1][i - 1];else a[i][j] = a[i][j - 1] + a[i - 1][j - 1];
}
这篇关于贝尔数,两类斯特灵数的计算公式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!