n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.请给出具体思路

来源：学生作业帮助网 编辑：作业帮 时间：2024/11/06 03:56:28

n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.请给出具体思路
n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.
请给出具体思路

n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.请给出具体思路
第二类斯特林数,n个不同的元素划分成m个非空集合的方法数
S(n,m)=mS(n-1,m)+S(n-1,m-1)
S(n,1)=1
如果堆不同再乘以m!

在n个物体中，先选出m个物体，每一堆放一个，这样有A（m）（n）=n*(n-1)*....*(n-m+1)种情况，然后其余的物品随便放，有m^(n-m)种情况，两者相乘就是答案

这个问题等价于：从M个堆中可重复的选出n个做排列，每个堆至少被选一次
使用母函数解决
G(x)=n!*(x+x^2/2!+x^3/3!+... ...)^M
G(x)展开后x^n项的系数就是答案
如果M个堆是相同的就再除以M!
这是最高效的算法，如果还要快，G(x)展开的时候可以使用二分法。
关于母函数，请参见：http://baike.baidu....

全部展开

这个问题等价于：从M个堆中可重复的选出n个做排列，每个堆至少被选一次
使用母函数解决
G(x)=n!*(x+x^2/2!+x^3/3!+... ...)^M
G(x)展开后x^n项的系数就是答案
如果M个堆是相同的就再除以M!
这是最高效的算法，如果还要快，G(x)展开的时候可以使用二分法。
关于母函数，请参见：http://baike.baidu.com/view/2177279.html

收起

n*(n-1)*(n-2)*.........(m+1)*m/1*2*3*4*5*6*7*8*9.......*(m-1)*m

n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.请给出具体思路 12个乒乓球分成三堆,每堆至少一个,有几种不同的分法? 12个球分成三堆,每堆至少一个,共有几个不同的分法? 12个乒乓球分成三堆,每堆至少一个,共有几种不同的分法? 把10个苹果分成三堆,每堆至少1个则有几种不同的分法? 把10个苹果分成三堆,每堆至少一个,最多5个,则不同的分法共有多少? 把10个相同的乒乓球分成三堆,每堆至少一个,共有几种分法不要一个个列出来 的, 将50个苹果分成三堆,每堆至少一个,有多少种的分法 有8个苹果,要分成三堆,每堆至少一个.有几种分法?分别写出来! 5055个小球分成100堆,每堆至少一球,各堆的球数都不相等.有几种分法 把10个苹果分成三堆,要求每堆至少1个,至多5个,则不同的分法共有___________ 把10个苹果分成三堆,要求每堆至少1个,则不同的分法有几种?用计数原理做, m个球分成n堆(m >= n)有几种分法 把10个苹果分成三堆,每堆至少1个,应有( )种分法 把450个苹果平均分成若干堆（不能只一堆,也不能每堆一个苹果）.共有多少种不同的分法? 15个苹果分成不同的4堆,最多的一堆至少有( )个. 把60个橘子分成偶数堆,使得每堆的个数相等,有多少不同的分法? 把60个桃子分成偶数堆,使得每堆的个数相等,有多少种不同的分法