集合划分问题 Bell数

问题:

n个元素的集合{1,2,.,n }可以划分为若干个非空子集。例如,当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}}
其中,集合{{1,2,3,4}} 由1个子集组成;集合{{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}} 由2个子集组成;集合{{1,2},{3},{4}},{{1,3},{2},{4}},{{1,4}.{2},{3}},{{2,3},{1},{4}},{{2,4},{1},{3}},{{3,4},{1},{2}} 由3 个子集组成;集合{{1},{2},{3},{4}} 由4个子集组成。
编程任务:
给定正整数n 和m,计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个
非空子集组成的集合。
数据输入:
由文件input.txt 提供输入数据。文件的第1 行是元素个数n 和非空子集数m。
结果输出:
程序运行结束时,将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt中。
输入文件示例输出文件示例
input.txt output.txt
5 52

解题思路:

设n个元素的集合可以划分为F(n,m)个不同的由m个非空子集组成的集合。

考虑3个元素的集合,可划分为
① 1个子集的集合:{{1,2,3}}
② 2个子集的集合:{{1,2},{3}},{{1,3},{2}},{{2,3},{1}}
③ 3个子集的集合:{{1},{2},{3}}
∴F(3,1)=1;F(3,2)=3;F(3,3)=1;

如果要求F(4,2)该怎么办呢?

A.往①里添一个元素{4},得到{{1,2,3},{4}}

B.往②里的任意一个子集添一个4,得到
{{1,2,4},{3}},{{1,2},{3,4}},
{{1,3,4},{2}},{{1,3},{2,4}},
{{2,3,4},{1}},{{2,3},{1,4}}

∴F(4,2)=F(3,1)+2*F(3,2)=1+2*3=7

推广,得F(n,m)=F(n-1,m-1)+m*F(n-1,m)

注:
解法来自网络。一本书上只是简单的说这是bell数,但是对组合论不是太了解。所以看到这个答案时觉得很清晰,就记录了下来

Bell数,又称为贝尔数。

是以埃里克・坦普尔・贝尔(Eric Temple Bell)为名的。

 

B(n)是包含n个元素的集合的划分方法的数目。

 

B(0) = 1, B(1) = 1, B(2) = 2, B(3) = 5,

B(4) = 15, B(5) = 52, B(6) = 203,…

 

递推公式为,

B(0) = 1,

B(n+1) = Sum(0,n) C(n,k)B(k). n = 1,2,…

 

其中,Sum(0,n)表示对k从0到n求和,C(n,k) = n!/[k!(n-k)!]

 

————————-

Stirling数,又称为斯特灵数。

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

 

第一类Stirling数是有正负的,其绝对值是包含n个元素的集合分作k个环排列的方法数目。

 

递推公式为,

S(n,0) = 0, S(1,1) = 1.

S(n+1,k) = S(n,k-1) + nS(n,k)。

 

第二类Stirling数是把包含n个元素的集合划分为正好k个非空子集的方法的数目。

 

递推公式为,

S(n,n) = S(n,1) = 1,

S(n,k) = S(n-1,k-1) + kS(n-1,k).

 

 

————-

bell数和stirling数的关系为,

 

每个贝尔数都是”第二类Stirling数”的和。

 

B(n) = Sum(1,n) S(n,k).

参考资料:http://planetmath.org/?op=getobj&from=objects&id=9059

 

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>