15问答网 > 给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。

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

求编程高手帮忙解答，用JAVA编程……

2025-06-22 06:03:14

推荐回答（1个）

回答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) 证明有一点复杂，我想如果你要的是程序解决的方法那应该用不上了。