隔板法(排列组合)

                     

贡献者: addis; 切糕糕

预备知识 组合

  

未完成:如果确定不是高中内容,应该移动到组合数学:计数

  1在排列组合问题中,隔板法(stars and bars)常用解决以下问题:

例 1 

   把 $n$($n = 1,2,\dots$)个不加区分的小球放进 $m$($1\leqslant m\leqslant n$)个有编号的盒子,每个盒子至少有一个小球,有多少种不同的方法?

图
图 1:题目示意图

   我们可以想象这些小球排成一列后被 $m-1$ 个隔板隔开,每一组被隔开的小球就相当于装进一个盒子中.小球之间一共有 $n-1$ 个空隙可以插入隔板,一个空隙最多插一个隔板,所以不同的情况数就是组合 $C_{n-1}^{m-1}$.

图
图 2:隔板法示意图

1. 盒子可以为空

预备知识 范德蒙恒等式

  

未完成:应当是高中内容,不需要引入范德蒙恒等式才对

例 2 

   把 $n$($n=1,2\dots$)个不加区分的小球放进 $m$($m=1,2\dots$)个有编号的盒子,盒子可为空,有多少种不同的方法?

   把所有的情况根据非空盒子的个数分类.非空盒子个数可能为 $i=1$ 个($n$ 个小球都在里面),$i=2$ 个,一直到 $i=\min \left\{m,n \right\} $ 个(若 $n\leqslant m$ 则每个小球都在不同的盒子).首先从 $m$ 个盒子里面选择 $i$ 个非空盒子会有 $C_m^i$ 种情况.再考虑这 $i$ 个有编号盒子装 $n$ 个小球(不为空)又有几种情况:用隔板法得到共有 $C_{n-1}^{i-1}$ 种.所以一个 $i$ 对应 $C_m^i C_{n-1}^{i-1}$ 种情况.最后把所有不同 $i$ 的情况数加在一起,得出所有情况的总数为

\begin{equation} \sum_{i = 1}^{\min \left\{m,n \right\} } C_m^i C_{n-1}^{i-1} = \sum_{i=1}^{\min \left\{m,n \right\} } C_m^i C_{n-1}^{n-i} \end{equation}
这里使用了 $C_a^b = C_a^{a-b}$(式 6 ).又由范德蒙恒等式,有
\begin{equation} \sum_{i=1}^{\min \left\{m,n \right\} } C_m^i C_{n-1}^{n-i} = C_{m+n-1}^n = \frac{(m+n-1)!}{n!(m - 1)!} \end{equation}
这就是最后的答案.


1. ^ 参考 Wikipedia 相关页面


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

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利