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

1、排列组合问题一一插板法 分组、插空法不相邻、捆绑法相邻插板法m为空的数量【基此题型】有n个一样的兀素，要求分到不同的m组中，且每组至少有一个兀素，冋有多少种分法?Oi_O-_101j 011 01o. . Oi_ o. . o,.n图中“"表示一样的名额，“"表示名额间形成的空隙，设想在这几个空隙中插入六块“挡板"，那么将这10个名额分割成七个局部，将第一、二、三、七个局部所包含的名额数分给第一、二、三七所学校，那么“挡板"的一种插法恰好 对应了 io个名额的一种分配方法，反之，名额的一种分配方法也决定了档板的一种插法，即挡板的插法种数与名额的分配 方法

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

3、至少一个，问有几种情况？问题的题干满足条件12，适用插板法，c9 2=36下面通过几道题目介绍下插板法的应用 e二次插板法 例8 :在一节目单中原有 6个节目，假设保持这些节目相对次序不变，再添加3个节目，共有几种情况？-o - o - o - o - o - o -三个节目abc可以用一个节目去插 7个空位，再用第二个节目去插8个空位，用最后个节目去插 9个空位 所以一共是 c7 1 X c8 1 X c9 1=504种【根本解题思路】将 n个一样的元素排成一行，n个元素之间出现了 n-1个空档，现在我们用m-1个“档板插入n-1丨个空档中，就把n个元素隔成有序的 m份，每个组依次按组序号分

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

5、：有n个一样的元素，要求分到 m组中，问有多少种不同的分法？ 解题思路：这种问题是允许有些组中分到的元素为“0，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上1个，这样所要元素总数就 m个，问题也就是转变成将n+m个元素分到 m组，并且每 组至少分到一个的问题，也就可以用插板法来解决。【例2】有8个一样的球放到三个不同的盒子里，共有种不同方法.A . 35 B . 28 C . 21 D . 45解答：题目允许盒子有空，那么需要每个组添加1个，那么球的总数为8+3X仁11，此题就有C 10, 2=45种分法了，选项 D为正确答案。【基此题型的变形二】题型：有n个一样的元素，要求分到

6、 m组，要求各组中分到的元素至少某个确定 值S s> 1，且每组的s值可以不同，问有多少种不同的分法？解题思路：这种问题是要求组中分到的元 素不能少某个确定值 s，各组分到的不是至少为一个了。对于这样的题，我们就首先将各组都填满，即各组 就填上对应确实定值 s那么多个，这样就满足了题目中要求的最起码的条件，之后我们再分剩下的球。这 样这个问题就转变为上面我们提到的变形一的问题了，我们也就可以用插板法来解决。【例3】15个一样的球放入编号为1、2、3的盒子，盒球数不少于编号数，有几种不同的放法？解析：编号1:至少1个,符合要求。编号2 :至少2个：需预先添加1个球，那么总数-1编号3:至少

7、3个，需预先添加个放进3个盒子里2个，才能满足条件，后面添加一个，那么总数-2那么球总数15-1-2=12112=55【例题有9颗相同的糖/每天至少吃1颗，要4天吃完有名少种吃法宅辭析：氐理同上，具需要同2个板插入到9 粧成的思个内部空駄 轉9菽糖分成4 蛆且毎蛆魏目不少于1即可口因而3个扳互不棚邻，实方法就为【毎功 现有!0个完全相同的篮球全部另给7个班级.毎班至少1个球，问共有舊少 神不同的分法？注释:每组允许有書个元素时也可以用插取法亠苴原理不阖注意下题解;轴区别.【例;將8牛完全相同的球於到3个不同的禽子中Tt有雲少种方法？解枷此題申进有要萃毎个盘子中至少匾一冲球，国此实解址不同孑上面

8、药播槌為 但 仍庖是入2个板，盘庙三俎.怛在分蛆的过程申，允许两块扳之间没有球.其考虑鶴雏为 插入两块刼乱与原来的8个球一共10介无素口所有方进數实际是这10个无素地一个队列， 怛因为球迂间无恙昂h板迂间儘别，所収方进議实际为从io个元素斯占的m个位章甲桃2个佼量就±2个板，实余位置全部换球即可口因此为法数为盂注释：特别注意插板法与捆娜法.插空渗虺别之处在于其元隶是相號口【例题1 一条马路上有輪号为K N 、9的丸盏路灯.现为了节约用电.要将苴中 的三垄关擅但不能同时关掉相邻的两雯或三盏-那么所有不融关灯方法有裟少种？解枷 典绘蚌9盞灯中鉛3蠱憧娈求捅邻药灯不樂芙亂 因此可以屯将羹昊

