注该篇文章已与我的个人博客同步更新。欢迎移步https://cqh-i.github.io/体验更好的阅读效果。隔板法是组合数学的方法用来处理n个无差别的球放进k个不同的盒子的问题。可一般化为求不定方程的解数并利用母函数解决问题。隔板法与插空法的原理一样。例子例1.现在有10个球要放进3个盒子里●●●●●●●●●●隔2个板子把10个球被隔开成3个部分●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、…如此类推10个球放进3个盒子的方法总数为( 10 − 1 3 − 1 ) ( 9 2 ) 36 {\displaystyle {\binom {10-1}{3-1}}{\binom {9}{2}}36}(3−110−1)(29)36n个球放进k个盒子的方法总数为( n − 1 k − 1 ) {\displaystyle {\binom {n-1}{k-1}}}(k−1n−1)(普通隔板法)问题等价于求x 1 x 2 . . . x k n {\displaystyle x_{1}x_{2}...x_{k}n}x1x2...xkn的可行解数其中x 1 , x 2 , . . . , x k {\displaystyle x_{1},x_{2},...,x_{k}}x1,x2,...,xk为正整数。理解隔板法隔板法就是在n个元素间的n-1个空插入k-1个板子把n个元素分成k组的方法。应用隔板法必须满足的3个条件n个元素是相同的k个组是互异的每组至少分得一个元素公式将n个相同的求放到m个不同的盒子里的个数为C n − 1 m − 1 C_{n-1}^{m-1}Cn−1m−1例如把10个相同的球放入3个不同的箱子每个箱子至少一个问有几种情况C n − 1 m − 1 C 9 2 36 C_{n-1}^{m-1}C_{9}^{2}36Cn−1m−1C9236空盒子推广(添元素隔板法)例2.现在有10个球要放进3个盒子里并允许空盒子。考虑103个球的情况●|●|●●●●●●●●●●●、●|●●|●●●●●●●●●●、●|●●●|●●●●●●●●●、●|●●●●|●●●●●●●●、●|●●●●●|●●●●●●●、…每个盒子的球都被拿走一个得到一种情况如此类推||●●●●●●●●●●、|●|●●●●●●●●●、|●●|●●●●●●●●、|●●●|●●●●●●●、|●●●●|●●●●●●、…则问题就等价于把13个相同小球放入3个不同箱子每个箱子至少一个有几种情况C n m − 1 m − 1 C 12 2 66 C_{nm-1}^{m-1}C_{12}^{2}66Cnm−1m−1C12266n个球放进k个盒子的方法总数允许空盒子等同于nk个球放进k个盒子的方法总数不允许空盒子即( n k − 1 k − 1 ) {\displaystyle {\binom {nk-1}{k-1}}}(k−1nk−1)问题等价于求x 1 x 2 . . . x k n {\displaystyle x_{1}x_{2}...x_{k}n}x1x2...xkn的可行解数其中x 1 , x 2 , . . . , x k {\displaystyle x_{1},x_{2},...,x_{k}}x1,x2,...,xk为非负整数。隔板法应用添元素隔板法例3.把10个相同的小球放到3个不同的箱子第一个箱子至少1个第二个箱子至少3个第3个箱子可以为空有几种情况分析: 我们可以在第二个箱子先放入10个小球中的2个小球剩8个放3个箱子然后在第三个箱子放入8个小球之外的1个小球即补充了一个球则问题转化为把9个相同小球放3不同箱子每箱至少1个几种方法C 8 2 28 C_{8}^{2}28C8228减元素隔板法例4. 将20个相同的小球放入编号分别为1234的四个盒子中要求每个盒子中的球数不少于它的编号数求放法总数。分析先在编号1234的四个盒子内分别放0123个球剩下14个球再把剩下的球分成4组每组至少1个由例1知方法有C 13 3 286 C_{13}^{3}286C133286种.添板插板法例5.有一类自然数从第三个数字开始每个数字都恰好是它前面两个数字之和直至不能再写为止如2571459等这类数共有个分析因为前2位唯一确定了整个序列只要求出前两位的所有情况即可设前两位为a和b显然a b 9且a不为0.1_1_1_1_1_1_1_1_1_ _ 1代表9个1- 代表10个空位我们可以在这9个空位中插入2个板分成3组第一组取到a个1第二组取到b个1但此时第二组始终不能取空若多添加第10个空时设取到该板时第二组取空即b0所以一共有C 10 2 45 C_{10}^{2}45C10245选板法例6.有10粒糖如果每天至少吃一粒(多不限)吃完为止求有多少种不同吃法分析o_o_o_o_o_o_o_o_o_o o代表10个糖_ 代表9个空所以10块糖9个空插入9块隔板每个板都可以选择放或不放相邻两板间的糖一天吃掉这样共有2 9 512 2^951229512啦.分类插板法例7.小梅有15块糖如果每天至少吃3块吃完为止那么共有多少种不同的吃法此问题不能用插板法的原因在于没有规定一定要吃几天因此我们需要对吃的天数进行分类讨论最多吃5天最少吃1天1吃1天或是5天各一种吃法 一共2种情况2吃2天每天预先吃2块即问11块糖每天至少吃1块吃2天几种情况C 10 1 10 C_{10}^{1}10C101103吃3天每天预先吃2块即问9块糖每天至少1块吃3天?C 8 2 28 C_{8}^{2}28C82284吃4天每天预先吃2块即问7块糖每天至少1块吃4天C 6 3 20 C_{6}^{3}20C6320所以一共是 210282060 种二次插板法例8 在一张节目单中原有6个节目若保持这些节目相对次序不变再添加3个节目共有几种情况-o-o-o-o-o-o- 三个节目abc可以用一个节目去插7个空位再用第二个节目去插8个空位用最后个节目去插9个空位所以一共是C 7 1 × C 8 1 × C 9 1 504 C_{7}^{1}×C_{8}^{1}×C_{9}^{1}504C71×C81×C91504种参考维基百科-隔板法排列组合