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

1、精品文档，欢迎下载1 / 10插板法（m 为空的数量）【基本题型】有 n 个相同的元素，要求分到不中，且每组至少有一个元素，问有多少种分法?OL_IOI_ I OII OI_ I OL101_ I OII OI_ I O 11 O图中“ ”表示相同的名额，“”表示名额间形成的空隙，设想在这几个空隙中插入六块“挡板”，则将这 10 个名额分割成七个部分，将第一、二、三、七个部分所包含的名额数分给第一、二、三七所学校，则“挡板”的一种插法恰好对 应了 10 个名额的一种分配方法，反之，名额的一种分配方法也决定了档板的一种插法，即挡板的插法种数与名额的分配方 法种数是相等的，【总结】需满足条件：n

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

3、3 个不同的箱子，每个箱子至少一个，问有几种情况？问题的题干满足条件（1） （2）,适用插板法,c9 2=36下面通过几道题目介绍下插板法的应用e 二次插板法例 8 :在一张节目单中原有6 个节目，若保持这些节目相对次序不变，再添加 3 个节目,共有几种情况？-0 - o - o - o - o - o -二个节目 abc可以用一个节目去插 7 个空位，再用第二个节目去插8 个空位，用最后个节目去插 9 个空位所以一共是 C7 1 乞 8 1Xc9 仁 504 种【基本解题思路】将 n 个相同的元素排成一行，n 个元素之间出现了（ n-1）个空档，现在我们用（m-1 ）个档板”插入（n-1）

4、个空档中，就把 n 个元素隔成有序的 m 份，每个组依次按组序号分到对应位置的几个元素（可能是1 个、2个、3 个、4 个、.），这样不同的插入办法就对应着n 个相同的元素分到 m 组的一种分法，这种借助于这排列组合问题插板法 份组）、插空法（不相邻）、捆绑法（相邻）精品文档，欢迎下载2 / 10样的虚拟 档板”分配元素的方法称之为插板法。【基本题型例题】【例 1】 共有 10 完全相同的球分到 7 个班里，每个班至少要分到一个球，问有几种不同分法？解析：我们可以将 10 个相同的球排成一行，10 个球之间出现了 9 个空隙，现在我们用 6 个档板”插入这 9 个空隙中，就 把 10 个球隔成

5、有序的 7 份，每个班级依次按班级序号分到对应位置的几个球（可能是1 个、2 个、3 个、4 个），这样，借助于虚拟 档板”就可以把 10 个球分到了 7 个班中。【基本题型的变形（一）】题型：有 n 个相同的元素，要求分到 m 组中，问有多少种不同的分法?解题思路：这种问题是允许有些组中分到的元素为0”,也就是组中可以为空的。对于这样的题，我们就首先将每组都填上 1 个，这样所要元素总数就 m 个，问题也就是转变成将（n+m ）个元素分到 m 组，并且每 组至少分到一个的问题，也就可以用插板法来解决。【例 2】有 8 个相同的球放到三个不同的盒子里，共有（）种不同方法A. 35 B. 28

6、C. 21 D . 45解答：题目允许盒子有空，则需要每个组添加1 个，则球的总数为 8+3X仁 11，此题就有 C （10, 2） =45（种）分法了，选项 D 为正确答案。【基本题型的变形（二）】题型：有 n 个相同的元素，要求分到 m 组，要求各组中分到的元素至少某个确定值S（s 1，且每组的 s 值可以不同），问有多少种不同的分法？解题思路：这种问题是要求组中分到的元素不能少某个确定值s,各组分到的不是至少为一个了。对于这样的题，我们就首先将各组都填满， 即各组就填上对应的确定值 s 那么多个，这样就满足了题目中要求的最起 码的条件，之后我们再分剩下的球。这样这个问题就转变为上面我们提

7、到的变形（一）的问题了，我们也 就可以用插板法来解决。【例 3】15 个相同的球放入编号为 1、2、3 的盒子内，盒内球数不少于编号数，有几种不同的放法？ 解析：编号 1:至少 1 个，符合要求。编号 2:至少 2 个：需预先添加 1 个球，则总数-1编号 3:至少 3 个，需预先添加 2 个，才能满足条件，后面添加一个，则总数 -2 则球总数 15-1-2=12 个放进 3 个盒子里所以 C （11，2） =55 （种）【例题有 9 颗相同的韬,毎天至少吃 1 颗，要 4 天吃禿“有多少种吃法 2 解朴 感理同上，只需要用 3 个扳描入型炭的&个内部空隙，将 9 穎總分成 4 蛆且岳

8、蛆数目不少于 1 即可因而？个板互不捆峯 其方法救为C；B【球习现有 10 个完全相同的篮球全部幻给 7 个班级,每班至少 1 个球“问共有哆少 种不同的分法？注釋：毎爼允许有零个元素时也可以用插愎法.直原理不同上注意下题解;堀匡别0精品文档，欢迎下载3 / 10【例题 1 将 8 个完全相同的球放到 3 个不同的盒子中、一共有多少种方诜？解析：此題中没有要求粵个金子中至少放一勺球，因此并舞诀不同于上面的插板法，怛 仍旧是插入 2 个扳，分成三如。但在分址的过程中，允许两块植之间没有球口其盘虑思維为 播入两块板后，与瘟来的 8 个球一块 10 个无素所有方法数卖际是这 10 个无索的一个队捌，

