隔板法的三种题型公式

理解隔板法#

隔板法就是在n个元素间的n−1个空插入k−1个板子，把n个元素分成k组的方法。方案数为Ck−1n−1。

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

n个元素是相同的

k个组是互异的

每组至少分得一个元素

例如，把10个相同的球放入3个不同的箱子，每个箱子至少一个，有C29种情况。

隔板法应用#

普通隔板法#

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

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

增减元素隔板法#

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

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

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

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

也可转化为例2的形式，即求方程x+y+z=10(x≥1,y≥3,z≥0)的整数解的个数。构造新变量a=y−2,b=z+1，现在x,a,b都≥1了，因此可以运用隔板法。原方程化为x+a+b=10−2+1=9，隔板法求得方案数C2−19−1=C28=28。

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

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

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

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

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

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

这里可以构造第三个盒子c来放剩下的球，即a+b+c=9(a≥1,b≥0,c≥0)。老套路，转化为a+(b+1)+(c+1)=11，使得⎧⎩⎨a≥1(b+1)≥1(c+1)≥1

题目等价于，11个球放入3个不同的箱子，每个箱子至少放一个，C210。

选板法#

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

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

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

分类插板法#

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

分析：

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

吃1天或是5天，各一种吃法,一共2种情况

吃2天，每天预先吃2块，即问11块糖，每天至少吃1块，吃2天，几种情况？C110=10

吃3天，每天预先吃2块，即问9块糖，每天至少1块，吃3天？C28=28

吃4天，每天预先吃2块，即问7块糖，每天至少1块，吃4天？C36=20

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

*逐步插板法#

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

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

分析：可以用一个节目去插7个空位，再用第二个节目去插8个空位，用最后个节目去插9个空位，所以一共是C17C18C19=504种。

综合例题#

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

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