n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.请给出具体思路
来源:学生作业学帮网 编辑:学帮网 时间:2024/05/13 08:59:41
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个桃子分成偶数堆,使得每堆的个数相等,有多少种不同的分法