高三一轮复习排列组合

2020年3月7日星期六基本原理组合排列排列数公式组合数公式应用问题1、知识结构一。复习回顾2。分类记数原理，分步记数原理分类记数原理分步记数原理原理完成一件事可以有n类办法，在第一类中有m1种不同的方法，在第二类中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共N=m1+m2+……+mn有种不同的方法。完成一件事需要分成n个步骤，第一步有m1种不同的方法，第二步有m2种不同的方法，……，第n步有mn种不同的方法，那么完成这件事共N=m1×m2×……×mn有种不同的方法。区别分类记数原理针对的是“分类”问题，其中各种方法相互独立，用其中任何一种方法都可完成这件事。分步记数原理针对的是“分步”问题，各步方法相互依存，只有各步都完成才能完成这件事。排列组合定义从n个不同元素中，任取m(m≤n)个不同元素按照一定顺序排成一列，叫做从n个不同元素中取出m个不同元素的一个排列。从n个不同的元素中，任取m（m≤n）个不同的元素并成一组，叫做从n个不同的元素中取出m个不同的元素的一个组合。区别与顺序有关与顺序无关判定看取出的两个元素互换位置是否为同一种方法，若不是，则是排列问题；若是，则是组合。公式)1()2)(1(mnnnnAmn)!(!mnn!)1()2)(1(mmnnnnmnC!!!mmnn3。排列与组合考向一分类加法计数原理【例1】►(2011·全国)某同学有同样的画册2本，同样的集邮册3本，从中取出4本赠送给4位朋友，每位朋友一本，则不同的赠送方法共有()．A．4种B．10种C．18种D．20种[审题视点]由于是两类不同的书本，故用分类加法计数原理．解析赠送一本画册，3本集邮册，共4种方法；赠送2本画册，2本集邮册共C24种方法，由分类计数原理知不同的赠送方法共4＋C24＝10(种)．答案B考向二分步乘法计数原理【例2】►(2011·北京)用数字2,3组成四位数，且数字2,3至少都出现一次，这样的四位数共有________个(用数字作答)．法二满足条件的四位数可分为三类：第一类含有一个2，三个3，共有4个；第二类含有三个2，一个3共有4个；第三类含有二个2，二个3共有C24＝6(个)，因此满足条件的四位数共有2×4＋C24＝14(个)．解析法一用2,3组成四位数共有2×2×2×2＝16(个)，其中不出现2或不出现3的共2个，因此满足条件的四位数共有16－2＝14(个)．•(2012·陕西高考)两人进行乒乓球比赛，先赢3局者获胜，决出胜负为止，则所有可能出现的情形(各人输赢局次的不同视为不同情形)共有()A．10种B．15种C．20种D．30种【解析】由题意知比赛场数至少为3场，最多为5场．分三类：①当为3场时，情况为甲或乙连赢3场，共2种．②当为4场时，若甲赢，则前3场中甲赢2场，最后一场甲赢，共有C23＝3(种)情况；同理，若乙赢也有3种情况．共有6种情况．③当为5场时，前4场，甲、乙各赢2场，最后1场胜出的人赢，共有2C24＝12(种)情况．由上综合知，共有20种情况．C【例1】如图，用5种不同的颜色给图中A、B、C、D四个区域涂色，规定每个区域只涂一种颜色，相邻区域颜色不同，求有多少种不同的涂色方法？考向3涂色问题解法一（分步法）如题图分四个步骤来完成涂色这件事需分为四步，第一步涂A区有5种涂法；第二步涂B有4种方法；第三步涂C有3种方法；第四步涂D有3种方法(还可以使用涂A的颜色)，根据分步计数原理共有5×4×3×3＝180种涂色方法．解法二：由于A、B、C两两相邻，因此三个区域的颜色互不相同，共有＝60种涂法；又D与B、C相邻、因此D有3种涂法；由分步计数原理知共有60×3＝180种涂法．1802011高考导航解法三（分类法）：完成涂色的方法分为两类，第一类：四个区域涂四种不同的颜色共有＝120种涂法；第二类：四个区域涂三种不同的颜色，由于A、D不相邻只能是A、D两区域颜色一样，将A、D看做一个区域，共＝60种涂法．由分类计数原理知共有涂法120＋60＝180(种)．方法总结：对涂色问题，有两种解法，法1是逐区图示法，注意不相邻可同色.法2根据用色多少分类法.变式1如下图，一个地区分为5个行政区，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有________种．(以数字作答)答案：72(2)某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列，这种方法称为“捆绑法”；(3)某些元素不相邻排列时，可以先排其他元素,再将这些不相邻元素插入空挡，这种方法称为“插空法”.(1)有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）法“优限法”；3.排列组合混合题的解题策略解题原则：先选后排，先分再排(4)间接法和去杂法等等.（一）特殊元素的“优先安排法”对于特殊元素的排列组合问题，一般应先考虑特殊元素，再考虑其它元素。例1用0，1，2，3，4这五个数，组成没有重复数字的三位数，其中偶数共有（）A.24B.30C.40D.60分析：由于该三位数是偶数，所以末尾数字必须是偶数，又因为0不能排首位，故0就是其中的“特殊”元素，应优先安排。按0排在末尾和不排在末尾分为两类；1)0排在末尾时，有个；2)0不排在末尾时，先用偶数排个位，再排百位，最后排十位有个；由分类计数原理，共有偶数30个.2A4111233AAAB解题技巧练习1有4名男生、5名女生，全体排成一行，甲不在中间也不在两端有多少种不同的排法？解(1)方法一(元素分析法)先排甲有6种，其余有A88种，故共有6·A88＝241920(种)排法．方法二(位置分析法)中间和两端有A38种排法，包括甲在内的其余6人有A66种排法，故共有A38·A66＝336×720＝241920(种)排法．例2用0，1，2，3，4这五个数，组成没有重复数字的三位数，其中1不在个位的数共有_______种。（二）总体淘汰法(间接法）对于含有否定词语的问题，还可以从总体中把不符合要求的减去，此时应注意既不能多减又不能少减。35A分析：五个数组成三位数的全排列有个，0排在首位的有个，1排在末尾的有，减掉这两种不合条件的排法数，再加回百位为0同时个位为1的排列数（为什么？）故共有种。24A24A35A13A392132435AAA24A24A13A种排法。各不能排某位，则有、个位，个不同元素排若22112mnmnmnAAAbamn（三）相邻问题——捆绑法对于某几个元素要求相邻的排列问题，可先将相邻的元素“捆绑”在一起，看作一个“大”的元（组），与其它元素排列，然后再对相邻的元素（组）内部进行排列。例37人站成一排照相，要求甲，乙，丙三人相邻，分别有多少种站法？分析：先将甲，乙，丙三人捆绑在一起看作一个元素，与其余4人共有5个元素做全排列，有种排法，然后对甲，乙，丙三人进行全排列。55A由分步计数原理可得：种不同排法。5353AA（四）不相邻问题——插空法对于某几个元素不相邻得排列问题，可先将其它元素排好，然后再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可。例47人站成一排照相，要求甲，乙，丙三人不相邻，分别有多少种站法？分析：可先让其余4人站好，共有种排法，再在这4人之间及两端的5个“空隙”中选三个位置让甲、乙、丙插入，则有种方法，这样共有种不同的排法。44A35A3544AA练习4.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？解:分两步进行第一步排2个相声和3个独唱共有种，55A第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种不同的方法46A由分步计数原理,节目的不同顺序共有种55A46A相相独独独元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端例5有4名男生，3名女生。3名女生高矮互不等，将7名学生排成一行，要求从左到右，女生从矮到高排列，有多少种排法？（五）顺序固定问题用“除法”对于某几个元素顺序一定的排列问题，可先将这几个元素与其它元素一同进行排列，然后用总的排列数除以这几个元素的全排列数.所以共有种。473377AAA分析：先在7个位置上作全排列，有种排法。其中3个女生因要求“从矮到高”排，只有一种顺序故只对应一种排法，33A77A（1）五人排队，甲在乙前面的排法有几种？练习5〈2〉三个男生，四个女生排成一排，其中甲、乙、丙三人的顺序不变，有几种不同排法？473377AAA分析：若不考虑限制条件，则有种排法，而甲，乙之间排法有种，故甲在乙前面的排法只有一种符合条件，故符合条件的排法有种.55A22A5522AA35A即（六）分排问题用“直排法”把n个元素排成若干排的问题，若没有其他的特殊要求，可采用统一排成一排的方法来处理.例6七人坐两排座位，第一排坐3人，第二排坐4人，则有多少种不同的坐法？分析：7个人，可以在前后排随意就坐，再无其他限制条件，故两排可看作一排处理，所以不同的坐法有种.77A（1）三个男生，四个女生排成两排，前排三人、后排四人，有几种不同排法？或：七个人可以在前后两排随意就坐，再无其他条件，所以两排可看作一排来处理不同的坐法有种77A774437AAA（2）八个人排成两排，有几种不同排法？887A练习6（七）实验法（穷举法）题中附加条件增多，直接解决困难时，用实验逐步寻求规律有时也是行之有效的方法。例7将数字1，2，3，4填入标号为1，2，3，4的四个方格内，每个方格填1个，则每个方格的标号与所填的数字均不相同的填法种数有（）A.6B.9C.11D.23分析：此题考查排列的定义，由于附加条件较多，解法较为困难，可用实验法逐步解决。第一方格内可填2或3或4。如填2，则第二方格中内可填1或3或4。若第二方格内填1，则第三方格只能填4，第四方格应填3。若第二方格内填3，则第三方格只能填4，第四方格应填1。同理，若第二方格内填4，则第三方格只能填1，第四方格应填3。因而，第一格填2有3种方法。不难得到，当第一格填3或4时也各有3种，所以共有9种。练习7.设有编号1,2,3,4,5的五个球和编号1,2，3,4,5的五个盒子,现将5个球投入这五个盒子内,要求每个盒子放一个球，并且恰好有两个球的编号与盒子的编号相同,有多少投法？解：从5个球中取出2个与盒子对号有_____种还剩下3球3盒序号不能对应，利用实际操作法，如果剩下3,4,5号球,3,4,5号盒3号球装4号盒时，则4,5号球有只有1种装法3号盒4号盒5号盒34525C20（八）住店法解决“允许重复排列问题”要注意区分两类元素：一类元素可以重复，另一类不能重复，把不能重复的元素看作“客人”，能重复的元素看作“店”，再利用乘法原理直接求解。例8七名学生争夺五项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有（）A.B.CD.分析：因同一学生可以同时夺得n项冠军，故学生可重复排列，将七名学生看作7家“店”，五项冠军看作5名“客人”，每个“客人”有7种住宿法，由乘法原理得种。注：对此类问题，常有疑惑，为什么不是呢？57577557A57C75用分步计数原理看，5是步骤数，自然是指数。练习.8.五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多少？五名学生争夺四项比赛的冠军(冠军不并列)，获得冠军的可能性有多少种？解答：报名的方法种数为4×4×4×4×4＝45(种)．获得冠军的可能情况有5×5×5×5＝54(种).（九）元素相同问题隔板策略例9.有10个运动员名额，分给7个班，每班至少一个,有多少种分配方案？解:因为10个名额没有差别，把它们排成一排.相邻名额之间形成9个空隙.在9个空档中选6个位置插个隔板,可把名额分成7份，对应地分给7个班级，每一种插板方法对应一种分法共有______种分法.69C一班二班三班四班五班六班七班练习9、12个相同的球分给3个人,每人至少一个,而且必须全部分完，有多少种分法？