问题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种排法；
甲、乙排好后,丙、丁只有一种排法,由分步计数原理知满足条件的所有排法共有331＝9种． （3）可先排丙、丁有A种排法,则甲、乙只有一种排法,由分步计数原理满足条件的排列共有A1＝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种方法． ∴这时共有A213＝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个小球一共有222224种, 其中有1个空盒,即4个小球都放进其中1个盒子的情况有2种；
则将4个小球放进取出的2个盒子中,且