隔板法(排列组合)

                     

贡献者: addis; int256

预备知识 组合

  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:隔板法示意图

   综上,可以发现隔板法的应用有以下 $3$ 个要求:

  1. 要求每个盒子至少分得 $a$ 个物品,$a$ 必须等于 $1$;
  2. 物品之间无差异;
  3. 盒子之间有差异(盒子有顺序)。

1. 盒子可以为空

例 2 

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

   对于盒子可以空的方法,为了满足条件 $1$,我们可以先增加 $m$ 个球(这 $m$ 个球将分给各个盒子,使得满足条件 $1$),而对于每种分法的实际情况对应于减去这 $m$ 个虚拟球。

   即:若在现在这 $n+m$ 个球、$m$ 个盒子的前提下任一盒子分得了 $k$ 个球,则在原题条件下应分得 $k-1$ 个球。这样现在的问题情形是求 $n+m$ 个球、$m$ 个盒子的标准隔板法。故答案就为 $C_{n+m-1}^{m-1}$。

2. 要求各个盒子至少分得 $k > 1$ 个球

   模仿刚才要求盒子可以为空的方法,我们先从总共的 $n$ 个球中拿出 $(k-1)m$ 个(注意这里是 $k-1$,不是 $k$。因为标准的隔板法要求每组还至少分得一个),先钦定给各个盒子分别 $k-1$ 个。这样剩余的 $n-(k-1)m$ 个球、$m$ 个盒子的标准隔板法。故这样的问题的方法数是 $C_{n-(k-1)m-1}^{m-1}$。注意要求存在一个方法,即 $n-(k-1)m-1 \le m-1$。

3. 要求混合

   前两种情况也可以混合,例如下面这道例题。

例 3 

   把 $11$ 个球分给 $4$ 个盒子。各个盒子要求如下:

  1. $1$ 号盒子无要求,可以没有球也可以有球;
  2. $2$ 号盒子要求至少分到 $3$ 个球;
  3. $3$ 号盒子要求至少分得 $1$ 个球;
  4. $4$ 号盒子无要求(同 $1$ 号盒子)。

   求不同的方法数。

   我们先创建两个 “虚拟球”,这两个虚拟球分别在 $1$ 号和 $4$ 号盒子中,使得他们变为标准的隔板法情形。这里使得 $11$ 个球变为 $11+2 = 13$ 个球。

   接下来考虑 $2$ 号盒子,需要 $3$ 个球,故先拿走 $3-1=2$ 个球固定分配给 $2$ 号盒子。这使得 $2$ 号盒子也变为标准的隔板法的情形。而 $3$ 号盒子就是标准的隔板法,无需对其进行任何处理。故实际是要对一个 $13-2=11$ 个球、$4$ 个盒子的情形进行标准隔板法(巧妙地,可以直接带入原题数据进标准隔板法的 “$C_{n-1}^{m-1}$” 而得到正确结果)。故答案就是 $C_{11-1}^{4-1} = C_{10}^3$。


1. ^ 参考 Wikipedia 相关页面


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

                     

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