隔板法 学习笔记
前言
2019.10.19就CSP第一轮了（好慌
隔板法定义
在组合数学中，隔板法（又叫插板法）是排列组合的推广，主要用于解决不相邻组合与追加排列的问题。 隔板法就是在n个元素间插入(b-1)个板，即把n个元素分成b组的方法。——百度百科
普通隔板法
经典问题：求x y z=10的正整数解的个数。
这个问题与此问题相同：如图，有10个小球，现要插入2块板，问总共有多少种方法？
就比如这种情况：当x=2,y=5,z=3时，等式成立，同时转换成的隔板问题的情况是这样的：
很显然，10个小球之间有10-1=9个空隙，插2块板，不难得出答案就是C_{2}^{9}=36种方法。 （不会组合数？那就戳这里）
添元素隔板法
例$1$：求$x y z=10$的非负整数解的个数。
我：这题和上题不是一模一样吗（小声bb 大佬：对对对，这题和上题一样水 （言归正传 本题注意是非负整数解，所以x,y,z可以有0（废话） 所以我们可以在等式两边同时加上3 然后等式就变成了x y z 3=10 3 整理一下：(x 1) (y 1) (z 1)=13 然后设A=x 1,B=y 1,C=z 1，代回原式：A B C=13 这格式好像和上题一模一样… 因为x,y,z为非负整数，那么显而易见A,B,C均为正整数，所以A,B,C的方案数可以通过上一题的方法快速地求出，即：C_{2}^{12}=66。 因为每一组得出的A,B,C对应着唯一一组x,y,z，所以x,y,z的方案数也是66。
例2：有一类自然数，从第三位开始每一位上的数字都是前两位数字之和，直至不能写为止，问这类自然数有多少个。
首先，我们假设这类自然数的前两位数为a,b，显然，确定了前两位数，这个数字就确定了（因为每个数都要到不能写为止）。 根据题意，这个数必须有第三位，所以a bleq 9，并且a是最高位anot=0。 我：那我还是照着之前的思路，放9个球，插1个板，如下图，答案就是C_{1}^{8}=8。
大佬：不对啊，anot=0，但是b可以为0啊，所以等式两边同时 1，所以a (b 1)leq 10，所以放10个球，插1个板，如下图，答案就是C_{1}^{9}=9。
我：原来是这样啊。 （这时，奆佬走了过来把纸撕了） 奆佬：不不不，你们都错了。
奆佬：a b不一定等于9，所以我们应该再设一个变量c，使得a b c=9(cge 0)，然后等式两边同时加2，所以a (b 1) (c 1)=11，所以放11个球，插2个板，如下图，答案就是C_{2}^{10}=45。
添板插板法
例题：有一类自然数，从第三位开始每一位上的数字都是前两位数字之和，直至不能写为止，问这类自然数有多少个。（同上题）
奆佬：上题还可以用添板插板法做 我：（大吃一惊） 我们还是设前两位为a,b，那么a bleq 9,anot=0。
我们可以在前9个空位中插2个隔板，分成3组，当b=0时，则在第10个空位上插隔板。 那么答案就是总共在10个空位插2个隔板，C_{2}^{10}=45。
选板法
例题：有10颗糖，每天至少吃一颗，吃完为止，问有多少种吃法。
(我吃糖你还管我
如上图，有9个空位，可以插入9个板，每个板可以放或不放，所以总共有2^9=512种吃法。 我：哇，有这么多种吃法，我每10天试一种，那我要吃多少天呢…
分类插板
例题：有15颗糖，每天至少吃三颗，吃完为止，问有多少种吃法。
(这题好像和上一题又是一模一样 因为题目中并没有规定要吃几天，也没有规定每天一定要吃几颗，所以需要分类讨论。 当吃1天时，答案就是1种（一天吃15颗糖） 当吃2天时，每天先吃2块，即有11颗糖，每天至少吃1颗，吃2天，有C_{1}^{10}=10种情况。 当吃3天时，每天先吃2块，即有9颗糖，每天至少吃1颗，吃3天，有C_{2}^{8}=28种情况。 当吃4天时，每天先吃2块，即有7颗糖，每天至少吃1颗，吃4天，有C_{3}^{6}=20种情况。 当吃5天时，答案就是1种（每天吃3颗糖） 所以最终的答案就是1 10 28 20 1=60种吃法。
逐步插板
例题：在一张节目单中原有6个节目，若保持这些节目相对次序不变，再添加3个节目，共有几种情况？
可以用一个节目去插7个空位，再用第二个节目去插8个空位，用最后个节目去插9个空位。 所以一共是C_{1}^{7}times C_{1}^{8}times C_{1}^{9}=504种。
总结
隔板法应用的条件
分成的组别要不同
分的每组至少有$1$个元素
$n$个元素不同
隔板法就是在$n$个元素间$(n-1)$个空中插入$k$个板，可以把$n$个元素分成$k 1$组的方法
完结撒花❀O(∩_∩)O❀
