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

1、排列组合问题一一插板法（分组）、插空法（不相邻）、捆绑法（相令B）插板法（m为空的数量）【基本题型】有卜个相同/元素,要求分到不啊的一m组中，且每组气巴匚三产,问有多少种分法？oooooloojooIIq图中“”表示相同的名额，“”表示名额间形成的空隙，设想在这几个空隙中插入六块“挡板”，则将这10个名额分割成七个部分，将第一、二、三、七个部分所包含的名额数分给第一、二、三七所学校，则“挡板”的一种插法恰好对应了io个名额的一种分配方法，反之，名额的一种分配方法也决定了档板的一种插法，即挡板的插法种数与名额的分配方法种数是相等的，【总结】需满足条件：h个相同元素，不同个m组，每组至少有一个元素

2、则只需在n个元素的3个条件的问题,n-1个间隙中放置m-1块隔板把它隔成m份即可，共有种不同方法注意：这样对于很多的问题，是不能直接利用插板法解题的。但，可以通过一定的转变，将其变成符合上面这样就可以利用插板法解决，并且常常会产生意想不到的效果。插板法就是在n个元素间的（n-1）个空中插入若干个（b）个板，可以把n个元素分成（b+1）组的方法应用插板法必须满足三个条件：（1）这n个元素必须互不相异（2）所分成的每一组至少分得一个元素（3）分成的组别彼此相异举个很普通的例子来说明把10个相同的小球放入3个不同的箱子，每个箱子至少一个，问有几种情况？问题的题干满足条件（1）（2）,适用插板法,c9

3、2=36下面通过几道题目介绍下插板法的应用e二次插板法例8:在一张节目单中原有6个节目，若保持这些节目相对次序不变，再添加3个节目，共有几种情况？-o-o-o-o-o-o-二个下目abc可以用一个节目去插7个空位，再用第二个节目去插8个空位，用最后个节目去插9个空位所以一共是c71XC81Xc91=504种【基本解题思路】将n个相同的元素排成一行，n个元素之间出现了（n-1）个空档，现在我们用（m-1）个档板”插入（n-1）个空档中，就把n个元素隔成有序的m份，每个组依次按组序号分到对应位置的几个元素（可能是1个、2个、3个、4个、.），这样不同的插入办法就对应着n个相同的元素分到m组的一种分

4、法，这种借助于这样的虚拟档板”分配元素的方法称之为插板法。【基本题型例题】【例1】共有10完全相同的球分到7个班里，每个班至少要分到一个球，问有几种不同分法？解析：我们可以将10个相同的球排成一行，10个球之间出现了9个空隙，现在我们用6个档板”插入这9个空隙中，就把10个球隔成有序的7份，每个班级依次按班级序号分到应位置的几个球（可能是1个、2个、3个、4个），这样，借助于虚拟档板”就可以把10个球分到了7个班中。【基本题型的变形（一）】题型：有n个相同的元素，要求分到m组中，问有多少种不同的分法？解题思路：这种问题是允#有些组中分到的元素为何:也就是组中可以为空的。对于这样的题，我们就首先

5、将每组都填上1个，这样所要元素总数就m个，问题也就是转变成将（n+m）个元素分到m组，并且每组至少分到一个的问题，也就可以用插板法来解决。【例2】有8个相同的球放到三个不同的盒子里，共有（）种不同方法.A.35B.28C.21D.45解答：题目允许盒子有空，则需要每个组添加1个，则球的总数为8+3X1=11,此题就有C（10,2）=45（种）分法了，选项D为正确答案。【基本题型的变形（二）】题型：有n个相同的元素，要求分到m组，要求各组中分到的元素至少某个确定值S（s>1,且每组的s值可以不同），问有多少种不同的分法？解题思路：这种问题是要求组中分到的元素不能少某个确定值s,各组分到的不