9、 但因为球乏间无董别，板之间儘别，所以芳辻敦实际为从 i0 个无素所占的 10 个偉蓋中桃 2 个位査就上 2 个板，实余险蚩全部放球即可。因此方辻数为盂 备 9 的九葢路灯， 现为了节约用电要将苴中 的三盏关捧，但不能同时关毎相邻的两盏或三多则所有不融关灯方法有多少种 7辭析：姜羌棹 9 盏灯中的 3 盏，但要求捆邻的灯不能关 HU 因此可以先将要关椁的 3 養灯拿出来，这样还剩竹盞灯，现衣只需把准备羌诃的 3 養灯插入劃亮着的 6 蓋灯所珊成的 空隙之间即可 6鑒灯的内部及两蠕共有了个空，故为进救为【例题】一条马路的两边各立着 10 盏电灯，现在为了节省用电，决定毎边关撞 3 盏， 但为了

10、安全/道路起点和终点两边的灯必须是亮的而且任意一边不自誌续关掉两盏.问总 共可以有多少总方案号A 120B. 320 C. 4)0Ek 420解析；考虑一侧的羌灯方為 W 盍灯关掉 3 盞，还剩 7 蠢，因为囲瑞的灯不能黄,表 乐 3 整羌掉的灯只能据忘 7 整灯形戍的6个内部空辔申，而不能放在两端,故方法數为 C,【例】10 个学生中，男女生各有 5 人，选 4 人参加数学竞赛。(1 )至少有一名女生的选法种数为 _。(2)A、B 两人中最多只有一人参加的选法种数为 _解法 1：10 名中选 4 名代表的选法的种类：Cio4,排除 4 名参赛全是男生：C4(排除法)Cio4 -C54=205

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

12、相邻。下面举例说明。一.数字问题【例】 把 1, 2, 3，4, 5 组成没有重复数字 且数字 1, 2 不相邻的五位数，则所有不同排法有多少种？3, 4，5 三个元素排定，共有丄 种排法，然后再将 1，2 插入四个空位共有凡种排法，故由乘法原理得，所有不同的五位数有二.节目单问题【例】在一张节目单中原有六个节目，若保持这些节目的相对顺序不变，再添加进去三个节目，则所有不同的添加方法共有多少种？解析：-0 - o - o - o - o - o -六个节目算上前后共有七个空位，那么加上的第一个节目则有 种方法；此时有七个节目，再用第二个节目去插八个空位有二种方法；此时有八个节目，用最后一个节目

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

14、空位置插入其中有 cJ 种方法。所以共有兰种方法。五.座位问题【例】3 个人坐在一排 8 个椅子上，若 每个人左右两边都有空位，则坐法的种类有多少种？解法：先拿出 5 个椅子排成一排，在 5 个椅子中间出现 4 个空，再让 3 个人每人带一把椅子去插空，于是有 打 V 种。解析：本题直接解答较为麻烦，因为可先将（用不亮的 3盏灯去插剩下亮的6 盏灯空位，就有7 个空位）共种方法，因此所有不同的关灯方法为种。四停车问题精品文档，欢迎下载5 / 10【例题】若有虹乩 C-. Ik E 五个人排 IU，要求 A 和 B 两个人必须不站在一起“则有哆 少排队方:去？解析晝題申娶求 AB 两人不池总一起

15、，斯以可馭先将除 A 和 B 更外的 3 个人排成一挑 方法数为然賠再将 A 和 E 分别斂到莫余 3 个人排队斯形成的 4 个空札 也就是从却 个空中桃出两个并排上两个人，英方法数为才，因此迫方法歎用才【例题8 个人排成 HR.要求甲乙必须*胡 I 且与丙不木瞬有多少种方法？解析：甲乙相朋 可以据鄴看作一个元素，但这个整体元素久和向不和邻，所以先不排 达个甲乙丙,而是排剩下的 5 个人，方法救为加，然治再将甲乙枸成的螫体无索及丙这两 个无素柿入到此前T 人所形成的右个空里， 方珪数为/,另外甲乙两个人內部还存在排序 要求为崔o 畋 3进数为AA；A -【憑习 1 5 个男生 3 仕生排成一排

16、 要求玄生不能相邻.有多少种方袪？注释：将要求不相邻元素插入排好无素时，要注釋是否直掰插入两端位置.【例题 1 若有治B、C. R E 五个人排甌要求 A 和 B 两个人必须不站在丄且丸 和 B 不能站在两端,则有多少排臥方法？解析 1 原理同前，也是先排城 G D E 三个人然忌将人 B 查列 GDHE 所彫成的 两个空甲，因为九 E 不济两端，所収只有两个空可逸,方滦迫数为卫注释：对于捆绑法和插空法的区别可简单记为“相邹冋理莽法不邻冋裁召沬先精品文档，欢迎下载6 / 10精要：所谓拥绑法.指在辭决对于某几个元康要求相邹的问题时,先整転虑，将相邻 元素视作一整体参与排序，然后再单独考虑这个整

