从n个元素中有重复地取r个,不计顺序,则不同的取法有多少种?
这个问题的答案被称为有重复组合数。结果很简洁,是C(n+r-1,r)。(注:这表示从n+r-1个数中取出r个数的组合数)
【证明1】
我们先把原命题具体化。假设这n个元素就是1~n这n个数:
对于每一种选出来的组合a1,a2,a3,... ,am,我们要求:a1<=a2<=a3<=...<=ar,那么最终的目的就是找出这样的a(i)组数。
这里我们构造b1=a1,b2= a2+1,... ,b(i)= a(i)+(i-1),... ,b(r)= a(r)+(r-1)
于是b(i)和a(i)一一对应,即所求a(i)组数对应于b(i)组数
又因为 b1 < b2 < b3 < ... < br 且b(i)取值于1~ n+(r-1)
亦即原命题等价于从1~ n+r-1中取得r个不重复排列数
来源:http://zhidao.baidu.com/question/16706714.html
【证明2】
将n个元素看做n个盒子,r看作r个无区别的球,则相当于:
把r个同样的球放入n个顺次排列的盒子,求不计放球顺序的放法种数
用0表示盒子,1表示球
我们把这n个0和r个1写在一行上。
由于球必须放在盒子中,规定某个0之前,到上一个0为止的1的个数,表示该盒子中装的球数
注意到最后一个数必须是0
所以相当于从前面n+r-1个位置中挑出r个位置放1,其余n-1个位置放0
来源:http://pengzhe0302.spaces.live.com/blog/cns!529d86ea9ec40ca2!113.entry