给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。
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) 证明有一点复杂，我想如果你要的是程序解决的方法那应该用不上了。
对於第一种情况，等价于把前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) 证明有一点复杂，我想如果你要的是程序解决的方法那应该用不上了。
追问
……
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
