排列组合问题之插板法.

1、排列组合问题之插板法 :插板法是用于解决“相 同元素”分 组问题,且要求每组均“非 空” 即, 要求每组 至少一个元素; 若对于“可 空”问 题,即每组可以是零个元素 ,又该如何解题呢 ?例 1. 现有 10个完全相同的球全部分给 7个班级, 每班至少 1个球, 问共有多少 种不同的分法 ? 【解析】 :题目中球的分法共三类 :第一类:有 3个班每个班分到 2个球,其余 4个班每班分到 1个球。其分法种数 为 C 37=35。第二类:有 1个班分到 3个球, 1个班分到 2个球,其余 5个班每班分到 1 个球。其分法种数 2* C 27=42。第三类:有 1个班分到 4个球,其余的 6个班每班

2、分到 1个球。其分法种数 C 17=7。所以, 10个球分给 7个班,每班至少一个球的分法种数为 84:。由上面解题过程可以明显感到对这类问题进行分类计算 , 比较繁锁 , 若是上题中 球的数目较多处理起来将更加困难 , 因此我们需要寻求一种新的模式解决问题 , 我 们创设这样一种虚拟的情境插板。将 10个相同的球排成一行 , 10个球之间出现了 9个空档, 现在我们用“档 板” 把 10个球隔成有序的 7份,每个班级依次按班级序号分到对应位置的几个球 (可能 是 1个、 2个、 3个、 4个 ,借助于这样的虚拟“档 板”分 配物品的方法称之为插 板法。由上述分析可知 ,分球的方法实际上为档板

3、的插法 :即是在 9个空档之中插入 6 个“档 板”(6个档板可把球分为 7组 ,其方法种数为 C 39=84。由上述问题的分析解决看到 , 这种插板法解决起来非常简单 , 但同时也提醒各位 考友, 这类问题模型适用前提相当严格 ,必须同时满足以下 3个条件: 所要分的元素必须完全相同 ; 所要分的元素必须分完 ,决不允许有剩余 ; 参与分元素的每组至少分到 1个,决不允许出现分不到元素的组。下面再给各位看一道例题 :例 2.有 8个相同的球放到三个不同的盒子里 ,共有（种不同方法 .A . 35 B . 28 C . 21 D . 45【解析】 :这道题很多同学错选 C , 错误的原因是直接

4、套用上面所讲的 “插 板 法” 而, 忽略了“插 板法”的 适用条件。例 2和例 1的最大区别是 :例 1的每组元素 都要求“非 空” 而, 例 2则无此要求,即可以出现空盒子。其实此题还是用“插 板法” , 只是要做一些小变化 ,详解如下 :设想把这 8个球一个接一个排起来 ,即 | | | | | 共 |形成 | 9个 |空档 |,（此 时的空档包括中间 7个空档和两端 2个空档 ,然后用 2个档板把这 8个球分成 3组, 先插第一个档板 , 由于可以有空盒 ,所以有 9个空档可以插 ;再插第二个板 ,有 10个空 档可以插 ,但由于两个板是不可分的 （也就是说当两个档板相邻时 ,虽然是两种插法 , 但实际上是一种分法 ,所以共 C 210种【提示】 :利用“插 板法”解 决这种相同元素问题时 ,一定要注意“空 ”与 “不 空”的 分析, 防止掉入陷阱。【总结】 :“非 空”问 题插板法原型为 :设有 M 个相同元素,分成 N 组,每组至少 一个元素的分组方法共有 C N(M-1; “可 空”问 题插板法问题原型为 :设有 M 个相同元素 , 分成 N 组,则分组方法共有 C (N-1(M+2 种方法。练习 1. 有 10级台阶, 分 8步走完。每步可以迈 1级、 2级或 3级台阶, 有多少