9、焯韵3 爺灯拿出応 逮禅还飘由蓋灯.现在只孟把准字关闭的M整灯桶入列亮着的5盏灯所弼成的 空腕之间即可口庁養灯的内部友画端共有？个塞，址芳法歎为鼻口【例题】一条马路的两边各立着山盏电虹现在帥了书省用电事决是毎边关掉3黄， 但宵了平安，道瞎起点和终点两边的灯必须星亮的，而且任意一边不首眶续关擅两蓋口问总 找可以有驾少总方案？扎 120B. 320 C> 4J0D. 420霹析：君虑一侧的关灯方法，山盞灯知车M盏还剩7盞卩因注两端的灯不能走 衣 示3爺芙坤的灯只能握在7養灯形咸时首个内部空隙中，衙不命缀在斑诺,故吻法数为CS更【例】10个学生中，男女生各有 5人，选4人参加数学竞赛。1至少有

10、一名女生的选法种数为 。2A、B两人中最多只有一人参加的选法种数为 解法1： 10名中选4名代表的选法的种类：Cio4，排除4名参赛全是男生：C54 排除法Cio4 C54=205解法2 :选1女生时，选2个女生时，选3、4个女生时的选法，分别相加2021年国考真题某单位订阅了 30份学习材料发放给 3个部门，每个部门至少发放 9份材料。问一共有多少种不同的发放方法？ A.7B.9C.10D.12解析：每个部门先放 8个，后面就至少放一个，三个部门那么要先放8X 3=24份，还剩下30-24=6份来放入这三个部门，且每个部门至少发放1份，那么C 5,2=10插空法插空法就是对于解决 某几个元素

11、要求不相邻 的问题时，先将其他元素排好，再将所指定的不相邻的元素插 入它们的间隙或两端位置。首要特点就是不相邻。下面举例说明。一. 数字问题【例】把1，2, 3，4, 5组成没有重复数字 且数字1, 2不相邻的五位数，那么所有不同排法有多少种？解析：此题直接解答较为麻烦，因为可先将3, 4，5三个元素排定，共有种排法，然后再将1, 2插入四个空位共有种排法，故由乘法原理得，所有不同的五位数有二. 节目单问题【例】在一节目单中原有六个节目，假设保持这些节目的相对顺序不变，再添加进去三个节目，那么所有 不同的添加方法共有多少种？解析：-o - o - o - o - o - o -六个节目算上前后

12、共有 七个空位，那么加上的第一个节目那么有种方法；此时有七个节目， 再用第二个节目去插八个空位有种方法；此时有八个节目， 用最后一个节目去插九个空位有种方法。由乘法原理得，所有不同的添加方法为：。三. 关灯问题【例】一条马路上有编号 1 , 2, 3, 4, 5, 6, 7, 8, 9的九盏路灯，为了节约用电，可以把其中的三盏灯关掉，但不能同时关掉相邻两盏或三盏 ，那么所有不同的关灯方法有多少种？解析：如果直接解答须分类讨论，故可把六盏亮着的灯看作六个元素，然后用不亮的三盏灯去插七个空位用不亮的3盏灯去插剩下亮的6盏灯空位，就有7个空位共有种方法，因此所有不同的关灯方法为种。四停车问题【例】停

13、车场划出一排12个停车位置，今有8辆车需要停放，要求空位置连在一起，不同的停车方法有多少 种？解析：先排好8辆车有种方法，要求空位置连在一起剩下4个空位在一起，来插入 8辆车，有9个空位可以插,将空位置插入其中有种方法。所以共有种方法。五座位问题【例】3个人坐在一排8个椅子上，假设 每个人左右两边都有空位 ，那么坐法的种类有多少种？解法：先拿出5个椅子排成一排，在5个椅子中间出现4个空，再让3个人每人带一把椅子去插空，于是有种。【例题】假设有茲味氏K E五亍人排IU,要我比和B两人必须不站在一起那么有实 牛排肚方;费鮮*廿題中要至AB两人不站在一翹,所以可以丸席除AB之夕卜的3个人排威-拣 专

14、注救为g.效器再将虫舸B分対儲兀剑其余3个人排吐所爭成的4个空中,也就黒从4 个空中桃出禹个并出上两个人，具方辻數曲才，邑此患为法数盘疋口1例题"人排成TA.要求甲乙必烦t晦且吕丙不相勿有寥少种方法¥解析1甲乙利邻，可法捆鄴看件一个元索，但这个螫体元索又和丙不村邻，所以死不的F 这个甲乙侯h而餐排剌下尿个人，方法數为疋，然启再将甲乙枸戍的整体无素及丙这两 个元素描心山匕前厅人所彩成的刍个空里，方进歎为用車另外甲乙两个人内部还喬在排序 鑒求为啟選芳进数为兀实丿/【遵习1 $亍男生2仕生排成一排"要求立生不能相邻有囑少种方法？注释：将要求不相邻元素插入排好元索时，要注

