贝尔数

定义当n为大于等于0的整数时，n个元素的集合{1,2,...,n}可以划分若干个非空子集的个数称为贝尔数。贝尔数以埃里克·坦普尔·贝尔(Eric Temple Bell)的名字命名，贝尔数列开头为：1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751……

举例当n=4时，集合{1,2,3,4}可以划分为15个不同的非空子集如下：

{{1},{2},{3},{4}},

{{1,2},{3},{4}},

{{1,3},{2},{4}},

{{1,4},{2},{3}},

{{2,3},{1},{4}},

{{2,4},{1},{3}},

{{3,4},{1},{2}},

{{1,2},{3,4}},

{{1,3},{2,4}},

{{1,4},{2,3}},

{{1,2,3},{4}},

{{1,2,4},{3}},

{{1,3,4},{2}},

{{2,3,4},{1}},

{{1,2,3,4}}

程序计算贝尔数的程序如下：（VC++环境下调试通过）

1. #include<iostream>

2. using namespace std;

3. unsigned __int64 c(int n,int m)

4. {

5. if(m>n/2) m=n-m;

6. int i;

7. unsigned __int64 a=1,b=1;

8. for(i=n;i>n-m;i--)

9. a*=i;

10. for(i=2;i<=m;i++)

11. b*=i;

12. return a/b;

13. }

14. unsigned __int64 bell(int n)

15. {

16. unsigned __int64 t=0;

17. int i;

18. if(n==0) return 1;

19. else

20. {

21. for(i=0;i<=n-1;i++)

22. t+=c(n-1,i)*bell(i);

23. }

24. return t;

25. }

26. int main()

27. {

28. int n;

29. while(scanf("%d",&n)!=EOF)

30. printf("%I64u

",bell(n));

31. return 0;

32. }