首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

组合数学,该怎么处理

2012-03-18 
组合数学有N个互不相同的球,M个直径与球直径相同的槽,要把这个N个球,放到M个槽中有多少种方法?注意,所放的

组合数学
有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)!

热点排行