排列组合--插板法、插空法、捆绑法

排列组合问题 插板法 (分组 )、插空法（不相邻） 、捆绑法（相邻）【基本题型】插板法（m 为空的数量）有 n 个相同的元素，要求分到不同的m 组中，且每组至少有一个元素，问有多少种分法？图中“”表示相同的名额， “ ”表示名额间形成的空隙，设想在这几个空隙中插入六块“挡板”，则将这 10 个名额分割成七个部分，将第一、二、三、七个部分所包含的名额数分给第一、二、三七所学校，则“挡板”的一种插法恰好对应了 10 个名额的一种分配方法，反之，名额的一种分配方法也决定了档板的一种插法，即挡板的插法种数与名额的分配方法种数是相等的，【总结】需满足条件： n 个相同元素， 不同个 m 组，每组至少有一个元素 ，则只需在n 个元素的 n-1个间隙中放置m-1 块隔板把它隔成m 份即可 ,共有种不同方法 。注意：这样对于很多的问题，是不能直接利用插板法解题的。但，可以通过一定的转变，将其变成符合上面3 个条件的问题， 这样就可以利用插板法解决，并且常常会产生意想不到的效果。插板法就是在n 个元素间的（n-1）个空中插入若干个（ b）个板 ,可以把 n 个元素分成（b+1 ）组的方法 .应用插板法必须满足三个条件：（1） 这 n 个元素必须互不相异（2） 所分成的每一组至少分得一个元素(3) 分成的组别彼此相异举个很普通的例子来说明把 10 个相同的小球放入3 个不同的箱子,每个箱子至少一个,问有几种情况 ?问题的题干满足条件（ 1）（ 2）,适用插板法 ,c9 2=36下面通过几道题目介绍下插板法的应用e 二次插板法例 8 ：在一张节目单中原有6 个节目 ,若保持这些节目相对次序不变,再添加 3 个节目 ,共有几种情况 ?-o - o - o - o - o - o -三个节目abc可以用一个节目去插7 个空位 ,再用第二个节目去插8 个空位 ,用最后个节目去插9 个空位所以一共是c7 1c8 1c9 1=504 种【基本解题思路】将 n 个相同的元素排成一行，n 个元素之间出现了（n-1）个空档，现在我们用（m-1）个 “档板 ”插入（ n-1） 个空档中，就把n 个元素隔成有序的m 份，每个组依次按组序号分到对应位置的几个元素（可能是1 个、 2 个、 3 个、 4 个、.），这样不同的插入办法就对应着n 个相同的元素分到m 组的一种分法，这种借助于这样的虚拟 “档板 ”分配元素的方法称之为插板法。【基本题型例题】【例 1】 共有 10 完全相同的球分到7 个班里，每个班至少要分到一个球，问有几种不同分法？解析：我们可以将 10 个相同的球排成一行， 10 个球之间出现了 9 个空隙，现在我们用 6 个档板 ”插入这 9 个空隙中，就 “把 10 个球隔成有序的 7 份，每个班级依次按班级序号分到对应位置的几个球（可能是 1 个、2 个、 3 个、 4 个），这样，借助于虚拟 “档板 ”就可以把 10 个球分到了 7 个班中。【基本题型的变形（一）】题型：有n 个相同的元素，要求分到m 组中，问有多少种不同的分法？解题思路：这种问题是允许有些组中分到的元素为“0”，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上1 个，这样所要元素总数就m 个，问题也就是转变成将（n+m ）个元素分到m 组，并且每组至少分到一个的问题，也就可以用插板法来解决。【例 2】有 8 个相同的球放到三个不同的盒子里，共有（）种不同方法 .a 35 b 28 c 21 d 45解答：题目允许盒子有空，则需要每个组添加1 个，则球的总数为8+3 1=11 ，此题就有c（ 10， 2）=45（种）分法了，选项d 为正确答案。【基本题型的变形（二）】题型：有 n 个相同的元素，要求分到m 组，要求各组中分到的元素至少某个确定值s（ s 1，且每组的s 值可以不同），问有多少种不同的分法？解题思路：这种问题是要求组中分到的元素不能少某个确定值s，各组分到的不是至少为一个了。对于这样的题， 我们就首先将各组都填满，即各组就填上对应的确定值s 那么多个， 这样就满足了题目中要求的最起码的条件，之后我们再分剩下的球。这样这个问题就转变为上面我们提到的变形（一）的问题了，我们也就可以用插板法来解决。【例 3】 15 个相同的球放入编号为1、2、3 的盒子内，盒内球数不少于编号数，有几种不同的放法？ 解析：编号 1：至少 1 个，符合要求。编号 2：至少 2 个：需预先添加1 个球，则总数 -1编号 3：至少 3 个，需预先添加2 个，才能满足条件，后面添加一个，则总数-2则球总数15-1-2=12 个放进 3 个盒子里所以 c（ 11， 2）=55 （种）【例】 10 个学生中，男女生各有5 人，选 4 人参加数学竞赛。（1）至少有一名女生的选法种数为 。（2）a 、b 两人中最多只有一人参加的选法种数为 10解法 1：10 名中选 4 名代表的选法的种类：c4, 排除 4名参赛全是男生： c 4(排除法 )c4c4=2055105解法 2：选 1 女生时，选2 个女生时，选3、 4 个女生时的选法，分别相加真题（2010 年国考真题）某单位订阅了多少种不同的发放方法？（30 份学习材料发放给） a.7b.93 个部门，每个部门至少发放c.10d.129 份材料。问一共有解析：每个部门先放8 个，后面就至少放一个，三个部门则要先放8 3=24 份，还剩下30-24=6 份来放入这三个部门，且每个部门至少发放1 份，则 c（ 5,2） =10插空法插空法就是对于解决某几个元素要求不相邻的问题时，先将其他元素排好，再将所指定的不相邻的元素插入它们的间隙或两端位置。首要特点就是不相邻。下面举例说明。一. 数字问题【例】把 1， 2， 3， 4， 5组成 没有重复数字且数字 1， 2不相邻 的五位数，则所有不同排法有多少种？解析：本题直接解答较为麻烦，因为可先将3， 4， 5三个元素排定，共有种排法，然后再将1， 2插入四个空位共有种排法，故由乘法原理得，所有不同的五位数有二. 节目单问题【例】在一张节目单中原有六个节目，若保持这些节目的相对顺序不变，再添加进去三个节目，则所有不同的添加方法共有多少种？解析： -o - o - o - o - o - o -六个节目算上前后共有七个空位，那么加上的第一个节目则有种方法； 此时有七个节目， 再用第二个节目去插八个空位有种方法； 此时有八个节目，用最后一个节目去插九个空位 有种方法。由乘法原理得，所有不同的添加方法为：。三. 关灯问题【例】一条马路上有编号1， 2， 3， 4， 5， 6， 7， 8， 9的九盏路灯，为了节约用电，可以把其中的三盏灯关掉，但 不能同时关掉相邻两盏或三盏，则所有不同的关灯方法有多少种？解析：如果直接解答须分类讨论，故可把六盏亮着的灯看作六个元素，然后用不亮的三盏灯去插七个空位（用不亮的 3盏灯去插剩下亮的6盏灯空位，就有7个空位）共有种方法，因此所有不同的关灯方法为种。四. 停车问题【例】停车场划出一排12个停车位置，今有8辆车需要停放，要求空位置连在一起，不同的停车方法有多少种？解析：先排好 8辆车有种方法，要求空位置连在一起（剩下4个空位在一起，来插入8辆车，有 9个空位可以插），将空位置插入其中有种方法。所以共有种方法。五. 座位问题【例】3个人坐在一排8个椅子上，若每个人左右两边都有空位，则坐法的种类有多少种？解法：先拿出5个椅子排成一排，在5个椅子中间出现4个空，再让3个人每人带一把椅子去插空，于是有种。解答：根据题目要求，则其中一个盒子必须得放2 个， 其他每个盒子放1 个球， 所以从 6 个球中挑出2 个球看成一个整体，则有2c6 ，这个整体和剩下4 个球放入5 个盒子里，则有525aca5 。方法是65排列组合中的解题方法之插板法一、基础理论：插板是一个无形的东西即板子，它不能代表一个元素，它区别于插空法。插板法是用于解决“相同元素 ” 分组问题。判断插板法的题目主要看题干中的两个词语：相同元素至少为1， 如果有这样两个词语一般此题就可以直接插板进行解题。引例说明：春节前单位慰问困难职工，将10 份相同的慰问品分给6 名职工，每名职工至少要分得1 份慰问品，分配方法共有：a.84 种 b.126 种 c.210 种 d.252 种【分析】此题第一眼给人的感觉是能用列举法进行分类解题，但是细一思考分类的情况太多了，不易计算，因为想用插板法解题一般是分两类或三类。而插板法就可以使这种为题迎刃而解。利用无形的板子把其分割开来。【解析】 “10 份慰问品相同且每人至少得1 份”，满足插板法的两个前提相同元素至少为1，故可直接使用插板法。将10 份慰问品依次排成一条直线，我们用插板的形式把慰问品分给6 名职工，中间形成9 个空，插上第1 个板子，则第一个板子之前的分给第一名职工，在后面又插了一个板子，表示第1 个板子和第 2 个板子之间的分给第二名职工，依次类推， 因为要分给6 个人， 所以要插5 个板子， 第 5 个板子之后的分给第六名职工，所以只要板子固定了，那么每名职工分几份慰问品就固定了。所以 10 分慰问品中间形成了9 个空 ;分给 6 个人，插入5 个板 ;共有 =126 种分配方法。注：估计有的同学会问，为什么第一个慰问品之前的位置和最后一个慰问品之后的位置不能放板子。其实原因在于 “每名员工至少分1 份慰问品 ”，如果在第一个慰问品之前的位置放板子那么第一名职工就一份分不到了，如果在最后一个慰问品之后的位置放板子那么最后一名职工就一份分不到了。二、真题举例：例 1、假设 x、y、z 是三个非零自然数，且有x+y+z=36 ，则共有多少组满足条件的解? a.700 b.665 c.630 d.595【分析】此题可以看做是36 块糖排成一排，即元素相同;由于 x、y、z 是非零自然数，即至少为1， 问题： x+y+z=36 ，顺便看成3 个人来分这36 块糖。满足插板法应用条件。【解析】根据题意，36 块糖内部形成35 个空位，分给三个人，需要插两个板子，故有=595 种，而一种分法对应着一组解，如x=1 ， y=1 ， z=34，就是一组解。共有595 组解。因此，选d 。例 2、将 10 本没有区别的图书分到编号为1、2、3 的图书馆，要求每个图书馆分得图书数量不小于其编号数，问共有多少种不同的分法?( ) a.12 b.15 c.30 d.45【分析】根据题意，“10 本没有区别的图书”即相同元素，“要求每个图书馆分得图书数量不小于其编号数“即 1 号图书馆至少分1 本， 2 号图书馆至少分两本，3 号图书馆至少分3 本， 分析完题意之后发现似乎不满足插板法的前提条件至少为1，类似的这种题目我们只需要适当变形就可利用插板法解题。【解析】 1 号图书馆至少分1 本，已经满足至少为1，不用变形。而2 号图书馆至少分两本，所以可从10 本中取出一本先给2 号图书馆。而3 号图书馆至少分3 本，可以从10 本中取出两本书给3 号图书馆，所以在给出一本和两本，那么还剩下7 本，现在1 号， 2 号， 3 号图书馆至少在发放一本书就可以满足了，那么此时就可以用插板法解题。所以答案是=15小结：题目中一般有相同元素，至少为什么，此题都可用插板法解题，所以大家要不断熟悉插板法的应用。三、插板法和列举法的对比例 3、10 个名额分配到八个班，每班至少一个名额，问有多少种不同的分配方法?a.34 种 b.36 种 c.40 种 d.42 种【答案】 b【列举法】先每个班级分一个名额，然后剩下两个名额， 如果两个名额分到一个班级里面则有,如果两个名额分到两个班级里面则有种分法，则共有8+28=36.【插板法】 10 个名额 9 个空，插入7 个板，共有种分配方法。例 4、某单