n个球放a个不同篮子，排列组合的算法
假如有n个相同的球，要放入a个不同的篮子中，球必须全部放完，请问怎么求有几种放的方式（球不记先后顺序）
希望能程序在3秒钟内算出1000个球,1000个篮子的结果
问题点数：100、回复次数：16Top
1 楼char1984（）回复于 2005-11-03 19:29:48 得分 0
顶一下Top
2 楼boylez（boylez）回复于 2005-11-03 20:19:49 得分 0
篮子可空的话是a^n;
Top
3 楼boylez（boylez）回复于 2005-11-03 20:24:14 得分 0
如果不可空的话是a^(n-a) n>=a
n<a为0Top
4 楼char1984（）回复于 2005-11-04 09:12:48 得分 0
boylez(boylez) ，好像还是有点问题
比如3个球3个篮，放案有如下10种：
003 030 300 120 210 102 201 012 021 111
a^(n-a)的话就是3种Top
5 楼char1984（）回复于 2005-11-04 13:06:24 得分 0
顶一下Top
6 楼char1984（）回复于 2005-11-04 13:06:44 得分 0
顶一下Top
7 楼boylez（boylez）回复于 2005-11-04 13:18:48 得分 0
楼上，你所说得是不可空的情况？那么只有111一种啊Top
8 楼boylez（boylez）回复于 2005-11-04 13:49:26 得分 0
可空的话好像要写成一个求和式，我现在不知道怎么更简单的表达。老了……Top
9 楼boylez（boylez）回复于 2005-11-04 14:06:38 得分 0
如果n>=a:
a
西格马{C（a,i）*i^(n-i)}
i=1
如果n<a:
n
西格马{C(a,i)*i^(n-i)}
i=1
注：C是求组合C(a,i)，a在下i在上Top
10 楼char1984（）回复于 2005-11-04 16:51:53 得分 0
楼上的好像还是不对
比如4个球4个篮子
如果球分成4个1份，方案数为： 4
如果球分成1,3,方案数为：p(4,2)= 12
如果球分成2,2： c(4,2)= 6
如果球分成1,1,2： 4*c(3,2)= 12
如果球分成1,1,1,1： 1
总共是35种
而用西格玛算出来是4+6*4+4*3+1=41Top
11 楼char1984（）回复于 2005-11-04 17:04:18 得分 0
我现在只是用很原始的递归的办法求的,要花时间O(n^a)Top
12 楼boylez（boylez）回复于 2005-11-04 23:28:16 得分 0
好像是不对。。老了，多么简单的排列组合啊。。居然，，，唉Top
13 楼char1984（）回复于 2005-11-05 06:47:28 得分 0
顶Top
14 楼char1984（）回复于 2005-11-05 19:35:10 得分 0
继续顶，期待编程的实现Top
15 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2005-11-05 21:22:20 得分 100
这相当于如下问题：求不定方程 x1+x2+...+x(a)=n的非负整数解的个数？
答案：C(n, n+a-1) = (n+a-1)!/[n!*(a-1)!]
感兴趣者不妨自己验证一下。证明略。Top
16 楼char1984（）回复于 2005-11-06 08:30:47 得分 0
谢谢楼上，一语点破Top
