隔板法题型整理

参考博文：「隔板法」详解

理解隔板法

隔板法就是在 $n$ 个元素间的 $n-1$ 个空插入 $k-1$ 个板子，把 $n$ 个元素分成 $k$ 组的方法。方案数为 ${\mathrm{C}}_{n-1}^{k-1}$。

应用隔板法必须满足的 3 个条件：

1. $n$ 个元素是相同的
2. $k$ 个组是互异的
3. 每组至少分得一个元素

例如，把 10 个相同的球放入 3 个不同的箱子，每个箱子至少一个，有 ${\mathrm{C}}_9^2$ 种情况。

隔板法应用

普通隔板法

例 1. 求方程 $x+y+z=10$ 的正整数解的个数。

分析：将 $10$ 个求排成一排，球与球之间形成 $9$ 个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为 $x$、$y$、$z$ 的值，则隔板法与解的个数之间建立了一一对应关系，故解的个数为 ${\mathrm{C}}_{n-1}^{m-1}={\mathrm{C}}_9^2=36$。

增减元素隔板法

例 2. 求方程 $x+y+z=10$ 的非负整数解的个数。

分析：注意到 $x$、$y$、$z$ 可以为零，故例 1 解法中的限定「每空至多插一块隔板」就不成立了，怎么办呢？只要预先给 $x$、$y$、$z$ 各添加一个球，这样原问题就转化为求 $(x+1)+(y+1)+(z+1)=13$ 的解的个数了，则问题就等价于把 $13$ 个相同小球放入 $3$ 个不同箱子，每个箱子至少一个，方案数为 ${\mathrm{C}}_{n+m-1}^{m-1}={\mathrm{C}}_{12}^2=66$。

例 3. 把 $10$ 个相同的小球放到 $3$ 个不同的箱子，第一个箱子至少 $1$ 个，第二个箱子至少 $3$ 个，第 $3$ 个箱子可以为空，有几种情况？

我们可以在第二个箱子先放入 $10$ 个小球中的 $2$ 个，小球剩 $8$ 个放 $3$ 个箱子，然后在第三个箱子放入 $8$ 个小球之外的 $1$ 个小球（即补充了一个球），则问题转化为把 $9$ 个相同小球放 $3$ 不同箱子，每箱至少 $1$ 个，几种方法？${\mathrm{C}}_8^2=28$。

也可转化为例 2 的形式，即求方程 $x+y+z=10(x\ge 1,y\ge 3,z\ge 0)$ 的整数解的个数。构造新变量 $a=y-2,b=z+1$，现在 $x,a,b$ 都 $\ge 1$ 了，因此可以运用隔板法。原方程化为 $x+a+b=10-2+1=9$，隔板法求得方案数 ${\mathrm{C}}_{9-1}^{2-1}={\mathrm{C}}_8^2=28$。

例 4. 将 20 个相同的小球放入编号分别为 1，2，3，4 的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数。

分析：先在编号 $1,2,3,4$ 的四个盒子内分别放 $0,1,2,3$ 个球，剩下 $14$ 个球，再把剩下的球分成 $4$ 组，每组至少 $1$ 个，由例 $1$ 知方法有 ${\mathrm{C}}_{13}^3=286$（种）。

添板插板法（添加盒子法）

例 5. 有一类自然数，从左往右的第三个数字开始，每个数字都恰好是它左边两个数字之和，直至不能再写为止，如 1459，58，21369 等。这类数共有几个？

分析：因为前 2 位唯一确定了整个序列，只要求出前两位的所有情况即可，设前两位为 $a$ 和 $b$

显然 $a+b\le 9$，且 $a$ 不为 $0$，但 $b$ 可以为 0（例如 202246）。这里恼人的地方在于这个不等号，$a+b$ 的总数是不确定的。怎么办？

这里可以构造第三个盒子 $c$ 来放剩下的球，即 $a+b+c=9(a\ge 1,b\ge 0,c\ge 0)$。老套路，转化为 $a+(b+1)+(c+1)=11$，使得$\{\begin{array}{l}a\ge 1\\ (b+1)\ge 1\\ (c+1)\ge 1\end{array}$

题目等价于，11 个球放入 3 个不同的箱子，每个箱子至少放一个，${\mathrm{C}}_{10}^2$。

选板法

例 6. 有 10 粒糖，如果每天至少吃一粒（多不限），吃完为止，求有多少种不同吃法？

分析：o_o_o_o_o_o_o_o_o_o（o 代表 10 个糖，_ 代表 9 个空）

所以 10 块糖，9 个空，插入 9 块隔板，每个板都可以选择放或不放，相邻两板间的糖一天吃掉，这样共有 $2^9=512$ 啦。

分类插板法

例 7. 小梅有 15 块糖，如果每天至少吃 3 块，吃完为止，那么共有多少种不同的吃法？

分析：

此问题不能用插板法的原因在于没有规定一定要吃几天，因此我们需要对吃的天数进行分类讨论。显然最多吃 5 天，最少吃 1 天。

1. 吃 1 天或是 5 天，各一种吃法,一共 $2$ 种情况
2. 吃 2 天，每天预先吃 2 块，即问 11 块糖，每天至少吃 1 块，吃 2 天，几种情况？ ${\mathrm{C}}_{10}^1=10$
3. 吃 3 天，每天预先吃 2 块，即问 9 块糖，每天至少 1 块，吃 3 天？${\mathrm{C}}_8^2=28$
4. 吃 4 天，每天预先吃 2 块，即问 7 块糖，每天至少 1 块，吃 4 天？${\mathrm{C}}_6^3=20$

所以一共是 $2+10+28+20=60$ 种。

^*逐步插板法

实际上是逐步插空法，属于插空而不是插板法。

例 8. 在一张节目单中原有 6 个节目，若保持这些节目相对次序不变，再添加 3 个节目，共有几种情况？

分析：可以用一个节目去插 7 个空位，再用第二个节目去插 8 个空位，用最后个节目去插 9 个空位，所以一共是 ${\mathrm{C}}_7^1{\mathrm{C}}_8^1{\mathrm{C}}_9^1=504$ 种。

综合例题

有 $n$ 个不同的盒子，在每个盒子中放一些球（可以不放），使得总球数不大于 $m$，求方案数。

分析：总球数 $\le m$，所以我们可以增加一个盒子放 $m$ 个球中没被选中的球。所以题目等价于 $m$ 个球放入 $n+1$ 个盒子中，盒子有里球数可以为 $0$，添元素插板法，每一个盒子都增加一个球，即 $m+n+1$ 个球放入 $n+1$ 个盒子，${\mathrm{C}}_{m+n}^n$ 为答案。