怎么求元素为n个的集合上的划分的个数,例如n=4时

题目

怎么求元素为n个的集合上的划分的个数,例如n=4时

答案

LS说得有理
含有n个元素的集合的划分数记为Bn,
显然B1=1,B2=2,
对一般的n有递推公式
Bn+1=C(n,0)B0+C(n,1)B1+.+C(n,n)Bn,
C(n,k)是n元素取k个元素的组合数
利用递推公式可计陆续计算出:
B3=C(2,0)B0+C(2,1)B1+C(2,2)B2=1+2+2=5
B4=C(3,0)B0+C(3,1)B1+C(3,2)B2+C(3,3)B3=1+3*1+3*2+5=15,
.如A={1,2,3,4},即n=4,有15种划分,如下:
仅含1块的划分有1种(1234)
含2块的划分有7种
(1,234) (2,134) (3,124) (4,123) (12,34) (13,24) (14 ,23)
含3块的划分有6种(1,2,34) (1,3,24) (1,4,23) (2,3,14) (2,4,13) (3,4,12)
含4块的划分有1种(1,2,3,4)