n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.请给出具体思路
问题描述：
n个不同的物品,分成M堆,每堆至少一个.问有多少种分法,求高效率的算法.
请给出具体思路
答
n*(n-1)*(n-2)*.........(m+1)*m/1*2*3*4*5*6*7*8*9.......*(m-1)*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.com/view/2177279.html
答
第二类斯特林数,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)种情况，两者相乘就是答案