6、是至少为一个了。对于这样的题，我们就首先将各组都填满，即各组就填上对应的确定值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（种）K例题有9颗相同确，每天至少吃1颗要4天吃完,有多少

7、种吃法？解析：原理同上，只需要用3个板插入到9颖糖形成的8个内部空隙，将9颠穗分成4如且每蛆戮目不少子1即可.因而3个板互不相邻，其方法数为C联【炼刀1现有10个完全相同的篮球全部渊7个班级，每班至少1个球>问共有多少种不同的分法？注释：每组允许有春叶元素时也可以用抵极法，其原理不同，注意下题解）统J区别.例题）将8个完全相同的球放到3个不同的盒子中，一共有多少种方法？解析：此题中没有要求每个盆子中至少放一小球，因此其解法不同于上面的标板法，但仍旧是描入2个板，分成三如口但有分组的过程中，允许西块板之间没有俅口其考虑思维为插入两块板后，与原来的8个球一共1。个元素所有方法数实陆是这1。个

8、元素的一个队列，但因为球之间无差别，板之间丸塞别，所以方法数实际为从】。个无素所占的10个位宣中桃2个住毒加上2个板，其余住贵金都放球即可.因"盼法数为党.注释：特别注意插板法与捆绑法、插空1却返利之处在于其元素是相邮.t例题一条马路上有翁号为h工，9的九盍路灯，现为了节约用电，要将其中的三盏关拽但不能同时关技相邻的两盏或三盏，则所有不砒关灯方法有多少种？解析：要关掉9盏灯中的3盏，怛要求相邻的灯不能关闭，因此可以先将要关棹的3盏灯拿出来，这样还轲6盏灯，现在只需把准备关闭的3盏灯插入到亮着的6盏灯所形成的空隙之间即可.6盏灯的内部及两端共有7个空，就方法数为点。【例题】一条马路的两

9、边各立着1。蓬电灯酶为了节省用电，决定每边关撞3苣，但为了安全道路起点和终点两边的灯必须是亮的而且任意一边不肓婚续关掉两盏.问总共可以有哆少总方案7&120B、320C、400D420解析：考虑一侧的关灯方法，】0番灯关捽3盏，还轲7盏,因为旃潴的灯不能关，表示3盟关捽的灯只能插在7盆灯形成的6个内部空隙中，而不能城在的塌，坟方法数为d,【例】10个学生中，男女生各有5人，选4人参加数学竞赛。（1）至少有一名女生的选法种数为。（2） A、B两人中最多只有一人参加的选法种数为解法1:10名中选4名代表的选法的种类：Ci。4,排除4名参赛全是男生：C54（排除法）C104C54=205解法

10、2:选1女生时，选2个女生时，选3、4个女生时的选法，分别相加（2010年国考真题）某单位订阅了30份学习材料发放给3个部门，每个部门至少发放9份材料。问一共有多少种不同的发放方法？（）A.7B.9C.10D.12解析：每个部门先放8个，后面就至少放一个，三个部门则要先放8X3=24份，还剩下30-24=6份来放入这三个部门，且每个部门至少发放1份，则C（5,2）=10插空法插空法就是对于解决某几个元素要求不相邻的问题时，先将其他元素排好，再将所指定的不相邻的元素插入它们的间隙或两端位置。首要特点就是不相邻。下面举例说明。1 .数字问题【例】把1,2,3,4,5组成没有重复数字且数字1,2不相

11、邻的五位数，则所有不同排法有多少种？解析：本题直接解答较为麻烦，因为可先将3,4,5三个元素排定，共有工种排法，然后再将1,2插入四个空位共有4n种排法，故由乘法原理得，所有不同的五位数有儿",兑:"72种口2 .节目单问题【例】在一张节目单中原有六个节目，若保持这些节目的相对顺序不变，再添加进去三个节目，则所有不同的添加方法共有多少种？解析：-o-o-o-o-o-o-六个节目算上前后共有七个空位，那么加上的第一个节目则有41种方法；此时有七个节目，再用第二个节目去插八个空位有41种方法；此时有八个节目，用最后一个节目去插九个空位有种方法。由乘法原理得，所有不同的添加方法为

