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

Question

如题所述

Answer 1

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)

Answer 2

含有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)追问

有没有简单点的方法？