解一个编程题.（子集划分）将n个数（1,2,…,n）划分成r个子集.每个数都恰好属于一个子集,任何两个不同的子集没有共同的数,也没有空集.将不同划分方法的总数记为S(n,r).例如,S(4,2)=7,这7种不

Question

解一个编程题.
（子集划分）将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)=______________.
（提示：先固定一个数,对于其余的5个数考虑S(5,3)与S(5,2),再分这两种情况对原固定的数进行分析.）

Answer 1

求S(m,n)
若第一个元素作为单独的子集：S(m-1,n-1)
否则：n*S(m-1,n)
所以S(m,n) = S(m-1,n-1) + n*S(m-1,n)