堆放排列组合

             

  • 本词条处于草稿阶段.

   比热力学课本上简单得多的方法推导出这种排列组合来.

   题目是这样的,

   如果有 $n$ 个不加区分的小球,有 $N$ 个有编号的盒子($N \geqslant n$),那么把所有小球都放到盒子里有几种方法(每个盒子能装的个数没有限制)?

   现在把所有的情况根据非空盒子的个数分类.非空盒子个数可能为 1 个($n$ 个小球都在里面),2 个,一直到 $n$ 个(每个盒子只装 1 个).如果用 $i$ 个盒子装小球,那么首先从 $N$ 个盒子里面选择 $i$ 个会有 $C_n^i$ 种情况.然后要考虑的是,如果用已选的 $i$ 个有编号盒子装 $n$ 个小球,又有几种情况.用所谓的插空法得到共有 $C_{n-1}^{i-1}$ 种情况.所以一个 $i$ 对应 $C_N^i C_{n-1}^{i-1}$ 种情况.

   最后把所有不同 $i$ 的情况数加在一起,得出所有情况的总数为

\begin{equation} \sum_{i = 1}^n C_N^i C_{n-1}^{i-1} \end{equation}
又由于 $C_a^b = a!/[(a-b)!b!] = C_a^{a-b}$,上式可变为
\begin{equation} \sum_{i=1}^n C_N^i C_{n-1}^{n-i} \end{equation}
又由于 $\sum_i C_a^i C_b^{n-i} = C_{a+b}^n$($i$ 取所有可能的整数使得 $i \leqslant a$, $n - i \leqslant b$ )(见),上式变为
\begin{equation} \sum_{i=1}^n C_N^i C_{n-1}^{n-i} = C_{N+n-1}^n = \frac{(N+n-1)!}{n!(N - 1)!} \end{equation}
这就是最后的答案.

致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择会员制,大量广告,内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证网站能在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

         

© 小时科技 保留一切权利