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

来源:学生作业帮助网 编辑:作业帮 时间:2024/03/29 05:53:57
n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.请给出具体思路

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