多重集的r-组合的个数

定义

如果S是一个多重集，S具有k种类型的元素为a1,a2,…ak，满足S = {∞×a1,∞×a2,…,∞×ak}，S的任一个r-组合的个数等于C（r+k-1，r）;

证明

S的任一个r-组合均呈{x1·a1,x2·a2,…,xk·ak}的形式，其中x1,x2,…,xk皆为非负整数，且x1+x2+…+xk = r;因此，S的r-组合的个数等于方程
　　　　　　　　　　　　　x1+ x2 + …+xk = r 　　　　　　　　　　　　（式１）
的解个数。
首先 得出r值为非负整数，故在式1的左边写出r个1，1 1 1 1 … 1 1 1 = r；　　
其次 x1，x2，…，xk 相加为r ，所以我们用k-1个0来划分上面的1，想象一下现在有r个人排成一排，用k-1个木棒来分开不同群的人，木棒的左边为一群人，木棒的右边为另外一群人。此时有k-1个木棒，于是分出k 群人，不同群的人即为 x1，x2,…，xk的值。
然后 似乎这就是 r个1 + k-1个0 的全排列；非也。例子：我们用的木棒是一样的，人也是一样的人，如下图所示。

最后，其实S的r-组合的个数可以归结成H = {r×1，k-1 × 0 }的多重集的排列数，要求H多重集的排列数具体参考如下，比较简单：

参考书目

1.组合数学- Richard A. Brualdi 著 机械工业出版社