Question

给定正整数n和m，计算出n个元素的集合可以划分为多少个不同的由m个不同的非空子集组成的集合

给定正整数n和m，计算出n个元素的集合可以划分为多少个不同的由m个不同的非空子集组成的集合
用c++ 那个会

Answer 1

思路是这样的：把n个元素编号，对於最后那个n号元素，有两种情况。一种是独立组成一个集合，另一种是和别的元素混在一起。
对於第一种情况，等价于把前n-1个元素分成m-1份，然后n号元素单独放。
对於第二种情况，等价于把前n-1个元素分成m份，然后把n号元素放入这m个集合中的一个（也就是说有m种放法）
那麽总数就是
F(n,m) = F(n-1,m-1) + m * F(n-1,m)
接下来就可以用计算机程序的递归来解决了。

实际数学上这个叫做“第二类Stirling数”，有一个直接计算的公式，F(n,m) = 1/m! *sum((-1)^k * C(m,k)*(m−k)^n,k=1...m) 证明有一点复杂，我想如果你要的是程序解决的方法那应该用不上了。