17、体内部各元素间顺序.提醒：苴首要特点是桶 4 其次捆綁法一股都应用在不同躺的器序问题中柯【例题有10本不同的书：苴中数学书4本*外语书3本语文书3本口若将这些书 排成一列放在书架上让数学书排在一起 外语书也恰好排在一起的排法共有（）种。解析:这是一个排序间錢，书本之间是不同锹实申要求数学卒和外语韦都备自在一起. 为快速解决这个问廳先将4本数学书看做一个元讀，将？本外语书请做一个元素，感后和 剌下药2本语文书拱5个兄啜进幷坑 T#序，方蛙歎为兀，然后排在一起餉4本数学书之 间顺序不同也对应暈后螫个排序不同，所以在4本书內部也需要捋序，方法数为片，同理， 外语丰排序方法数为ga而三署之间灵好步过程

18、故而用乘法原理得AXA-【例题1 5个人站成 T要求甲乙两人站在一起，有多少种方法g解析：先将甲乙两人看戍1个人，再剩下的3个人一起排列，方进数为片，然冶申乙 两个人也有顺序要求，为蛙載为因此站炫法歎为火耳。【海习】一台晩会上有百个濾唱节目和4-ms节目，4个舞蹈节目要排在一起# 少不同的轴*节目的顺序？注释：运用捆绑法时，1 定要注意1S绑起来極体內部是否存在顺序的要求有的题目 肓顺序的要求 育的则没有.如下面的例题-【例题6个不同的球放到5个不同的當子中，要求毎个盘子至少放一个球* 一共有容 少种方法解析：榜蹩蹇懣，显慈是2个球放劉其中一个食子，另外4个球分别放割4个盒孑中， 因此方辻刘I

19、从6个嫌中桃出2个球作为亠个整体放別一个蠹子申,魅常送个螫俸春剩下的4个球分昂甘非列换劃5个金子申,故为法数是CAr.解答：根据题目要求， 则其中一个盒子必须得放 2 个，其他每个盒子放 1 个球，所以从 6 个球中挑出 2 个球2525看成一个整体，则有C6,这个整体和剩下 4 个球放入 5 个盒子里，则有A5。方法是C6A排列组合中的解题方法之插板法一、基础理论：插板是一个无形的东西即板子，它不能代表一个元素，它区别于插空法。插板法是用于解决相同元素”分组问题。判断插板法的题目主要看题干中的两个词语：相同元素至少为 1，如果有这样两个词语一般此题就可以直接插板进行解题。引例说明：春节前单位

20、慰问困难职工，将10 份相同的慰问品分给 6 名职工，每名职工至少要分得1 份慰问品，分配方法共有：A.84 种 B.126 种 C.210 种 D.252 种【分析】此题第一眼给人的感觉是能用列举法进行分类解题，但是细一思考分类的情况太多了，不易计算，因为想用插板法解题一般是分两类或三类。而插板法就可以使这种为题迎刃而解。利用无形的板子把其分割开来。【解析】10 份慰问品相同且每人至少得1 份”，满足插板法的两个前提相同元素至少为1,故可直接使用插板法。将 10 份慰问品依次排成一条直线，我们用插板的形式把慰问品分给6 名职工，中间形成 9个空，插上第 1 个板子，则第一个板子之前的分给第一

21、名职工，在后面又插了一个板子，表示第1 个板子和第 2 个板子之间的分给第二名职工，依次类推，因为要分给 6 个人，所以要插 5 个板子，第 5 个板子之后的分给第六名职工，所以只要板子固定了，那么每名职工分几份慰问品就固定了。所以 10 分慰问品中间形成了 9 个空;分给 6 个人，插入 5 个板共有丫:=126 种分配方法。精品文档，欢迎下载7 / 10精品文档，欢迎下载9 / 10注：估计有的同学会问，为什么第一个慰问品之前的位置和最后一个慰问品之后的位置不能放板子。其实原因在于每名员工至少分 1 份慰问品”如果在第一个慰问品之前的位置放板子那么第一名职工就一份 分不到了，如果在最后一个

22、慰问品之后的位置放板子那么最后一名职工就一份分不到了。二、 真题举例：例 1、假设 X、y、z 是三个非零自然数，且有x+y+z=36，则共有多少组满足条件的解？A.700B.665C.630D.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.15C.30D.45【分析】根据题意，10 本没有区别的图书”即相同元素，要求每个图书馆分得图书数量不小于其编号数即 1 号图书馆至少分 1 本，2 号图书馆至少分两本，3 号图书馆至少分 3 本，分析完题意之后发现似乎不满足插板法的前提条件至少为1，类似的这种题目我们只需要适当变形就可利用插