12、：A1A1A1=7x8x9=504种。3 .关灯问题【例】一条马路上有编号1,2,3,4,5,6,7,8,9的九盏路灯，为了节约用电，可以把其中的三盏灯关掉，但不能同时关掉相邻两盏或三盏，则所有不同的关灯方法有多少种？解析：如果直接解答须分类讨论，故可把六盏亮着的灯看作六个元素，然后用不亮的三盏灯去插七个空位（用不亮的3盏灯去插剩下亮的6盏灯空位，就有7个空位）共有C/种方法，因此所有不同的关灯方法为IE1种。四.停车问题【例】停车场划出一排12个停车位置，今有8辆车需要停放，要求空位置连在一起，不同的停车方法有多少种？解析：先排好8辆车有种方法，要求空位置连在一起（剩下4个空位在一起，来插入

13、8辆车，有9个空位可以插），将空位置插入其中有1A1一。种方法。所以共有生也种方法。五.座位问题【例】3个人坐在一排8个椅子上，若每个人左右两边都有空位，则坐法的种类有多少种?解法：先拿出5个椅子排成一排，在5个椅子中间出现4个空，再让3个人每人带一把椅子去插空，于是有中=24种。【例题】若有hB、C、dE五个人排队，要求A和B两个人必须不站在一起.则有多少排队方:去？解析：题中要求AB痍人狗占左一起，所以可以先嘴除A和B之外的3个人排成一批方法数为固，然后再将A和B分别插人到其余W个人排队所形成的4个室中，也就是从4个空中挑出两个并排上两个人，其方法数为反，因此总方法数收客:E例题g个人排成

14、一队，要求甲乙必须未脚且与丙不本掰，有安少种方法？解析：甲乙相邻，可以臧娜看作一个无素，但这个整体无素又和丙不相邻，所以先不排这个甲己丙，而是排剩下的5个人，方法数为4,然后再得甲己枸成的整体元素及丙这两个元素插入到此前5人所形成的6个空里，疗法数为达、另外甲乙场个人内部还存在排序要求为用o就总方法数为Aa-a；-陈习15个男生3侬生排成一排，要求女生不能相邻,有多少种方法？注释：将要求不相邻元素插入排好元素时，要注释是否有邮插入两端位置.【例题1若有最B.C.RE五个人排队j要求A和E两个人必须不站在一起，且A和B不能站在两端,则有多少排队方法？聊法.不邻问融令f解析:原理同前，也是先排得C

15、、D>E三个人，嫁后将4B查到C、DhE所静底的断个空我因为&E不站勘端，所以只有两个空可选,方法总数为用冯L注释：对于捆绑法和插空法的区别，可简单记为“相等同捆绑法精要：所谓捆绑法，指在解决对于某几个元度求相等的问题时，先整体考虑，将t目部元素视作一个整体参与排序，然后再单独考虑这个整体内部各元素间顺序.提醒：苴首要特点是畸,其次捆绑法一般都应用在不同物体的排序问题中.例题有1。本不同的书：其中数学书4本,外语书3本，语文书3本.若将这些书排成一列放在书架上，让数学书排在一起，外语书也恰好排在一起的排法共有（）种.解析:这是一个排序问题，书本之间是不同或其中要求数学书和外语书都

16、各自在一起.为快速解决这个问题，先将4本数学书看做一个元案,将3本外语书看做一个元素，然后和剌下的3本语文书共5个元素进行统T*序，为法数为儿，然后排在一起的4本数学书之间痛序不同也对应:最后整个排序不同，所以在4本书内部也需要描序，疗法数为其，同理，外语书排序方法数为前.而三者之间建分步过程，放而用乘法原理得力用用.【例题15个人站成Th要求甲乙两人站在一起，有多少种方法？解析匕先将甲乙两人看成1个人，与剩下的3个人一起排现方法数为川，然后中乙两个人包有原序要求，方法数为耳，因此站队方法数为£住.续习】一台晚会上有6个演唱节目和4mS节目，4个舞蹈节目要排在一起，有妻少不同的翎/节

