作业帮集合划分的个数把一个集合拆成一个或几个无交集的非空子集（即这些子集两两无交集,它们的并是全集）,叫做这个集合的一种划分.问：含有n个元素的集合有几种划分?
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/09 16:03:28
集合划分的个数把一个集合拆成一个或几个无交集的非空子集（即这些子集两两无交集,它们的并是全集）,叫做这个集合的一种划分.问：含有n个元素的集合有几种划分?
集合划分的个数
把一个集合拆成一个或几个无交集的非空子集（即这些子集两两无交集,它们的并是全集）,叫做这个集合的一种划分.
问：含有n个元素的集合有几种划分?
集合划分的个数把一个集合拆成一个或几个无交集的非空子集（即这些子集两两无交集,它们的并是全集）,叫做这个集合的一种划分.问：含有n个元素的集合有几种划分?
n=1 1个
n=2 2个
n=3 5个
n=4 1 1 4 6 12个
2^(n-1)
2的n-1次方
不信可以验证！
含有n个元素的集合的划分数记为Bn,显然B1=1,B2=2,对一般的n有递推公式
Bn+1=C(n,0)B0+C(n,1)B1+....+C(n,n)Bn,
其中规定B0=1,C(n,k)是n元素取k个元素的组合数,C(n,k)=n!/(k!(n-k)!),k=0,1,...,n,利用递推公式可计陆续计算出:
B3=C(2,0)B0+C(2,1)B1+C(2,2)B2...
全部展开
含有n个元素的集合的划分数记为Bn,显然B1=1,B2=2,对一般的n有递推公式
Bn+1=C(n,0)B0+C(n,1)B1+....+C(n,n)Bn,
其中规定B0=1,C(n,k)是n元素取k个元素的组合数,C(n,k)=n!/(k!(n-k)!),k=0,1,...,n,利用递推公式可计陆续计算出:
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,
Bn是著名的Bell数.如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)
收起
非空子集，2的n次方减一