麻烦问下,这个组合数公式是怎么推导出来的多谢k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m)

Question

麻烦问下, 这个组合数公式是怎么推导出来的 多谢
k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m)

Answer 1

这就是可重复组合数的公式
可以如此转化成普通组合模型
准备k个挡板,编号为1到k,对任意取出m个元素如此排列
1号挡板后面跟着所有取出的1类元素,在接着2号挡板后面跟着所有取出的2类元素,
以此类推k号挡板后面跟着所有取出的k类元素可知
这样一共是k+m个物体的一种排列,对这样的排列,可以知道除1号挡板固定在最前面,其他挡板可以在后面任何位置.仅需从首位以外的m+k-1个位置中挑出k-1位置就可确定一种排列.
所以方案是C(m+k-1,k-1)=C(m+k-1,m)