隔板法 学习笔记
隔板法 学习笔记
前言
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❀
相关文章
- Spring学习笔记(一)——Spring介绍及工厂模式解耦
- SEM学习笔记——竞价账户流程梳理
- Spring学习笔记(三十七)——Flyway 数据库版本控制
- LeetCode笔记:Weekly Contest 306
- java学习笔记 head first java
- 学习笔记 | 非负矩阵分解(NMF)浅析
- Maven笔记
- ES6 学习笔记(五)基本类型Boolean
- nginx学习笔记
- 关于K8S中部署Ansible AWX(awx-operator 0.30.0)的一些笔记(Helm方式)
- Pytest学习笔记5——Allure测试报告用例详细描述
- Java的学习笔记(06)对象 一
- 国产之光,鸿蒙系统学习笔记一
- FFmpeg开发笔记(一)搭建Linux系统的开发环境
- java学习笔记11–Annotation详解编程语言
- Spring-data-jpa 学习笔记(一)详解编程语言
- 深入浅出MySQL笔记(mysql笔记)
- 腾讯大神开放Redis学习笔记(腾讯大神redis笔记)
- 狂神解说Redis记录这些宝贵的经验(狂神解说redis笔记)
- prototype学习笔记整理
- jquery在项目中做复选框时遇到的一些问题笔记
- NodeJS学习笔记之Connect中间件模块(二)