组合数学
有N个互不相同的球,M个直径与球直径相同的槽,要把这个N个球,放到M个槽中有多少种方法?注意,所放的球有次序之分。例如:2个球,1个槽有2种方法。,2个球,2个槽有6种方法。...在一个OJ系统上看到这题?
[解决办法]
应该是组合数学中的分装问题吧。。今天看组合数学看到的。。可以看成是球放入盒子里的问题来解决。(书上说的。)本人对此还不怎么理解。
可以分为四种情况来讨论。
是否可区分球 是否可区分盒子 盒子是否可空 把n个球放入k个盒子的方法数
情况1: 是 是 是 k^n
是 是 否 k!S(n,k)
情况2: 否 是 是 C(k+n-1, n)(组合公式)
否 是 否 C(n-1,k-1)
情况3: 是 否 是 S(n,1)+S(n,2)+`````+S(n,k)
是 否 否 S(n,k)
第四种情况有点复杂就不写出来了。。。自己看下嘛
[解决办法]
不好意思,这个整形划分是有顺序差别的,这使得问题变得更简单,直接用隔板法就可以求,
把10划分为3个可以为0的数,划分个数相当于2个无差别的版和10个无差别的数的全排列,
共(10+2)!/10!/2!,带入本题,就是(m+n-1)!/n!/(m-1)!,再加上球的差别就是(m+n-1)!/n!/(m-1)! * n!
=(m+n-1)!/(m-1)!