第80炼排列组合的常见模型

1、第 80 炼 排列组合的常见模型一、基础知识：（一）处理排列组合问题的常用思路：1、特殊优先：对于题目中有特殊要求的元素，在考虑步骤时优先安排，然后再去处理无要求的元素。例如：用 0,1,2,3,4 组成无重复数字的五位数，共有多少种排法？解：五位数意味着首位不能是0，所以先处理首位，共有4 种选择，而其余数位没有要求，只需将剩下的元素全排列即可，所以排法总数为N4A4496 种2、寻找对立事件：如果一件事从正面入手，考虑的情况较多，则可以考虑该事的对立面，再用全部可能的总数减去对立面的个数即可。例如：在 10 件产品中，有7 件合格品， 3 件次品。从这10 件产品中任意抽出3 件，至少有一

2、件次品的情况有多少种解：如果从正面考虑，则“至少1 件次品”包含1 件， 2 件， 3 件次品的情况，需要进行分类讨论， 但如果从对立面想，则只需用所有抽取情况减去全是正品的情况即可，列式较为简单。 NC103C7385 （种）3、先取再排 （先分组再排列） ：排列数Anm 是指从n 个元素中取出m 个元素， 再将这m 个元素进行排列。 但有时会出现所需排列的元素并非前一步选出的元素，所以此时就要将过程拆分成两个阶段，可先将所需元素取出，然后再进行排列。例如： 从 4 名男生和3 名女生中选3 人，分别从事 3 项不同的工作， 若这 3 人中只有一名女生，则选派方案有多少种。解：本题由于需要先

3、确定人数的选取，再能进行分配（排列），所以将方案分为两步，第一步：确定选哪些学生，共有C42 C31 种可能，然后将选出的三个人进行排列：A33。所以共有C42 C13 A33108种方案（二）排列组合的常见模型1、捆绑法（整体法） ：当题目中有“相邻元素”时，则可将相邻元素视为一个整体，与其他元素进行排列，然后再考虑相邻元素之间的顺序即可。例如： 5 个人排队，其中甲乙相邻，共有多少种不同的排法解：考虑第一步将甲乙视为一个整体，与其余3 个元素排列，则共有A44 种位置，第二步考虑甲乙自身顺序，有 A22 种位置，所以排法的总数为NA44 A2248种2、插空法：当题目中有“不相邻元素”时，

4、则可考虑用剩余元素“搭台”，不相邻元素进行“插空”，然后再进行各自的排序注：（ 1）要注意在插空的过程中是否可以插在两边（ 2）要从题目中判断是否需要各自排序例如：有 6 名同学排队，其中甲乙不相邻，则共有多少种不同的排法解：考虑剩下四名同学 “搭台”，甲乙不相邻， 则需要从5 个空中选择2 个插入进去， 即有 C52种选择，然后四名同学排序，甲乙排序。所以NC52A44 A22480种3、错位排列：排列好的n 个元素，经过一次再排序后，每个元素都不在原先的位置上，则称为这 n 个元素的一个错位排列。例如对于a,b, c, d ，则 d,c,a, b 是其中一个错位排列。3个元素的错位排列有2

5、 种，4 个元素的错位排列有9 种，5 个元素的错位排列有44 种。以上三种情况可作为结论记住例如：安排 6 个班的班主任监考这六个班，则其中恰好有两个班主任监考自己班的安排总数有多少种？解：第一步先确定那两个班班主任监考自己班，共有C62 种选法，然后剩下4 个班主任均不监考自己班，则为4 个元素的错位排列，共9 种。所以安排总数为NC6291354、依次插空：如果在n 个元素的排列中有m 个元素保持相对位置不变，则可以考虑先将这m 个元素排好位置，再将nm 个元素一个个插入到队伍当中（注意每插入一个元素，下一个元素可选择的空1）例如：已知A,B,C,D, E,F6个人排队，其中A, B,C

6、相对位置不变，则不同的排法有多少种解：考虑先将 A,B,C 排好，则 D 有 4 个空可以选择，D 进入队伍后， E 有 5 个空可以选择，以此类推， F 有 6 种选择，所以方法的总数为N456120种5、不同元素分组：将n 个不同元素放入m 个不同的盒中6、相同元素分组：将n 个相同元素放入m 个不同的盒内，且每盒不空，则不同的方法共有Cnm 11 种。解决此类问题常用的方法是“挡板法” ，因为元素相同，所以只需考虑每个盒子里所含元素个数，则可将这n 个元素排成一列，共有n 1个空，使用 m 1 个“挡板”进入空档处，则可将这 n 个元素划分为 m 个区域，刚好对应那m 个盒子。例如：将

