隔板法（排列组合）

贡献者： addis; int256

　　¹在排列组合问题中，隔板法（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}$。

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

1. 要求每个盒子至少分得 $a$ 个物品，$a$ 必须等于 $1$；
2. 物品之间无差异；
3. 盒子之间有差异（盒子有顺序）。

1. 盒子可以为空

　　 对于盒子可以空的方法，为了满足条件 $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. 要求混合

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

　　 我们先创建两个 “虚拟球”，这两个虚拟球分别在 $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 相关页面。