15、释是否育猶插入两端位置。【例题假设有入氐匚山E五个人排BA -要求人和B两个人必须不站在一起且A 和另不能站在两谛，那么有塞少排EA方法？解析：原理同前，也是也排好G D E三个人，鶴馬将扱B查到二Ds E所琏成的 两个空 因为瓜B不站厨端，所职只有两个空可选，方进总擞油运总人注释：对于捆綁法和拯空法的区别，可简单记为"相邹冋匹讎不邹问歯證捆绑法r蓿要：所谓捆綁法指在解决对于梵几十元秦a眛相邹的问题时I先整体考虑，将栢邻 元素视诈整悻参与排序然后再单独考虑这个整僭内熬各元素间顺序提0S:其首要特点是*« 苴測§绑法一O®用在不凤枷体的持序问题孔【例题有W

16、本不同的书：苴中数学书4本外语书3本语文书H本.假设将这些书 排成一列放在书架上让数学苹徘在一起，外语吾也恰奸排在一起的排法共首f种。解悅迄是一个排序筒題，书本屯闻是不同竝其申娶配姒学书才#|潘书都售首在一起. 为快連解决这个问题 先将4本裁譬韦亦做个元将M本外评书肃故一元素，鵝席种 剩下药3本语丸书矢5个元索进舒统一排取 方迭歎沟A ,蕊肩排莊一起妁4本戳学书之 间顺痔不同也X曲最后整个持序不亂 所以在4本书内部也需要排序，方辻歎为片*同理， 外语书排序方蛙歎为&明三者尢间是分歩边嗽 战而用乘法虑理得乂彳以【例题3牛人站成T* 要求甲乙两?J粧一起，有多少种方法¥解椅：先瘠

17、申乙廊人看呢1个人，马剩下药3个人一起出妙山芳辻鮫为片，然启申乙 两个人也和匝厚姜篥，方谍数为力二 因此站肌方逸数为片g-【毎口】一台晩会上有6个演唱卒目和4丿灣朝节目,4个舞蹈节且要排在一起，晉爹 啓不同吊商节目颐序*?庄釋:运用捆绑梏时-一定翱主意捆堺起釆的整体內部是否存刃负序的要求有的题目 育J页序的要求有的那么段有口如下面的例题.例题1 6个不同的球邂5个不同酌盒子中，要求毎个禽孑至步放一个恿,一共有枣 少种方法¥ U+fl-s按黑题惫.显奥是2个球敕到異申一个盒芋，另外4林盘叙報劉4个盒孑申， 因此务述是先从6个诛中桃岀2个球作茹一个瞪眸疲列一个蛊子中,然寤这个確休和制下的

18、 4个球4?啡利畝劃5个盒子札 址芳辻嶽是併jC解答：根据题目要求，那么其中一个盒子必须得放 2 个，其他每个盒子放 1个球，所以从 6 个球中挑出 22 5 2 5 个球看成一个整体，那么有 C62 ，这个整体和剩下 4个球放入 5个盒子里，那么有 A55 。方法是 C62 A55排列组合中的解题方法之插板法一、根底理论：插板是一个无形的东西即板子，它不能代表一个元素，它区别于插空法。插板法是用于解决“一样元素分组问题。 判断插板法的题目主要看题干中的两个词语： 一样元素 至少为 1， 如果有这样两个词语一般此题就可以直接插板进展解题。引例说明：春节前单位慰问困难职工，将10份一样的慰问品分

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

20、个板子,表示第1个板子和第 2个板子之间的分给第二名职工,依次类推,因为要分给 6 个人,所以要插 5个板子,第 5个 板子之后的分给第六名职工,所以只要板子固定了,那么每名职工分几份慰问品就固定了。所以 1 0分慰问品中间形成了 9个空;分给 6个人,插入 5个板;共有=1 26种分配方法。注：估计有的同学会问,为什么第一个慰问品之前的位置和最后一个慰问品之后的位置不能放板子。 其实原因在于“每名员工至少分 1 份慰问品,如果在第一个慰问品之前的位置放板子那么第一名职工就 一份分不到了,如果在最后一个慰问品之后的位置放板子那么最后一名职工就一份分不到了。二、真题举例：例1、假设x、y、z是三

21、个非零自然数，且有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 本， 分析完题意之后发现似乎不满足插板法的前提条件