《排列组合--插板法、插空法、捆绑法》由会员分享，可在线阅读，更多相关《排列组合--插板法、插空法、捆绑法（6页珍藏版）》请在金锄头文库上搜索。
1、排列组合问题插板法(分组）、插空法(不相邻）、捆绑法（相邻) 插 板 法 （为空的数量) 【基本题型】有n个相似的元素,规定分到不同的m组中，且每组至少有一种元素,问有多少种分法?图中“ ”表达相似的名额,“ ”表达名额间形成的空隙,设想在这几种空隙中插入六块“挡板”，则将这10个名额分割成七个部分,将第一、二、三、七个部分所涉及的名额数分给第一、二、三七所学校，则“挡板”的一种插法正好相应了 个名额的一种分派措施,反之，名额的一种分派措施也决定了档板的一种插法，即挡板的插法种数与名额的分派措施种数是相等的,【总结】需满足条件：n个相似元素，不同个m组，每组至少有一种元素，则只需在个元素的n-
2、1个间隙中放置m-1块隔板把它隔成m份即可,共有种不同措施。注意:这样对于诸多的问题,是不能直接运用插板法解题的。但，可以通过一定的转变，将其变成符合上面3个条件的问题，这样就可以运用插板法解决,并且常常会产生意想不到的效果。【基本解题思路】将n个相似的元素排成一行，个元素之间浮现了（n-1)个空档，目前我们用(m-1)个“档板”插入(n-1)个空档中,就把n个元素隔成有序的m份,每个组依次按组序号分到相应位置的几种元素(也许是1个、2个、个、4个、)，这样不同的插入措施就相应着n个相似的元素分到m组的一种分法,这种借助于这样的虚拟“档板”分派元素的措施称之为插板法。【基本题型例题】【例】 共
3、有1完全相似的球分到7个班里,每个班至少要分到一种球,问有几种不同分法？解析:我们可以将10个相似的球排成一行，10个球之间浮现了个空隙,目前我们用6个档板”插入这9个空隙中，就“把10个球隔成有序的7份,每个班级依次按班级序号分到相应位置的几种球（也许是1个、2个、3个、个),这样，借助于虚拟“档板”就可以把1个球分到了7个班中。【基本题型的变形(一)】题型：有n个相似的元素，规定分到m组中,问有多少种不同的分法?解题思路:这种问题是容许有些组中分到的元素为“0”，也就是组中可觉得空的。对于这样的题，我们就一方面将每组都填上1个，这样所要元素总数就个，问题也就是转变成将(nm）个元素分到组,
4、并且每组至少分到一种的问题，也就可以用插板法来解决。【例2】有8个相似的球放到三个不同的盒子里，共有（ )种不同措施 A.5 B28 C.1 D.5解答:题目容许盒子有空，则需要每个组添加个,则球的总数为8+31=1,此题就有C（10,)=45(种)分法了,选项D为对的答案。【基本题型的变形(二)】题型:有n个相似的元素,规定分到组，规定各组中分到的元素至少某个拟定值（1，且每组的s值可以不同），问有多少种不同的分法？ 解题思路：这种问题是规定组中分到的元素不能少某个拟定值s,各组分到的不是至少为一种了。对于这样的题，我们就一方面将各组都填满,即各组就填上相应的拟定值s那么多种，这样就满足了题
5、目中规定的最起码的条件，之后我们再分剩余的球。这样这个问题就转变为上面我们提到的变形(一）的问题了，我们也就可以用插板法来解决。【例3】15个相似的球放入编号为1、2、3的盒子内,盒内球数不少于编号数，有几种不同的放法？解析：编号1：至少1个,符合规定。编号2:至少2个：需预先添加1个球,则总数编号:至少3个,需预先添加2个,才干满足条件,背面添加一种，则总数-则球总数1-1-=1个放进3个盒子里因此C(,2)=55（种)【例】1 个学生中，男女生各有5 人，选4 人参与数学竞赛。(1)至少有一名女生的选法种数为_。（）A、 两人中最多只有一人参与的选法种数为_解法1：10 名中选名代表的选法
6、的种类：C10, 排除名参赛全是男生：C5 (排除法)C14 -C5405解法2：选1女生时，选2个女生时,选3、4个女生时的选法,分别相加真题预测（国考真题预测)某单位订阅了30份学习材料发放给3个部门,每个部门至少发放9份材料。问一共有多少种不同的发放措施?( ） A7 B.9 C.10 D.12 解析:每个部门先放个,背面就至少放一种，三个部门则要先放83=4份，还剩余302=6份来放入这三个部门，且每个部门至少发放份,则（，）=10 插 空 法 插空法就是对于解决某几种元素规定不相邻的问题时，先将其她元素排好,再将所指定的不相邻的元素插入它们的间隙或两端位置。首要特点就是不相邻。下面举
7、例阐明。一 数字问题【例】把1，,3，5构成没有反复数字且数字,2不相邻的五位数,则所有不同排法有多少种?解析:本题直接解答较为麻烦,由于可先将3，4，三个元素排定，共有种排法，然后再将1，2插入四个空位共有种排法,故由乘法原理得，所有不同的五位数有二. 节目单问题【例】在一张节目单中原有六个节目,若保持这些节目的相对顺序不变,再添加进去三个节目,则所有不同的添加措施共有多少种?解析:o- - o - o -o 六个节目算上前后共有七个空位,那么加上的第一种节目则有种措施;此时有七个节目,再用第二个节目去插八个空位有种措施；此时有八个节目，用最后一种节目去插九个空位有种措施。由乘法原理得，所有
8、不同的添加措施为：。三. 关灯问题【例】一条马路上有编号1，2,3,4,6，7,8，的九盏路灯，为了节省用电，可以把其中的三盏灯关掉，但不能同步关掉相邻两盏或三盏,则所有不同的关灯措施有多少种?解析：如果直接解答须分类讨论，故可把六盏亮着的灯看作六个元素,然后用不亮的三盏灯去插七个空位(用不亮的盏灯去插剩余亮的6盏灯空位,就有7个空位）共有种措施，因此所有不同的关灯措施为种。四停车问题【例】停车场划出一排12个停车位置，今有辆车需要停放,规定空位置连在一起，不同的停车措施有多少种?解析:先排好辆车有种措施，规定空位置连在一起(剩余个空位在一起,来插入8辆车,有9个空位可以插)，将空位置插入其中有种措施。因此共有种措施。五. 座位问题【例】个人坐在一排8个椅子上，若每个人左右两边均有空位,则坐法的种类有多少种?解法:先拿出5个椅子排成一排，在5个椅子中间浮现个空，再让个人每人带一把椅子去插空，于是有种。 捆绑 法 解答:根据题目规定，则其中一种盒子必须得放个，其她每个盒子放1个球,因此从个球中挑出2个球当作一种整体,则有,这个整体和剩余4个球放入个盒子里，则有。措施是
