隔板法(排列组合)

                     

贡献者: 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 相关页面

                     

© 小时科技 保留一切权利