问题38复杂的排列组合问题
一、考情分析
高考对这部分的要求还是比较高的.考查两个计数原理、排列、组合在解决实际问题上的应用.值得提醒地是：计数模型不一定是排列或组合.画一画,数一数,算一算,是基本的计数方法,不可废弃.
二、经验分享
1.排列应用问题的分类与解法
(1)对于有限制条件的排列问题，分析问题时有位置分析法、元素分析法，在实际进行排列时一般采用特殊元素优先原则，即先安排有限制条件的元素或有限制条件的位置，对于分类过多的问题可以采用间接法．
(2)对相邻问题采用捆绑法、不相邻问题采用插空法、定序问题采用倍缩法是解决有限制条件的排列问题的常用方法.
2.组合问题常有以下两类题型变化
(1)“含有”或“不含有”某些元素的组合题型：“含”，则先将这些元素取出，再由另外元素补足；“不含”，则先将这些元素剔除，再从剩下的元素中去选取．
(2)“至少”或“至多”含有几个元素的组合题型：解这类题必须十分重视“至少”与“至多”这两个关键词的含义，谨防重复与漏解．用直接法和间接法都可以求解，通常用直接法分类复杂时，考虑逆向思维，用间接法处理．
3.排列与组合综合问题的常见类型及解题策略
(1)相邻问题捆绑法．在特定条件下，将几个相关元素视为一个元素来考虑，待整个问题排好之后，再考虑它们“内部”的排列．
(2)相间问题插空法．先把一般元素排好，然后把特定元素插在它们之间或两端的空当中，它与捆绑法有同等作用．
(3)特殊元素(位置)优先安排法．优先考虑问题中的特殊元素或位置，然后再排列其他一般元素或位置．
(4)多元问题分类法．将符合条件的排列分为几类，而每一类的排列数较易求出，然后根据分类加法计数原理求出排列总数．
三、知识拓展
1.分类标准是运用分类加法计数原理的难点所在，重点在于抓住题目中的关键词或关键元素、关键位置．首先根据题目特点恰当选择一个分类标准；其次分类时应注意完成这件事情的任何一种方法必须属于某一类．
2.利用分步乘法计数原理解决问题要按事件发生的过程合理分步，即分步是有先后顺序的，并且分步必须满足：完成一件事的各个步骤是相互依存的，只有各个步骤都完成了，才算完成这件事．分步必须满足两个条件：一是步骤互相独立，互不干扰；二是步与步确保连续，逐步完成．
3.解排列、组合问题的基本原则：特殊优先，先分组再分解，先取后排；较复杂问题可采用间接法，转化为求它的对立事件．
4.解决排列组合综合性问题的一般过程如下:
1.认真审题弄清要做什么事
2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类.
3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素.
解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略
解排列（或）组合问题,应按元素的性质进行分类,分类标准明确,不重不漏；按事情的发生的连续过程分步,做到分步层次清楚.
四、题型分析
(一)“相邻”与“不相邻”问题
【例1】甲、乙、丙、丁四名同学排成一排,分别计算满足下列条件的排法种数：
（1）甲不在排头、乙不在排尾；
（2）甲不在第一位、乙不在第二位、丙不在第三位、丁不在第四位；
（3）甲一定在乙的右端(可以不相邻)．
【解析】（1）①直接排,要分甲排在排尾和甲既不排在排头也不排在排尾两种情况．
若甲排在排尾共有AA＝6种排法．
若甲既不在排头也不在排尾共有AAA＝8种排法,由分类计数原理知满足条件的排法共有AA＋AAA＝14(种)．
②也可间接计算：A－2A＋A＝14(种)．
（2）可考虑直接排法：甲有3种排法；若甲排在第二位,则乙有3种排法；甲、乙排好后,丙、丁只有一种排法,由分步计数原理知满足条件的所有排法共有3×3×1＝9(种)．
（3）可先排丙、丁有A种排法,则甲、乙只有一种排法,由分步计数原理满足条件的排列共有A·1＝12(种),或看作定序问题＝12(种)．
【点评】对于相邻问题,可以先将要求相邻的元素作为一个元素与其他元素进行排列,同时要考虑相邻元素的内部是否需要排列,这种方法称为“捆绑法”；对于不相邻的元素,可先排其他元素,然后将这些要求不相邻的元素插入空当,这种方法称为“插空法”；对于“在”或者“不在”的排列问题的计算方法主要有：位置优先法、元素优先法、间接计算法．
【小试牛刀】【广东省汕头市2019届高三上学期期末】把分别写有1，2，3，4，5的五张卡片全部分给甲、乙、丙三个人，每人至少一张，且若分得的卡片超过一张，则必须是连号，那么不同的分法种数为______用数字作答．
【答案】36
【解析】先将卡分为符合条件的3份，由题意，3人分5张卡，且每人至少一张，至多三张，若分得的卡片超过一张，则必须是连号，相当于将1、2、3、4、5这4个数用2个板子隔开，在4个空位插2个板子，共有种情况，再对应到3个人，有种情况，则共有种情况．故答案为：36
(二)涂色问题
【例2】如图,用4种不同的颜色对图中5个区域涂色(4种颜色全部使用),要求每个区域涂一种颜色,相邻的区域不能涂相同的颜色,则不同的涂色种数有________.
【分析】由于区域1,2,3与区域4相邻,由条件宜采用分步处理,又相邻区域不同色,因此应按区域1和区域3是否同色分类求解．
【解析】按区域1与3是否同色分类；
(1)区域1与3同色；先涂区域1与3有4种方法,再涂区域2,4,5(还有3种颜色)有A种方法．
∴区域1与3涂同色,共有4A＝24种方法．
(2)区域1与3不同色：先涂区域1与3有A种方法,第二步涂区域2有2种涂色方法,第三步涂区域4只有一种方法,第四步涂区域5有3种方法．
∴这时共有A×2×1×3＝72种方法,
故由分类加法计数原理,不同的涂色种数为24＋72＝96.
【点评】（1）解决涂色问题,一定要分清所给的颜色是否用完,并选择恰当的涂色顺序．
（2）切实选择好分类标准,分清哪些可以同色,哪些不同色．
【小试牛刀】【安徽省淮南市2019届高三第一次模拟】如图为我国数学家赵爽约3世纪初在为《周髀算经》作注时验证勾股定理的示意图，现在提供5种颜色给其中5个小区域涂色，规定每个区域只涂一种颜色，相邻区域颜色不同，则区域涂色不相同的概率为
A． B． C． D．
【答案】B
【解析】
提供5种颜色给其中5个小区域涂色，规定每个区域只涂一种颜色，相邻区域颜色不同，
根据题意，如图，设5个区域依次为,分4步进行分析：
，对于区域，有5种颜色可选；
，对于区域与区域相邻，有4种颜色可选；
，对于区域，与区域相邻，有3种颜色可选；
，对于区域，若与颜色相同，区域有3种颜色可选，
若与颜色不相同，区域有2种颜色可选，区域有2种颜色可选，
则区域有种选择，
则不同的涂色方案有种，
其中，区域涂色不相同的情况有：
，对于区域，有5种颜色可选；
，对于区域与区域相邻，有4种颜色可选；
，对于区域与区域相邻，有2种颜色可选；
，对于区域，若与颜色相同，区域有2种颜色可选，
若与颜色不相同，区域有1种颜色可选，区域有1种颜色可选，
则区域有种选择，
不同的涂色方案有种，
区域涂色不相同的概率为 ,故选B．
(三)分配问题
【例3】有6本不同的书按下列分配方式分配,问共有多少种不同的分配方式？
（1）分成每组都是2本的三组；
（2）分给甲、乙、丙三人,每人2本．
【分析】（1）组合知识及分步计数原理求解；（2）均匀分组问题.
【解析】（1）先分三步,则应是CCC种选法,但是这里面出现了重复,不妨记6本书为分别A、B、C、D、E、F,若第一步取了(AB、CD、EF),则CCC种分法中还有(AB、EF、CD),(CD、AB、EF)、(CD、EF、AB)、(EF、CD、AB)、(EF、AB、CD)共有A种情况,而且这A种情况仅是AB、CD、EF的顺序不同,因此,只算作一种情况,故分配方式有＝15(种)．
（2）在问题（1）的基础上再分配,故分配方式有·A＝CCC＝90(种)．
【点评】不同元素的分配问题,往往是先分组再分配．在分组时,通常有三种类型：①不均匀分组；②均匀分组；③部分均匀分组,注意各种分组类型中,不同分组方法的求法．
【小试牛刀】把四件玩具分给三个小朋友,每位小朋友至少分到一件玩具,且两件玩具不能分给同一个人,则不同的分法有（ ）
A．36种 B．30种 C．24种 D．18种
【答案】B
【解析】分两步进行分析:先计算把四件玩具分给三个小朋友,每位小朋友至少分到一件玩具的分法数目:首先将件玩具分成组,其中组有件,剩余组各件,有种分组方法,再将这组对应三个小朋友,有种方法,则有种情况；计算两件玩具分给同一个人的分法数目,若两件玩具分给同一个人,则剩余的件玩具分给其他人,有种情况.综上可得,两件玩具不能分给同一个人的不同分法有种,故选B.
(四)排数问题
【例4】在某种信息传输过程中,用四个数字的一个排列（数字允许重复）表示以一个信息,不提排列表示不同信息. 若所有数字只有0,1,则与信息0110之多由四个相对应位置上数字相同的信息个数为（ ）
A. 9 B.10 C.11 D. 12
【分析】信息0110是四个数字,此类“至多”、“至少”类型的问题,可以直接利用分类讨论求解,也可以转化为反面的问题,利用间接法求解.
【解析一】（直接法）若0相同,只有1个；若1相同,共有个；若2相同,共有个,故共有个.
【解析二】（间接法）若3个数字相同,共有个,若4个数字相同共4个,二不同排列个数为个,所以共有个.
【点评】该题中要求的是“至多”有两个位置上数字相同,易出现的问题是分类混淆,漏掉各位数字信息均不同的情况,解决此类问题的关键是准确确定分类标准,分类计数时要做到不重不漏.
【小试牛刀】用数字0,1,2,3,4,5组成没有重复数字的五位数,其中比40000大的偶数共有（ ）
A．144个 B．120个 C．96个 D．72个
【答案】B
【解析】据题意,万位上只能排4、5．若万位上排4,则有个；若万位上排5,则有个．所以共有个．选B．
(五)摸球问题
【例5】【浙江温州市十校联合体2014届高三上学期期初联考】将四个相同的红球和四个相同的黑球排成一排,然后从左至右依次给它们赋以编号l,2,…,8.则红球的编号之和小于黑球编号之和的排法有 种.
【分析】注意到4个相同的红球没有区别,4个相同的黑球也没有区别,先求出任意排放的排法,编号相等的结果必有四组,其中每组一黑球一白球的编号和为9,则有,,,四种,红黑互换编号就有8种,因为红球的编号之和小于黑球编号之和的排法和大于的排法一样,则红球的编号之和小于黑球编号之和的排法有种.
【解析】依题意,任意排放的排法,红球编号与黑球编号相等的情况有,,,四种,红黑互换编号就是8种,所以红球的编号之和小于黑球编号之和的排法有种.
【点评】要搞清组合与排列的区别与联系：组合与顺序无关,排列与顺序有关；排列可以分成先选取(组合)后排列两个步骤进行．
【小试牛刀】四个不同的小球放入编号为1,2,3的三个盒子中,则恰有一个空盒的放法共有 种（用数字作答）．
【答案】42
【解析】根据题意,分2步进行分析,
①、先在编号为1,2,3的三个盒子中,取出2个盒子,有种取法,
②、将4个小球放进取出的2个盒子中,每个小球有2种放法,则4个小球一共有2×2×2×2=24种,
其中有1个空盒,即4个小球都放进其中1个盒子的情况有2种；
则将4个小球放进取出的2个盒子中,且不能有空盒,其放法数目为（24﹣2）=14种,
故四个不同的小球放入编号为1,2,3的三个盒子中,则恰有一个空盒的放法为3×14=42种；
故答案为：42．
(六)“至多”、“至少”问题
【例6】某医院有内科医生12名,外科医生8名,现选派5名参加赈灾医疗队,其中
（1）甲、乙两人至少有一人参加,有多少种选法？
（2）队中至少有一名内科医生和一名外科医生,有几种选法？
【分析】“无序问题”用组合,注意分类处理．
【解析】（1）分两类：甲、乙中有一人参加,甲、乙都参加,共有CC＋C＝6 936(种)；
（2）方法一(直接法)：至少有一名内科医生和一名外科医生的选法可分四类：一内四外；二内三外；三内二外；四内一外,所以共有CC＋CC＋CC＋CC＝14 656(种)．
方法二(间接法)：由总数中减去五名都是内科医生和五名都是外科医生的选法种数,得C－(C＋C)＝14 656(种)．
【点评】 对于有条件的组合问题,可能遇到含某个(些)元素与不含某个(些)元素问题；也可能遇到“至多”或“至少”等组合问题的计算,此类问题要注意分类处理或间接计算,切记不要因为“先取再后取”产生顺序造成计算错误．选择恰当分类标准,避免重复遗漏,出现“至少、至多”型问题,注意间接法的运用．
【小试牛刀】西部某县委将位大学生志愿者(男女) 分成两组, 分配到两所小学支教, 若要求女生不能单独成组, 且每组最多人, 则不同的分配方案共有（ ）
A．种 B．种 C．种 D．种
【答案】C
【解析】分组的方案有3、4和2、5两类,第一类有种;第二类有种,所以共有N=68+36=104种不同的方案.
(七)信息迁移题
【例7】回文数是指从左到右与从右到左读都一样的正整数．如22,121,3 443,94 249等．显然2位回文数有9个：11,22,33,…,99.3位回文数有90个：101,111,121,…,191,202,…,999.(*)
则：（1）4位回文数有________个；（2）2n＋1(n∈N*)位回文数有________个．(**)
【分析】由(*)式,理解“特殊”背景——回文数的含义,借助计数原理计算．
结合(**),可从2位回文数,3位回文数,4位回文数探索求解方法,从特殊到一般发现规律．
【解析】（1）4位回文数相当于填4个方格,首尾相同,且不为0,共9种填法；中间两位一样,有10种填法．共计9×10＝90(种)填法,即4位回文数有90个．
（2）根据回文数的定义,此问题也可以转化成填方格．由计数原理,共有9×10n种填空．
【点评】 （1）一题两问,以“回文数”为新背景,考查计数原理,体现了化归思想,将确定回文数的问题转化为“填方格”问题,进而利用分步乘法计数原理解决,将新信息转化为所学的数学知识来解决．
（2）从特殊情形入手,通过分析、归纳,发现问题中隐含的一些本质特征和规律,然后再推广到一般情形,必要时可以多列举一些特殊情形,使规律方法更加明确．
【小试牛刀】回文数是指从左到右读与从右到左读都一样的正整数,如2,11,242,6776,83238等,设位回文数个数为（为正整数）,如11是2位回文数,则下列说法正确的是（ ）
A. B. C. D.以上说法都不正确
【答案】B.
【解析】A：,故A错误；根据对称性可知,,故B正确,C,错误,故选
B.
四、迁移运用
1．【江西省临川第一中学等九校2019届高三3月联考】已知三棱锥的6条棱代表6种不同的化工产品，有公共顶点的两条棱代表的化工产品放在同一仓库是安全的，没有公共顶点的两条棱代表的化工产品放在同一仓库是危险的。现用编号为1，2，3的三个仓库存放这6种化工产品，每个仓库放2种，那么安全存放的不同方法种数为（ ）
A．12 B．24 C．36 D．48
【答案】D
【解析】设种产品分别为，画出图像如下图所示，根据题意，安全的分组方法有，，，，共种，每一种分组方法安排到个仓库，有种方法，故总的方法种数有种，故选D.
2．【东北三省三校2019届高三第一次模拟】中国有十二生肖，又叫十二属相，每一个人的出生年份对应了十二种动物（鼠、牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪）中的一种，现有十二生肖的吉祥物各一个，三位同学依次选一个作为礼物，甲同学喜欢牛和马，乙同学喜欢牛、狗和羊，丙同学哪个吉祥物都喜欢，如果让三位同学选取礼物都满意，则选法有（ ）
A．30种 B．50种 C．60种 D．90种
【答案】B
【解析】若同学甲选牛，那么同学乙只能选狗和羊中的一种，丙同学可以从剩下的10中任意选，所以共有
若同学甲选马，那么同学乙能选牛、狗和羊中的一种，丙同学可以从剩下的10中任意选，所以共有
所以共有种，故选B
3．【福建省龙岩市2019届高三下学期教学质量检查】已知数列各项均为整数，共有7项，且满足,，其中，(为常数且)．若满足上述条件的不同数列个数共有15个，则的值为（ ）
A．1 B．3 C．5 D．7
【答案】B
【解析】∵，
∴＝1或＝﹣1
设有x个1，则有6x个﹣1
∴﹣＝（﹣）+（﹣）+…+（﹣）
∴＝x+（6﹣x）•（﹣1）
∴x＝
∴这样的数列个数有,
解得x＝2或4，
∴或
故选：B．
4．【江西省重点中学盟校2019届高三第一次联考】今有个人组成的旅游团,包括4个大人，2个小孩，去庐山旅游，准备同时乘缆车观光，现有三辆不同的缆车可供选择，每辆缆车最多可乘3人，为了安全起见，小孩乘缆车必须要大人陪同，则不同的乘车方式有( )种
A． B． C． D．
【答案】C
【解析】第一类：只用两辆缆车，
若两个小孩坐在一块，则有种乘车方式；
若两个小孩不坐在一块，则有种乘车方式；
第二类：用三辆缆车，
若两个小孩坐在一块，则有种乘车方式；
若两个小孩不坐在一块，则有种乘车方式；
综上不同的乘车方式有种.
故选C
5．【安徽省合肥一中等六校教育研究会2019届高三第二次联考】某地举办科技博览会，有个场馆，现将个志愿者名额分配给这个场馆，要求每个场馆至少有一个名额且各场馆名额互不相同的分配方法共有（ ）种
A． B． C． D．
【答案】A
【解析】每个场馆至少有一个名额的分法为种，
至少有两个场馆的名额相同的分配方法有
（1，1，22），（2,2,20），（3,3,18），（4,4,16），（5,5,14），（6,6,12），（7,7,10），（8,8,8），（9,9,6），（10,10,4），（11,11,2），
再对场馆分配，共有种，
所以每个场馆至少有一个名额且各校名额互不相同的分配方法共有种，
故选A.
6．【河南省焦作市2019届高三上学期期中】已知一个三位数的百位数字为x，十位数字为y，个位数字为z，若此三位数与37（x+y+z）的大小相同，则这样的三位数有（ ）
A．14个 B．15个 C．16个 D．17个
【答案】B
【解析】由题意可得100x+10y+z＝37（x+y+z），即7x＝3y+4z，
故4（x﹣z）＝3（y﹣z），当x＝y＝z时，这样的三位数有9个，
当时，y﹣z＝7，
故，
当，,
故满足条件的三位数有15个，故选：B．
7.【湖南省长沙市雅礼中学、河南省实验中学2018届高三联考】郑州绿博园花展期间，安排6位志愿者到4个展区提供服务，要求甲、乙两个展区各安排一个人，剩下两个展区各安排两个人，其中的小李和小王不在一起，不同的安排方案共有（ ）
A. 168种 B. 156种 C. 172种 D. 180种
【答案】B
【解析】分类：（1）小李和小王去甲、乙，共种（2）小王，小李一人去甲、乙，共种，（3）小王，小李均没有去甲、乙，共种，总共N种，选B.
8．【四川省资阳市2018届高三4月模拟】从0，1，2，3这4个数字中选3个数字组成没有重复数字的三位数，则该三位数能被3整除的概率为
A. B. C. D.
【答案】C
【解析】从中选三个组成三位数共有个，该三位数被整除的有两种情况：三位数由组成和由组成，分别有和个数，被整除的数共有个，由古典概型概率公式得，故选C.
9．【贵州省凯里市第一中学2018届高三模拟】2017年11月30日至12月2日,来自北京、上海、西安、郑州、青岛及凯里等七所联盟学校(“全国理工联盟”)及凯里当地高中学校教师代表齐聚凯里某校举行联盟教研活动，在数学同课异构活动中,7名数学教师各上一节公开课，教师甲不能上第三节课，教师乙不能上第六节课，则7名教师上课的不同排法有（ ）种
A. 5040 B. 4800 C. 3720 D. 4920
【答案】D
【解析】由题意可得：
故选
10．【2018届湖南省（长郡中学、衡阳八中）、江西省（南昌二中）等十四校高三第二次联考】甲、乙、丙、丁、戊五位同学相约去学校图书室借、、、四类课外书（每类课外书均有若干本），已知每人均只借阅一本，每类课外书均有人借阅，且甲只借阅类课外书，则不同的借阅方案种类为（ ）
A. B. C. D.
【答案】C
【解析】分两类：乙、丙、丁、戊四位同学、、、四类课外书各借1本，共种方法；
乙、丙、丁、戊四位同学、、三类课外书各借1本，共有中方法，故方法总数为60种.
故选C.
11．某铁路货运站对6列货运列车进行编组调度,决定将这6列列车编成两组,每组3列,且甲与乙两列列车不在同一小组,如果甲所在小组3列列车先开出,那么这6列列车先后不同的发车顺序共有________种．
【答案】216
【解析】先进行分组,从其余4列火车中任取2列与甲一组,不同的分法为C＝6种．
由分步计数原理得不同的发车顺序为C·A·A＝216种．
12.两所学校分别有2名、3名学生获奖,这5名学生要排成一排合影,则同校学生排在一起的概率是__________.
【答案】
【解析】5名学生要排成一排合影共有种不同的排法,同校学生排在一起共有种不同的排法,所以所求概率为.
13．某班级原有一张周一到周五的值日表,五位班干部每人值一天,现将值日表进行调整,要求原周一和周五的两人都不值这两天,周二至周四的这三人都不值自己原来的日期,则不同的调整方法种数是_________________（用数字作答）.
【答案】
【解析】先安排周一和周五的两人,有=6种方法,然后再安排中间三天剩下的那天的人值日,有周一和周五两天选择,最后安排最后两个人,有 种方法,所以共有种方法.
14．某科室派出4名调研员到3个学校,调研该校高三复习备考近况,要求每个学校至少一名,则不同的分配方案种数为 .
【答案】
【解析】分两步完成:第一步将名调研员按分成三组,其分发有种；第二步将分好的三组分配到三个学校,其分发有种,所以不同的分配方案种数种,故填.
15．将编号为1,2,3,4的四个小球放入3个不同的盒子中,每个盒子里至少放1个,则恰好1个盒子放有2个连号小球的所有不同方法有 种．（用数字作答）
【答案】
【解析】由题意这四个数有,,；,,；,,三种分组方式,将其放入三个盒子有种方法,故应填答案.
16．】三位老师和三位学生站成一排,要求任何两位学生都不相邻,则不同的排法总数为 ．
【答案】
【解析】
试题分析:由题设运用插空法可得．故应填答案．
17．如图所示,某货场有两堆集装箱,一堆2个,一堆3个,现需要全部装运,每次只能从其中一堆取最上面的一个集装箱,则在装运的过程中不同取法的种数是 ____________（用数字作答）.
【答案】.
【解析】如下图所示,对集装箱编号,则可知排列相对顺序为,,（即1号箱子一定在2号箱子前被取走,2号箱子一定在3号箱子前被取走）,,,故不同取法的种数是,故填：.
18. 【湖北省荆门市2019届高三元月调研】学校在高一年级开设选修课程，其中历史开设了三个不同的班，选课结束后，有5名同学要求改修历史，但历史选修班每班至多可接收2名同学，那么安排好这5名同学的方案有______种用数字作答
【答案】90
【解析】根据题意，分2步进行分析：
，将5名同学分成1、2、2的三组，有种分组方法；
，将分好的3组全排列，对应3个班级，有种情况，
则安排好这5名同学的方案种；
故答案为90．
15
展开阅读全文