7、6 个相同的小球放入到 4 个不同的盒子里，那么6 个小球5 个空档，选择 3 个位置放“挡板” ，共有C5320 种可能7、涂色问题：涂色的规则是“相邻区域涂不同的颜色”，在处理涂色问题时，可按照选择颜色的总数进行分类讨论，每减少一种颜色的使用，便意味着多出一对不相邻的区域涂相同的颜色（还要注意两两不相邻的情况），先列举出所有不相邻区域搭配的可能，再进行涂色即可。例如：最多使用四种颜色涂图中四个区域，不同的涂色方案有多少种？解：可根据使用颜色的种数进行分类讨论（1）使用 4种颜色，则每个区域涂一种颜色即可：N1 A44（2）使用 3种颜色，则有一对不相邻的区域涂同一种颜色，首先要选择不相邻的

8、区域：用列举法可得：I,IV不相邻所以涂色方案有：N2A43（3）使用 2 种颜色，则无法找到符合条件的情况，所以讨论终止总计 SA44A4348 种二、典型例题：例 1：某电视台邀请了6 位同学的父母共12 人，请 12 位家长中的4 位介绍对子女的教育情况，如果这4 位中恰有一对是夫妻，则不同选择的方法种数有多少思路：本题解决的方案可以是：先挑选出一对夫妻，然后在挑选出两个不是夫妻的即可。第一步：先挑出一对夫妻：C16第二步：在剩下的10 个人中选出两个不是夫妻的，使用间接法：C1025所以选择的方法总数为 N C61 C1025240 （种）答案： 240 种例 2：某教师一天上 3 个

9、班级的课， 每班上 1 节，如果一天共 9 节课，上午 5 节，下午 4 节，并且教师不能连上 3 节课（第 5 节和第 6 节不算连上），那么这位教师一天的课表的所有不同排法有（）A.474种B.77种C.462种D.79种思路：本题如果用直接法考虑，则在安排的过程中还要考虑两节连堂，并且会受到第5,6节课连堂的影响，分类讨论的情形较多，不易求解。如果使用间接法则更为容易。首先在无任何特殊要求下，安排的总数为A93 。不符合要求的情况为上午连上3 节：A43 和下午连上三节：A33 ，所以不同排法的总数为：A93A43A33474 （种）答案：A例 3： 2 位男生和3 位女生共5 位同学站

10、成一排，若男生甲不站两端，3 位女生中有且只有两位女生相邻，则不同排法的种数是（）A.60B.48C.42D.36思路：首先考虑从3 位女生中先选中相邻的两位女生，从而相邻的女生要与另一女生不相邻，则可插空， 让男生搭架子， 因为男生甲不站两端，所以在插空的过程中需有人站在甲的边上，再从剩下的两个空中选一个空插入即可。第一步：从三位女生中选出要相邻的两位女生：C32第二步：两位男生搭出三个空，其中甲的边上要进入女生，另外两个空中要选一个空进女生，所以共有 C12 种选法。第三步：排列男生甲，乙的位置：A22 ，排列相邻女生和单个女生的位置：A22 ，排列相邻女生相互的位置：A22所以共有 NC

11、32 C12 A22 A22 A22 48 种答案： B例 4：某班班会准备从甲，乙等7 名学生中选派4 名学生发言，要求甲，乙两名同学至少有一人参加， 且若甲乙同时参加，则他们发言时不能相邻， 那么不同的发言顺序种数为 （）A. 360B.520C.600D.720思路：因为选人的结果不同会导致安排顺序的不同，所以考虑“先取再排”，分为“甲乙”同时选中和“甲乙只有一人选中”两种情况讨论：若甲乙同时被选中，则只需再从剩下5人中选取 2 人即可： C52 ，在安排顺序时， 甲乙不相邻则 “插空”，所以安排的方式有： A32A22 ，从而第一种情况的总数为：N1C52 A32 A22120（种），

12、若甲乙只有一人选中，则首先先从甲乙中选一人，有C21 ，再从剩下 5 人中选取三人，有C53 ，安排顺序时则无要求，所以第二种情况的总数为：N2C12 C53 A44480 （种），从而总计 600 种答案： C例 5：从单词“ equation ”中选取 5 个不同的字母排成一排，含有“qu”（其中“ qu”相连且顺序不变）的不同排列共有_种思路：从题意上看，解决的策略要分为两步：第一步要先取出元素，因为“qu”必须取出，所以另外 3 个元素需从剩下的6 个元素中取出，即 C63 种，然后在排列时，因为要求“qu”相连，所以采用 “捆绑法”，将 qu 视为一个元素与其它三个元素进行排列：A4