17、目的顺序？注释：运用捆绑法时-一定要注意捆绑起来由整体内部是否存在顺序的要求，有的题目有顺序的要求，有的则没有-如下面的例题.例题6个不同的球滋J3个不同的盘子中，要求每个盒子至少放一个球，一共有多少种方法？解析：按照题意，显然是2个球放到其中一个盒子，另外4个球分别放到4个盆子中，因此疔法是先从6个球中挑出2个球作为一个整体放到一个盒子中，蜷后这个整体和剩下的4个球分却由F列放到5个盒子中，地疔法数是C'A解答：根据题目要求，则其中一个盒子必须得放2个，其他每个盒子放1个球，所以从6个球中挑出2个25-25球看成一个整体，则有C6,这个整体和剩下4个球放入5个盒子里，则有A。方法是C

18、6A5排列组合中的解题方法之插板法一、基础理论：插板是一个无形的东西即板子，它不能代表一个元素，它区别于插空法。插板法是用于解决相同元素”分组问题。判断插板法的题目主要看题干中的两个词语：相同元素至少为1,如果有这样两个词语一般此题就可以直接插板进行解题。引例说明：春节前单位慰问困难职工，将10份相同的慰问品分给6名职工，每名职工至少要分得1份慰问品，分配方法共有：A.84种B.126种0.210#D.252种【分析】此题第一眼给人的感觉是能用列举法进行分类解题，但是细一思考分类的情况太多了，不易计算，因为想用插板法解题一般是分两类或三类。而插板法就可以使这种为题迎刃而解。利用无形的板子把其分

19、割开来。【解析】“1的慰问品相同且每人至少得1份”，满足插板法的两个前提相同元素至少为1,故可直接使用插板法。将10份慰问品依次排成一条直线，我们用插板的形式把慰问品分给6名职工，中间形成9个空，插上第1个板子，则第一个板子之前的分给第一名职工，在后面又插了一个板子，表示第1个板子和第2个板子之间的分给第二名职工，依次类推，因为要分给6个人，所以要插5个板子，第5个板子之后的分给第六名职工，所以只要板子固定了，那么每名职工分几份慰问品就固定了。所以10分慰问品中间形成了9个空；分26个人，插入5个板;共有G=126种分配方法。注：估计有的同学会问，为什么第一个慰问品之前的位置和最后一个慰问品之

20、后的位置不能放板子。其实原因在于每名员工至少分1份慰问品”，如果在第一个慰问品之前的位置放板子那么第一名职工就一份分不到了，如果在最后一个慰问品之后的位置放板子那么最后一名职工就一份分不到了。二、真题举例：例1、假设x、v、z是三个非零自然数，且有x+y+z=36,则共有多少组满足条件的解？A.700B.6650.630D.595【分析】此题可以看做是36块糖排成一排，即元素相同；由于x、v、z是非零自然数，即至少为1,问题：x+y+z=36,顺便看成3个人来分这36块糖。满足插板法应用条件。【解析】根据题意，36块糖内部形成35个空位，分给三个人，需要插两个板子，故有35=595种，而一种分法对应着一组解，如x=1,y=1,z=34,就是一组解。共有595组解。因此，选D。例2、将10本没有区别的图书分到编号为1、2、3的图书馆，要求每个图书馆分得图书数量不小于其编号数，问共有多少种不同的分法?()A.12B.15C.30D.45【分析】根据题意，“1阵没有区别的图书”即相同元素，要求每个图书馆分得图书数量不小于其编号数即1号图书馆至少分1本，2号图书馆至少分两本，