捆绑与隔板法

捆绑法

例1：8人排成一队，甲乙必须相邻的排列数

例2：8人排成一队，甲乙必须不相邻的排列数

例3：8人排成一队，甲乙必须相邻且与丙不相邻的排列数

例4：8人排成一队，甲乙必须相邻，丙丁必须相邻的排列数

例5：8人排成一队，甲乙不相邻，丙丁不相邻的排列数

普通隔板法

例1. 求方程 x+y+z=10的正整数解的个数。
将10个球排成一排，球与球之间形成9个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为x、y、z之值（如下图）。则隔法与解的个数之间建立了一一对立关系，故解的个数为C(n-1, m-1) = C(9, 2)。

例2. 把10个相同的小球放入3个不同的箱子，每个箱子至少一个，问有几种情况？
箱子看作隔板
C(n-1, m-1) = C(9, 2)

例3. 某人射击8枪，中了4枪，其中三枪连续，另外一枪单独命中，问有多少种排法？
将未中的4枪看作隔板，连续三枪和单独一枪看作两个小球，共5个空隙可选

例4：马路上有编号1, 2, 3, ... , 10个路灯，为了节约用电同时看清路面，可以把其中的三个路灯关掉，但不能同时关掉相邻的两个或三个，两端的路灯也不能关闭，问满足条件的关灯方法共多少种？
将要关掉的三个灯看作隔板，其余7个灯看作小球

添加元素隔板法

例1. 求方程 x+y+z=10的非负整数解的个数。
注意到x、y、z可以为零，故普通隔板法中的限定“每空至多插一块隔板”就不成立了，怎么办呢？只要添加三个球，给x、y、z各添加一个球，这样原问题就转化为求 x+y+z=13的正整数解的个数了，则问题就等价于把13个相同小球放入3个不同箱子，每个箱子至少一个，有几种情况？易得解的个数为C(n + m -1, m-1) = C(12, 2)。

例2. 把10个相同的小球放入3个不同的箱子，每个箱子可为空，问有几种情况？
C(n + m -1, m-1) = C(12, 2)

例3： 把10个相同小球放入3个不同箱子，第一个箱子至少1个，第二个箱子至少3个，第三个箱子可以放空球，有几种情况？
先放1个球到第一个箱子，3个球到第二个箱子，然后问题转换为将6个球放入3个不同的箱子，每个箱子可为空，问有几种情况？
C(n + m - 1, m - 1) = C(8, 2)

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

例5：有一类自然数，从第三个数字开始，每个数字都恰好是它前面两个数字之和，直至不能再写为止，如257，1459等等，这类数共有几个？
前两位数就能确定该数为多少。
设第一位为a，第二位为b，有a + b <= 9 && a > 0
可得a + b + c = 8, a,b,c >= 0
C(m + n - 1, m - 1) = C(10, 2)

选板法

例1： 有10粒糖，如果每天至少吃一粒(多不限)，吃完为止，求有多少种不同吃法？
板数不定，可以是1, 2, …, 9
10块糖，9个空，插入9块板，每个板都可以选择放或是不放，相邻两个板间的糖一天吃掉
这样一共就是 2^9= 512

分类插板

例1： 小梅有15块糖，如果每天至少吃3块，吃完为止，那么共有多少种不同的吃法？
此问题不能用插板法的原因在于没有规定一定要吃几天，因此我们需要对吃的天数进行分类讨论
最多吃5天，最少吃1天
1： 吃1天或是5天，各一种吃法 一共2种情况
2：吃2天，每天预先吃2块，即问11块糖，每天至少吃1块，吃2天，几种情况？ C（10， 1）=10
3：吃3天，每天预先吃2块，即问9块糖，每天至少1块，吃3天? C（8 ，2）=28
4：吃4天，每天预先吃2块，即问7块糖，每天至少1块，吃4天？c（6 ，3）=20
所以一共是 2+10+28+20=60 种

逐步插板法

例1 ：在一张节目单中原有6个节目，若保持这些节目相对次序不变，再添加3个节目，共有几种情况？
-o - o - o - o - o - o - 三个节目abc
可以用一个节目去插7个空位，再用第二个节目去插8个空位，用最后个节目去插9个空位
所以一共是 c（7, 1）×c(8, 1)×c(9 ,1)=504种

几个思维含量的例题：

1.[ZOJ3557]How Many Sets II
给一个集合，一共n个元素，从中选取m个元素，选出的元素中没有相邻的元素的选法一共有多少种？
思路：先取出m个元素，剩余n - m个元素，共n - m + 1个空位，然后将m个元素插入到n - m + 1个空位中
C(n - m + 1, m)

2.hdu 3037 Saving Beans
有n个不同的盒子，在每个盒子中放一些球（可以不放），使得总球数≤m,求方案数（mod p）

方法1：分类讨论总球数
ans=C(n-1,n-1)+C(n,n-1)+C(n+1,n-1)+……+C(n+m-2,n-1)+C(n+m-1,n-1)
=C(n+m,n);(mod p)
方法2：考虑增加一个盒子
总球数≤m，一般我们就是总球数就是m，所以我们可以增加一个盒子，现在n+1个盒子，现在假设就要放m个球，n来来放k个球，剩下的m-k就放在那个我们增加的盒子里，这样n个盒子的组合球数就是我们要求的，所以题目等价于m个球放入n+1个盒子中，盒子有里球数可以为0，添元素插板法，每一个盒子都增加一个球，即m+n+1个球放入n+1个盒子，c（m+n，n）为答案。

参考

原文链接：https://blog.csdn.net/sdz20172133/article/details/81431066