13、4 ，因为“ qu”顺序不变，所以不需要再对qu 进行排列。综上，共有：C63 A44480 种答案： 480例 6：设有编号 1,2,3,4,5 的五个茶杯和编号为1,2,3,4,5 的五个杯盖，将五个杯盖盖在五个茶杯上，至少有两个杯盖和茶杯的编号相同的盖法有（）A. 30种B. 31种C. 32种D. 36种思路： 本题可按照相同编号的个数进行分类讨论，有两个相同时，要先从 5 个里选出哪两个相同，有 C52 种选法，则剩下三个为错位排列，有2 种情况，所以N1C522 ，有三个相同时，同理，剩下两个错位排列只有一种情况（交换位置），所以 N2C53 1，有四个相同时则最后一个也只能相同，

14、所以N3 1，从而 SC52 2C531131（种）答案： B例 7：某人上10 级台阶，他一步可能跨1 级台阶，称为一阶步，也可能跨2 级台阶，称为二阶步； 最多能跨 3 级台阶， 称为三阶步， 若他总共跨了6 步，而且任何相邻两步均不同阶，则此人所有可能的不同过程的种数为（）A.6B.8C.10D.12答案： A思路：首先要确定在这 6 步中，一阶步，二阶步，三阶步各有几步，分别设为x, y, zN ，x4x3x2xyz6则有，解得：y0,y2,y4 ，因为相邻两步不同阶，所以符合x2 y3z10z2z1z0x3要求的只有y2 ，下面开始安排顺序，可以让一阶步搭架子，则二阶步与三阶步必须插

15、z1入一阶步里面的两个空中，所以共有2 种插法， 二阶步与三阶步的前后安排共有3 种（三二二，三二三，二三三） ，所以过程总数为N236答案： A例 8：某旅行社有导游9 人，其中3 人只会英语，2 人只会日语，其余4 人既会英语又会日语，现要从中选6 人，其中 3 人负责英语导游，另外三人负责日语导游，则不同的选择方法有_种思路： 在步骤上可以考虑先选定英语导游， 再选定日语导游。 英语导游的组成可按只会英语的和会双语的人数组成进行分类讨论， 然后再在剩下的人里选出日语导游即可。 第一种情况：没有会双语的人加入英语导游队伍，则英语导游选择数为C33 ，日语导游从剩下6 个人中选择，有C63

16、中，从而N0C33C63 ，第二种情况：有一个会双语的人加入英语导游队伍，从而可得N1C14C32C53 ，依次类推，第三种情况。两个会双语的加入英语导游队伍，则N2C42C13C43 ，第四种情况，英语导游均为会双语的。则N3C43C33 ，综上所述，不同的选择方法总数为SC33C63C41C32C53C 42C31C43C43C33216 ( 种)答案：216 种例 9：如图，用四种不同颜色给图中A, B,C , D , E, F 六个点涂色，要求每个点涂一种颜色，且图中每条线段的两个端点涂不同颜色，则不同的涂色方法有（）A.288 种B.264 种C.240 种D.168 种思路：如果用

17、四种颜色涂六个点，则需要有两对不相邻的点涂相同的颜色。所以考虑列举出不相邻的两对点。列举的情况如下：A,CB, D，A, CB, E， A,CD, F，A,F B,D ，A, FB, E，A, FC, E， B,DC, E，B,E D,F ，C, ED, F共九组，所以涂色方法共有9 A44216如果用三种颜色涂六个点，则需要有三对不相邻的点涂相同的颜色，列举情况如下：A,CB, ED, F，A, FC, EB, D 共两组，所以涂色方法共有2A4348综上所述，总计264 种答案：B例 10：有8 张卡片分别标有数字1,2,3,4,5,6,7,8，从中取出6 张卡片排成3 行2 列，要求3 行中仅有中间行的两张卡片上的数字之和为5，则不同的排法共有（）A. 1344种B. 1248种C. 1056种D. 960种思路：中间行数字和为5 只有两种情况，即1,4 和 2,3 ，但这两组不能同时占据两行，若按题意思考，以1,4 占中间行为例，则在安排时既要考虑另一组2,3 是否同时被选中，还要考虑同时被选中时不能呆在同一行，情况比较复杂。 所以考虑间接法，先求出中间和为5 的所有情况，再减去两行和为5 的情形解：先考虑中间和为5 的所有情况：第一步：先将中间行放入