背景：
目前为止，我们关注的对象都是“组合”概念\(\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-2种不同的对象，剩余的2个对象从前述的k-2个对象中选择，则总方案数有\(\binom{n}{k-2}\left( \binom{2}{2} + \binom{1}{2} \right)\)；
依次类推，则选择\(k-\lambda\)种不同的对象，剩余的\(\lambda\)个对象从前述的\(k-\lambda\)个对象中选择，则总方案数有\(\binom{n}{k-\lambda}\left( \binom{1}{\lambda} + \binom{2}{\lambda}+\cdots + \binom{k-\lambda}{\lambda} \right) \)
综上所述，考虑可重复的情况时，从n个对象中选择k个出来的总方案数为：
$$
\begin{align}
\sum_{\lambda=0}^{k} \binom{n}{k-\lambda}\sum_{l=1}^{k-\lambda}\binom{l}{\lambda}
&= \sum_{\lambda=0}^{k} \binom{n}{k-\lambda}\sum_{l=1}^{k}\binom{l}{\lambda},\quad \dagger \text{凑齐余项} \\
&= \sum_{\lambda=0}^{k} \binom{n}{k-\lambda}\binom{k+1}{\lambda+1} \\
&= \binom{n+k+1}{k+1}
\end{align}
$$
至此，我们解构出带重复条件下排列的总方案数！
发表评论