隔板法 学习笔记

前言

$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+b\leq 9$,并且$a$是最高位$a\not=0$。
我:那我还是照着之前的思路,放$9$个球,插$1$个板,如下图,答案就是$C_{1}^{8}=8$。

大佬:不对啊,$a\not=0$,但是$b$可以为$0$啊,所以等式两边同时$+1$,所以$a+(b+1)\leq 10$,所以放$10$个球,插$1$个板,如下图,答案就是$C_{1}^{9}=9$。

我:原来是这样啊。
(这时,奆佬走了过来把纸撕了)
奆佬:不不不,你们都错了。

奆佬:$a+b$不一定等于$9$,所以我们应该再设一个变量$c$,使得$a+b+c=9(c\ge 0)$,然后等式两边同时加$2$,所以$a+(b+1)+(c+1)=11$,所以放$11$个球,插$2$个板,如下图,答案就是$C_{2}^{10}=45$。

添板插板法

例题:有一类自然数,从第三位开始每一位上的数字都是前两位数字之和,直至不能写为止,问这类自然数有多少个。(同上题)

奆佬:上题还可以用添板插板法做
我:(大吃一惊)
我们还是设前两位为$a,b$,那么$a+b\leq 9,a\not=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❀

暂无评论

发送评论


				
上一篇
下一篇