首页 > ACM题库 > HDU-杭电 > HDU 4767-Bell-数论-[解题报告]HOJ
2015
09-17

HDU 4767-Bell-数论-[解题报告]HOJ

Bell

问题描述 :

What? MMM is learning Combinatorics!?
Looks like she is playing with the bell sequence now:
bell[n] = number of ways to partition of the set {1, 2, 3, …, n}

e.g. n = 3:
{1, 2, 3}
{1} {2 3}
{1, 2} {3}
{1, 3} {2}
{1} {2} {3}
so, bell[3] = 5

MMM wonders how to compute the bell sequence efficiently.

输入:

T — number of cases
for each case:
  n (1 <= n < 2^31)

输出:

T — number of cases
for each case:
  n (1 <= n < 2^31)

样例输入:

6
1
2
3
4
5
6

样例输出:

1
2
5
15
52
203

斯特灵数[编辑]

维基百科,自由的百科全书

在组合数学,Stirling数可指两类数,都是由18世纪数学家James
Stirling提出的。

第一类[编辑]

Bell

s(4,2)=11

第一类Stirling数是有正负的,其绝对值是Bell个元素的项目分作Bell个环排列的方法数目。常用的表示方法有Bell

换个较生活化的说法,就是有Bell个人分成Bell组,每组内再按特定顺序围圈的分组方法的数目。例如Bell

  1. {A,B},{C,D}
  2. {A,C},{B,D}
  3. {A,D},{B,C}
  4. {A},{B,C,D}
  5. {A},{B,D,C}
  6. {B},{A,C,D}
  7. {B},{A,D,C}
  8. {C},{A,B,D}
  9. {C},{A,D,B}
  10. {D},{A,B,C}
  11. {D},{A,C,B}

这可以用有向图来表示。

  • 给定Bell,有递归关系Bell

递推关系的说明:考虑第n+1个物品,n+1可以单独构成一个非空循环排列,这样前n种物品构成k-1个非空循环排列,方法数为s(n,k-1);也可以前n种物品构成k个非空循环排列,而第n+1个物品插入第i个物品的左边,这有n*s(n,k)种方法。

  • Bell
  • Bell
  • Bell
  • Bell
  • Bell

Bell调和数的推广。

Bell是递降阶乘多项式的系数:

Bell

第二类[编辑]

第二类Stirling数是Bell个元素的集定义k个等价类的方法数目。常用的表示方法有Bell

换个较生活化的说法,就是有Bell个人分成Bell组的分组方法的数目。例如有甲、乙、丙、丁四人,若所有人分成1组,只有所有人在同一组这个方法,因此Bell;若所有人分成4组,只可以人人独立一组,因此Bell;若分成2组,可以是甲乙一组、丙丁一组,或甲丙一组、乙丁一组,或甲丁一组、乙丙一组,或其中三人同一组另一人独立一组,即是:

  1. {A,B},{C,D}
  2. {A,C},{B,D}
  3. {A,D},{B,C}
  4. {A},{B,C,D}
  5. {B},{A,C,D}
  6. {C},{A,B,D}
  7. {D},{A,B,C}

因此Bell

  • 给定Bell,有递归关系Bell
  • 递推关系的说明:考虑第n个物品,n可以单独构成一个非空集合,此时前n-1个物品构成k-1个非空的不可辨别的集合, 方法数为S(n-1,k-1);也可以前n-1种物品构成k个非空的不可辨别的 集合,第n个物品放入任意一个中,这样有k*S(n-1,k)种方法。
  • Bell
  • Bell
  • Bell
  • Bell

Bell是二项式系数,B_n是贝尔数

两者关系[编辑]

Bell

Bell克罗内克尔δ

参考:http://blog.csdn.net/pi9nc/article/details/12176549