贡献者: addis; int256
1在排列组合问题中,隔板法(stars and bars)常用来解决以下问题:
我们可以想象这些小球排成一列后被 $m-1$ 个隔板隔开,每一组被隔开的小球就相当于装进一个盒子中。小球之间一共有 $n-1$ 个空隙可以插入隔板,一个空隙最多插一个隔板,所以不同的情况数就是组合 $C_{n-1}^{m-1}$。
综上,可以发现隔板法的应用有以下 $3$ 个要求:
对于盒子可以空的方法,为了满足条件 $1$,我们可以先增加 $m$ 个球(这 $m$ 个球将分给各个盒子,使得满足条件 $1$),而对于每种分法的实际情况对应于减去这 $m$ 个虚拟球。
即:若在现在这 $n+m$ 个球、$m$ 个盒子的前提下任一盒子分得了 $k$ 个球,则在原题条件下应分得 $k-1$ 个球。这样现在的问题情形是求 $n+m$ 个球、$m$ 个盒子的标准隔板法。故答案就为 $C_{n+m-1}^{m-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$。
前两种情况也可以混合,例如下面这道例题。
我们先创建两个 “虚拟球”,这两个虚拟球分别在 $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$。