noip第13届普及组初赛试题的一题不会,（子集划分）将n个数（1,2,…,n）划分成r个子集.每个数都恰好属于一个子集,任何两个不同的子集没有共同的数,也没有空集.将不同划分方法的总数记为S(n

Question

noip第13届普及组初赛试题的一题不会,
（子集划分）将n个数（1,2,…,n）划分成r个子集.每个数都恰好属于一个子集,任何两个不同的子集没有共同的数,也没有空集.将不同划分方法的总数记为S(n,r).例如,S(4,2)=7,这7种不同的划分方法依次为{(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)},{(12),(34)},{(13),(24)},{(14),(23)}.当n=6,r=3时,S(6,3)=___90___________.
（提示：先固定一个数,对于其余的5个数考虑S(5,3)与S(5,2),再分这两种情况对原固定的数进行分析.）
请写出解析,不要只给答案,

Answer 1

设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)