LS說得有理
含有n個元素的集合的劃分數(shù)記為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個元素的組合數(shù)
利用遞推公式可計陸續(xù)計算出:
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)