有重复组合数公式的理解证明

定义：从n个不同的元素中有重复地取r个，不计顺序，则不同的取法有

$binom {n+r-1} r$

(rn+r−1​)种，这个数称为有重复组合数。

之前也讲过一个概念，有重复排列数：从n个不同的元素中有重复地取r个，计顺序，不同的取法数即为有重复排列数。
很容易理解，有重复排列数为
$n^r$

nr：排列时，每次抽取都有n种结果，共抽取r次，总数即为r个n相乘。

1.尝试

我们获取排列数的公式：

$排列数=sum_{i=1}^{组合数量}{组合i的排列种数}$

排列数=∑i=1组合数量​组合i的排列种数
但是，由于每种组合中重复的数字种数与个数可能众多，排列种数不同，难以通过除法快速处理，我只能寻求别的方法。

2.证明

假设n个元素分别为
$x_1,x_2dots x_n$

x1​,x2​…xn​，我们将第一次抽取的结果设为
$x_{n+1}$

xn+1​，第二次抽取的结果设为
$x_{n+2}$

xn+2​……第r-1次抽取的结果设为
$x_{n+r-1}$

xn+r−1​。

我们先不考虑
$x_{n+1}dots x_{n+r-1}$

xn+1​…xn+r−1​的值，此时我们可以知道第一次抽取的样本空间
$omega_1={x_1,x_2dots x_n}$

ω1​={x1​,x2​…xn​}，第二次抽样的样本空间
$omega_2={x_1dots x_n,x_{n+1}}$

ω2​={x1​…xn​,xn+1​}……第r次抽取的样本空间
$omega_r={x_1dots x_{n+r-1}}$

ωr​={x1​…xn+r−1​}
根据前面的有重复派列数的原理，我们这里每次抽取都有
$n+i-1$

n+i−1种可能，所以我们得到的排列数是
$frac{(n+r-1)!}{(n-1)!}$

(n−1)!(n+r−1)!​
因为
$x_{n+1}dots x_{n+r-1}$

xn+1​…xn+r−1​其实是抽到过的值，所以这时我们所得到的排列里，可能存在许多重复的数，形成相同的排列。
假设第
$i$

i次抽取时，我们在前面已经抽到了
$p$

p次
$x_a$

xa​的情况下，我们下一次抽到
$x_a$

xa​的概率是一次都没抽到的数的
$p+1$

p+1倍。因此很明显，若排列中各个数出现的次数是
$p_i$

pi​次
$(i=1,2……r)$

(i=1,2……r)，该排列在上述排列中的数量就是
$prod{p_i!}$

∏pi​!
根据组合的定理，组合中各个数出现的次数是
$p_i$

pi​次
$(i=1,2……r)$

(i=1,2……r)，则该组合就可以形成
$frac{r!}{prod{p_i!}}$

∏pi​!r!​种排列。
因此，根据上述关系：

$sum_{j=1}^{有重复组合数}{ prod{p_{j_i}!} frac{r!}{prod{p_{j_i}!} }}=frac{(n+r-1)!}{(n-1)!}$

∑j=1有重复组合数​∏pji​​!∏pji​​!r!​=(n−1)!(n+r−1)!​
(
$p_{j_i}$

pji​​表示某个组合中各个数的数量）
得：
$有重复组合数times r!=frac{(n+r-1)!}{(n-1)!}$

有重复组合数×r!=(n−1)!(n+r−1)!​

$有重复组合数=frac{(n+r-1)!}{r!(n-1)!}=binom {n+r-1} r$

有重复组合数=r!(n−1)!(n+r−1)!​=(rn+r−1​)