重复组合

重复组合问题就是在n个元素中，有放回地抽取r次，问能够抽出的组合数是多少？

可以看成这样子：

用“o”代表抽出的元素，用“|”代表隔板（用来分隔区间）

我们一共有n个区间，区间x_i的元素个数表示第i个元素被抽出的次数。由于区间的元素个数可以为0，因此我们需要n+1个隔板来区分这些区间。

比如当r=10, n=8时，一种情况可以是这样子：

|o|o|o|o|o|oo|o|oo|||

表示抽到1次1，1次2，1次3，1次4，1次5，2次6，1次7,2次8，0次9，0次10

那么我们注意到，两边的隔板是不能动的，因此只有n-1个隔板可以分配。并且隔板可以相邻，因此就是转化为在n+r-1个位置内，分配n-1个隔板的问题。

因此重复组合数为C^n-1_n+r-1 .