背景：
目前为止，我们关注的对象都是“组合”概念\(\require{AMSmath} \binom{n}{k}\)，即：从n个对象中，选择k个对象出来的总方案数。
问题：
在上述基础上，我们尝试着更深一步研究选择的方案数：如果n个对象中的任意一个对象均可被选择多次！
解构：
第一：k种不同的对象，则总方案数有\(\binom{n}{k}\)；
第二：k-1种不同的对象，剩余的一个对象从前述的k-1个对象中选择，则总方案数有\(\binom{n}{k-1}\binom{k-1}{1}\)；
依次类推，则选择\(k-\lambda\)种不同的对象，剩余的\(\lambda\)个对象从前述的\(k-\lambda\)个对象中选择，则总方案数有\(\binom{n}{k-\lambda}\left( \binom{k-\lambda}{\lambda} + \binom{k-\lambda}{\lambda-1}+\cdots + \binom{k-\lambda}{1} \)
综上所述，考虑可重复的情况时，从n个对象中选择k个出来的总方案数为：
$$
\begin{align}
\sum_{\lambda=0}^{k} \binom{n}{k-\lambda}\sum_{l=1}^{\lambda}\binom{k-\lambda}{l}
&= \sum_{\lambda=0}^{k} \binom{n}{k-\lambda}\binom{k-\lambda+1}{\lambda+1} \\
&= \sum_{\lambda=0}^{k} \binom{n}{\lambda} \binom{n-\lambda}{k-2\lambda}
\end{align}
$$
发表评论