解排列组合问题的十七种常用策略

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,解排列组合问题的常用策略,1,排列组合应用题解法综述,（,目录,）,基本概念和考点,合理分类和准确分步,特殊元素和特殊位置问题,相邻相间问题,定序问题,分房问题,环排、,多排问题,小集团问题,先选后排问题,平均分组问题,构造模型策略,实验法（枚举法）,其它特殊方法,2,排列组合应用题解法综述,计数问题中排列组合问题是最常见的，由于其解法往往是构造性的,因此方法灵活多样,不同解法导致问题难易变化也较大，而且解题过程出现“重复”和“遗漏”的错误较难自检发现。因而对这类问题归纳总结，并把握一些常见解题模型是必要的。,回目录,3,基,本,原,理,组合,排列,排列数公式,组合数公式,组合数性质,应,用,问,题,知识结构网络图：,回目录,4,名称内容,分类原理,分步原理,定 义,相同点,不同点,两个原理的区别与联系：,做一件事或完成一项工作的方法数,直接（,分类,）完成,间接（,分步骤,）完成,做一件事，完成它可以有,n,类办法，,第一类办法中有,m,1,种不同的方法，,第二类办法中有,m,2,种不同的方法,，,第,n,类办法中有,m,n,种不同的方法，,那么完成这件事共有,N=m,1,+m,2,+m,3,+m,n,种不同的方法,做一件事，完成它可以有,n,个步骤，,做第一步中有,m,1,种不同的方法，,做第二步中有,m,2,种不同的方法,，,做第,n,步中有,m,n,种不同的方法，,那么完成这件事共有,N=m,1,m,2,m,3,m,n,种不同的方法,.,回目录,5,1.,排列和组合的区别和联系：,名 称,排 列,组 合,定义,种数,符号,计算,公式,关系,性质,，,从,n,个不同元素中取出,m,个元,素，,按一定的顺序,排成一列,从,n,个不同元素中取出,m,个元,素，,把它并成,一组,所有排列的的个数,所有组合的个数,回目录,6,2.掌握解决排列组合问题的常用策略;,能运 用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力,3.学会应用数学思想和方法解决排列组合问题.,教学目标,1,.进一步理解和应用分步计数原理和分类计数原理。,回目录,7,完成一件事，有,n,类办法，在第1类办法中有,m,1,种不同的方法，在第2类办法中有,m,2,种不同的方法，在第,n,类办法中有,m,n,种不同的方法，那么完成这件事共有：,种不同的方法,1.,分类计数原理(加法原理),回目录,8,完成一件事，需要分成,n,个步骤，做第1步有,m,1,种不同的方法，做第2步有,m,2,种不同的方法，做第,n,步有,m,n,种不同的方法，那么完成这件事共有：,种不同的方法,2.,分步计数原理（乘法原理）,分步计数原理,各步相互依存,，每步中的方法完成事件的,一个阶段,，,不能完成整个事件,3.,分类计数原理,分步计数原理区别,分类计数原理,方法相互独立,，任何一种方法都可以,独立地完成这件事,。,回目录,9,某校组织学生分,4,个组从,3,处风景点中选一处去春游,则不同的春游方案的种数是,A. B. C. D.,（ 选,C,）,回目录,10,将数字,1,、,2,、,3,、,4,填入标号为,1,、,2,、,3,、,4,的四个方格里,每格填一个数字，则每个方格的标号与所填的数字都不相同的填法共有,A. 6,种,B. 9,种,C.11,种,D.23,种,（,331= 9.,可用框图具体填写）,回目录,11,考点分析,从,考纲大纲,看：高考对这部分的要求还是比较高的,.,要重视两个计数原理、排列、组合在解决实际问题上的应用,.,值得提醒地是：计数模型不一定是排列或组合,.,画一画，数一数，算一算，是基本的计数方法，不可废弃,.,例（,2001,年新课程卷） 某赛季足球比赛的计分规则是：胜一场，得,3,分；平一场，得,1,分；负一场，得,0,分,.,一球队打完,15,场，积,33,分,.,若不考虑顺序，该队胜、负、平的情况共有,A 3,种,B 4,种,C 5,种,D 6,种,.,回目录,12,解决排列组合综合性问题的一般过程如下,:,1.认真审题弄清要做什么事,2.怎样做才能完成所要做的事,即采取分步还,是分类,或是分步与分类同时进行,确定分多,少步及多少类。,3.确定每一步或每一类是排列问题(,有序,)还是,组合(,无序,),问题,元素总数是多少及取出多,少个元素.,解决排列组合综合性问题，往往类与步交,叉，因此必须掌握一些常用的解题策略,回目录,13,判断下列问题是组合问题还是排列问题,?,(1),设集合,A,=,a,b,c,d,e,，则集合,A,的含有,3,个元素的子集有多少个,?,(2),某铁路线上有,5,个车站，则这条铁路线上,共需准备多少种车票,?,有多少种不同的火车票价？,组合问题,排列问题,(3)10,名同学分成人数相同的数学和,英语两个学习小组，共有多少种分法,?,组合问题,(4)10,人聚会，见面后每两人之间要,握手相互问候，共需握手多少次,?,组合问题,(5),从,4,个风景点中选出,2,个安排游览,有多少种不同的方法,?,组合问题,(6),从,4,个风景点中选出,2,个,并确定这,2,个风景,点的游览顺序,有多少种不同的方法,?,排列问题,组合问题,回目录,14,合理分类和准确分步,解排列（或）组合问题，应按元素的性质进行分类，分类标准明确，不重不漏；,按,事情的发生的连续过程分步，做到分步层次清楚,.,回目录,15,总的原则,合理,分类和,准确,分步,解排列（或）组合问题，应按元素的性质进行分类，事情的发生的连续过程分步，做到分类标准明确，分步层次清楚，不重不漏。,解法,1,分析：先安排甲，按照要求对其进行分类，分两类：,根据分步及分类计数原理，不同的站法共有,例,1 6,个同学和,2,个老师排成一排照相，,2,个老师站中间，学生甲不站排头，学生乙不站排尾，共有多少种不同的排法？,1,）若甲在排尾上，则剩下的,5,人可自由安排，有 种方法,.,若甲在第,2,、,3,、,6,、,7,位，则,排尾的排法有 种，,1,位的排法有 种,第,2,、,3,、,6,、,7,位的排法有 种,，根据分步计数原理，不同的站法有 种。,再安排老师，有,2,种方法。,回目录,16,把握分类原理、分步原理是基础,例,1,如图，某电子器件是由三个电,阻组成的回路,其中有,6,个焊接,点,A,，,B,，,C,，,D,，,E,，,F,，如果某个焊接点脱落，整个电路就会不通。现发现电路不通了,那么焊接点脱落的可能性共有（ ）,63,种 （,B,）,64,种 （,C,）,6,种 （,D,）,36,种,分析,:,由加法原理可知,由乘法原理可知,2,22222-1=63,回目录,17,（,1,）,0,，,1,，,2,，,3,，,4,，,5,可组成多少个无重复数字且能被五整除的五位数？,练 习,1,分类：个位数字为,5,或,0,：,个位数为,0,：,个位数为,5,：,回目录,18,（,2,）,0,，,1,，,2,，,3,，,4,，,5,可组成多少个无重复数字且大于,31250,的五位数？,分类：,引申,1,：,31250,是由,0,，,1,，,2,，,3,，,4,，,5,组成的无重复数字的五位数中从小到大第几个数？,方法一：（排除法）,方法二：（直接法）,引申,2,：由,0,，,1,，,2,，,3,，,4,，,5,组成的无重复数字的,五位数中大于,31250,，小于,50124,的数共有多少个？,2004,全国,12,在由数字,1,，,2,，,3,，,4,，,5,组成的所有,没有重复的,5,位数中，大于,23145,且小于,43512,的,数共有（ ）个,58,回目录,19,合理分类与分步策略,例.在一次演唱会上共10名演员,其中8人能,能唱歌,5人会跳舞,现要演出一个2人,唱歌2人伴舞的节目,有多少选派方法?,解：,10演员中有5人只会唱歌，2人只会跳舞,3人为全能演员。,以只会唱歌的5人是否,选上唱歌人员为标准进行研究,只会唱,的,5人中没有人选上唱歌人员共有_,种,只会唱的,5人中只有1人选上唱歌人,员_种,只会唱的,5人中只有2人,选上唱歌人员有_种，由分类计数,原理共有_种。,+,+,回目录,20,本题还有如下分类标准：,*,以3个全能演员是否选上唱歌人员为标准,*,以3个全能演员是否选上跳舞人员为标准,*,以只会跳舞的2人是否选上跳舞人员为标准,都可经得到正确结果,解含有约束条件的排列组合问题，可按元素,的性质进行分类，按事件发生的连续过程分,步，做到标准明确。分步层次清楚，不重不,漏，分类标准一旦确定要贯穿于解题过程的,始终。,回目录,21,有不同的数学书,7,本，语文书,5,本，英语书,4,本，由其中取出不是同一学科的书,2,本，共有多少种不同的取法？,（,75 + 74 + 54 = 83,）,回目录,22,（,4,）（,2005,福建,理）从,6,人中选,4,人分别到巴黎、伦敦、悉尼、莫斯科四个城市游览，要求每个城市有一人游览，每人只游览一个城市，且这,6,人中甲、乙两人不去巴黎游览，则不同的选择方案共有（ ）,A,300,种,B,240,种,C,144,种,D,96,种,B,（直接法）分三种情况：,情况一,不选甲、乙两个去游览,:,则有 种选择方案,情况二,:,甲、乙中有一人去游览：有 种选择方案,;,情况三,：,甲、乙两人都去游览,有 种选择方案,综上不同的选择方案共有,+ + =240,（间接法）,回目录,23,1.从4名男生和3名女生中选出4人参加某个座 谈会，若这4人中必须既有男生又有女生，则不同的选法共有_,34,练习题,2.,3成人2小孩乘船游玩,1号船最多乘3人, 2,号船最多乘2人,3号船只能乘1人,他们任选,2只船或3只船,但小孩不能单独乘一只船,这3人共有多少乘船方法.,27,回目录,24,特殊元素和特殊位置问题,25,特殊元素和特殊位置优先策略,例1.由0,1,2,3,4,5可以组成多少个没有重复数字,五位奇数.,解:由于末位和首位有特殊要求,应该优先安,排,以免不合要求的元素占了这两个位置,先排末位共有_,然后排首位共有_,最后排其它位置共有_,由分步计数原理得,=288,位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。若有多个约束条件，往往是考虑一个约束条件的同时还要兼顾其它条件,回目录,26,“特殊元素、特殊位置优先安排法”,对于特殊元素的排列组合问题，一般应先考虑特殊元素，再考虑其它元素。,例,2,用,0,，,1,，,2,，,3,，,4,这五个数，组成没有重复数字,的三位数，其中偶数共有（ ）,A.24 B.30 C.40 D.60,分析：由于该三位数是偶数，所以末尾数字必须是偶数， 又因为,0,不能排首位，故,0,就是其中的“特殊”元素，应优先安排。按,0,排在末尾和不排在末尾分为两类；,0,排在末尾时，有 个；,0,不排在末尾时，先用偶数排个位，再排百位，最后排十位有 个；,由分类计数原理，共有偶数,30,个,.,B,解题技巧,回目录,27,学生要从六门课中选学两门：,（,1,）有两门课时间冲突，不能同时学，有几种选法？,（,2,）有两门特别的课，至少选学其中的一门，有几种选法？,回目录,28,解法一：,解法二：,（,1,）有两门课时间冲突,不能同时学，有几种选法？,回目录,29,解法一：,解法二：,（,2,）有两门特别的课，至少选学其中的一门，有几种选法？,30,特殊元素（或位置）优先安排,例,将,5,列车停在,5,条不同的轨道上，其中,a,列车不停在第一轨道上，,b,列车不停在第二轨道上，那么不同的停放方法有（ ）,（,A,）,120,种 （,B,）,96,种 （,C,）,78,种 （,D,）,72,种,解：,31,7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里,，,问有多少不同的种法？,练习题,32,（,1,）,0,1,2,3,4,5,这六个数字可组成多少个无重复数字的五位数？,（,2,）,0,，,1,，,2,，,3,，,4,，,5,可组成多少个无重复数字的五位奇数？,练 习,33,（,3,）,(2005,北京,文,),五个工程队承建某项工程的,5,个不同的子项目，每个工程队承建,1,项，其中甲工程队不能承建,1,号子项目，则不同的承建方案共有（ ）种。,（,4,）,(2005,全国,II,理,),在由数字,0,，,1,，,2,，,3,，,4,，,5,所组成的没有重复数字的四位数中，不能被整除的数共有,_,个,解：不能被,5,整除的有两种情况：情况,1,、首位为,5,有,种，情况,2,、首位不是,5,的有 种，故在由数字,0,，,1,，,2,，,3,，,4,，,5,所组成的没有重复数字的四位数中，,不能被整除的数共有,+ =192(,个,),192,34,小结：,1,、“在”与“不在”可以相互转化。解决某些元素在某些位置上用“定位法”，解决某些元素不在某些位置上一般用“间接法”或转化为“在”的问题求解。,2,、排列组合应用题极易出现“重”、“漏”现象，而重”、“漏”错误常发生在该不该分类、有无次序的问题上。为了更好地防“重”堵“漏”，在做题时需认真分析自己做题思路，也可改变解题角度，利用一题多解核对答案,回目录,35,相邻相间问题,36,相邻元素捆绑策略,例. 7人站成一排 ,其中甲乙相邻且丙丁相,邻, 共有多少种不同的排法.,甲,乙,丙,丁,由分步计数原理可得共有,种不同的排法,=480,解：可先将甲乙两元素捆绑成整体并看成,一个复合元素，同时丙丁也看成一个,复合元素，再与其它元素进行排列，,同时对相邻元素内部进行自排。,要求某几个元素必须排在一起的问题,可以用,捆绑法来解决问题.即将需要相邻的元素合并,为一个元素,再与其它元素一起作排列,同时,要注意合并元素内部也必须排列,.,回目录,37,例,5,个男生,3,个女生排成一排,3,个女生要排在一起,有多少种不同的排法,?,解,因为女生要排在一起,所以可以将,3,个女生看成是一个人,与,5,个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法,.,结论,捆绑法,:,要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题,.,即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列,.,分析,此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题,.,回目录,38,某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为（ ）,练习题,20,回目录,39,有,8,本互不相同的书,其中数学书,3,本,外文书,2,本,其他书,3,本,.,若将这些书排成一列放在书架上,则数学书恰好排在一起,外文书也恰好排在一起的排法共有,_,种,(,结果用数 值表示,).,回目录,40,不相邻问题插空策略,例3.一个晚会的节目有4个舞蹈,2个相声,3个,独唱,舞蹈节目不能连续出场,则节目的出,场顺序有多少种？,解:分两步进行第一步排2个相声和3个独唱共,有,种，,第二步将4舞蹈插入第一步排,好的6个元素中间包含首尾两个空位共有,种,不同的方法,由分步计数原理,节目的,不同顺序共有,种,相,相,独,独,独,元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端,回目录,41,不相邻问题,插空法,对于某几个元素不相邻得排列问题，可先将其它,元素排好，然后再将不相邻的元素在已排好的元素,之间及两端的空隙之间插入即可。,例,5 7,人站成一排照相，要求甲，乙，丙三人不相邻，分别有多少种站法？,分析：可先让其余,4,人站好，共有 种排法，再在这,4,人之间及两端的,5,个“空隙”中选三个位置让甲、乙、丙插入，则有 种方法，这样共有 种不同的排法。,回目录,42,某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为（ ）,30,练习题,回目录,43,（,1,）三个男生，四个女生排成一排，男生、女生各站一起，有几种不同方法？,（,2,）,三个男生，四个女生排成一排，,男生之间、女生之间不相邻，有几种不同排法？,捆绑法：,插空法：,（,3,）,(2005 ,辽宁,),用、,组成没有重复数字的八位数，要求与相邻，与相邻，与相邻，而与不相邻，这样的八位数共有,_,个（用数字作答）,练 习,回目录,44,(3)(2005 ,辽宁,),用、,组成没有重复数字的八位数，要求与相邻，,与相邻，与相邻，而与不相邻，,这样的八位数共有,_,个（用数字作答）,将与，与，与捆绑在一起排成一列,有 种，再将、插入,4,个空位中的两个,有 种，故有 种,引申,:,用、组成没有重复数字,的六位数，要求与相邻，与相邻，与,相邻，现将,7,、,8,插进去，仍要求与相邻，与,相邻，与相邻，那么插法共有,_,种,（用数字作答）,回目录,45,“相邻”用“捆绑”，“不邻”就“插空”,例,七人排成一排，甲、乙两人必须相邻，且甲、乙都不与丙相邻，则不同的排法有（ ）种,960,种 （,B,）,840,种 （,C,）,720,种 （,D,）,600,种,解：,另解：,回目录,46,练习,某城新建的一条道路上有,12,只路灯，为了节省用电而不影响正常的照明，可以熄灭其中三盏灯，但两端的灯不能熄灭，也不能熄灭相邻的两盏灯，可以熄灭的方法共有（ ）,（,A,） 种（,B,） 种 （,C,） 种 （,D,） 种,解：,回目录,47,例,学校组织老师学生一起看电影，同一排电影票,12,张。,8,个学生，,4,个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的坐法？,解,先排学生共有 种排法,然后把老师插入学生之间的空档，共有,7,个空档可插,选其中的,4,个空档,共有 种选法,.,根据乘法原理,共有的不同坐法为 种,.,结论,插入法,:,对于某两个元素或者几个元素要求不相邻的问题,可以用插入法,.,即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可,.,分析,此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就要特殊对待,.,所涉及问题是排列问题,.,回目录,48,小结：,以元素相邻为附加条件的应把相邻元素视为一个整体，即采用“捆绑法”；以某些元素不能相邻为附加条件的,可采用“插空法”。“插空”有同时“插空”和有逐一“插空”,并要注意条件的限定,.,回目录,49,定序问题倍缩空位插入策略,定序问题,50,例,6,有,4,名男生，,3,名女生。,3,名女生,高矮互不等，,将,7,名学生排成一行，要求从左到右，女生从矮到高,排列，有多少种排法？,顺序固定问题用“除法”,对于某几个元素顺序一定的排列问题，可先将这几个元素与其它元素一同进行排列，然后用总的排列数除以这几个元素的全排列数,.,所以共有 种。,分析：先在,7,个位置上作全排列，有 种排法。其中,3,个女生因要求“从矮到高”排，只有一种顺序故 只,对应一种排法，,回目录,51,定序问题倍缩空位插入策略,例4.7人排队,其中甲乙丙3人顺序一定共有多,少不同的排法,解:,(,倍缩法,)对于某几个元素顺序一定的排列,问题,可先把这几个元素与其他元素一起,进行排列,然后用总排列数除以,这几个元,素之间的全排列数,则共有不同排法种数,是：,（,空位法,）设想有7把椅子让除甲乙丙以外,的四人就坐共有,种方法，其余的三个,位置甲乙丙共有,种坐法，则共有,种,方法,1,思考:可以先让甲乙丙就坐吗?,回目录,52,例,6,有,4,名男生，,3,名女生。,3,名女生,高矮互不等，,将,7,名学生排成一行，要求从左到右，女生从矮到高,排列，有多少种排法？,顺序固定问题用“除法”,对于某几个元素顺序一定的排列问题，可先将这几个元素与其它元素一同进行排列，然后用总的排列数除以这几个元素的全排列数,.,所以共有 种。,分析：先在,7,个位置上作全排列，有 种排法。其中,3,个女生因要求“从矮到高”排，只有一种顺序故 只,对应一种排法，,回目录,53,（,插入法,)先排甲乙丙三个人,共有1种排法,再,把其余4四人,依次,插入共有,方法,4*5*6*7,定序问题可以用倍缩法，还可转化为占位插,空模型处理,练习题,10人身高各不相等,排成前后排，每排5人,要,求从左至右身高逐渐增加，共有多少排法？,回目录,54,例,期中安排考试科目,9,门,语文要在数学之前考,有多少种不同的安排顺序,?,解,不加任何限制条件,整个排法有 种,“,语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有 种,.,结论,对等法,:,在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一,.,在求解中只要求出全体,就可以得到所求,.,分析,对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了,.,并且也避免了问题的复杂性,.,回目录,55,分房问题,又名：住店法，,重排问题求幂策略,56,住店法,解决“允许重复排列问题”要注意区分两类元素：,一类元素可以重复，另一类不能重复，把不能重复的元素看作“客”，能重复的元素看作“店”，再利用乘法原理直接求解。,例,10,七名学生争夺五项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有（ ）,A. B. C D.,分析：因同一学生可以同时夺得,n,项冠军，故学生可重复排列，将七名学生看作,7,家“店”，五项冠军看作,5,名“客”，每个“客”有,7,种住宿法，由乘法原理得 种。,注：对此类问题，常有疑惑，为什么不是 呢？,用分步计数原理看，,5,是步骤数，自然是指数。,回目录,57,重排问题求幂策略,例.把6名实习生分配到7个车间实习,共有,多少种不同的分法,解:完成此事共分六步:把第一名实习生分配,到车间有,种分法.,7,把第二名实习生分配,到车间也有7种分法，,依此类推,由分步计,数原理共有 种不同的排法,允许重复的排列问题的特点是以元素为研究,对象，元素不受位置的约束，可以逐一安排,各个元素的位置，一般地,n,不同的元素没有限,制地安排在,m,个位置上的排列数为 种,n,m,回目录,58,1. 某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为（ ）,42,2. 某8层大楼一楼电梯上来8名乘客人,他们,到各自的一层下电梯,下电梯的方法,（ ）,练习题,回目录,59,环排问题和,多排问题,60,环排问题线排策略,例6. 5人围桌而坐,共有多少种坐法?,解：,围桌而坐与,坐成一排的不同点在于，坐成,圆形没有首尾之分，所以固定一人,A,并从,此位置把圆形展成直线其余4人共有_,种排法即,A,B,C,E,D,D,A,A,B,C,E,（5-1)！,一般地,n,个不同元素作圆形排列,共有(,n-1)!,种排法.如果从,n,个不同元素中取出,m,个元素作圆形排列共有,回目录,61,练习题,6颗颜色不同的钻石，可穿成几种钻石圈？,60,62,多排问题直排策略,例7.8人排成前后两排,每排4人,其中甲乙在,前排,丁在后排,共有多少排法,解:8人排前后两排,相当于8人坐8把椅子,可以,把椅子排成一排.,先在前4个位置排甲乙两,个特殊元素有_种,再排后4个位置上的,特殊元素有_种,其余的5人在5个位置,上任意排列有_种,则共有_种.,前排,后排,一般地,元素分成多排的排列问题,可归结为一排考虑,再分段研究,.,回目录,63,有两排座位，前排11个座位，后排12个座位，现安排2人就座规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是_,346,练习题,回目录,64,小集团问题,65,小集团问题先整体局部策略,例9.用1,2,3,4,5组成没有重复数字的五位数,其中恰有两个偶数夹1,在两个奇数之,间,这样的五位数有多少个？,解：把,当作一个小集团与排队,共有_种排法，再排小集团内部共有,_,种排法，由分步计数原理共有,_种排法.,3,1524,小集团,小集团排列问题中，先整体后局部，再结合其它策略进行处理。,回目录,66,.计划展出10幅不同的画,其中1幅水彩画,幅油画,幅国画, 排成一行陈列,要求同一,品种的必须连在一起，并且水彩画不在两,端，那么共有陈列方式的种数为_,2. 5男生和女生站成一排照像,男生相邻,女,生也相邻的排法有_种,回目录,67,元素相同问题隔板策略,应用背景：相同元素的名额分配问题,不定方程的正整数解问题,隔板法的使用特征：,相同的元素分成若干部分，每部分至少一个,68,元素相同问题隔板策略,例.,有10个运动员名额，在分给7个班，每,班至少一个,有多少种分配方案？,解：因为10个名额没有差别，把它们排成,一排。相邻名额之间形成个空隙。,在个空档中选个位置插个隔板，,可把名额分成份，对应地分给个,班级，每一种插板方法对应一种分法,共有_种分法。,一班,二班,三班,四班,五班,六班,七班,将,n,个相同的元素分成,m,份（,n，m,为正整数）,每份至少一个元素,可以用,m-1,块隔板，插入,n,个元素排成一排的,n-1,个空隙中，所有分法数为,回目录,69,例,高二年级,8,个班,组织一个,12,个人的年级学生分会,每班要求至少,1,人,名额分配方案有多少种,?,解,此题可以转化为,:,将,12,个相同的白球分成,8,份,有多少种不同的分法问题,因此须把这,12,个白球排成一排,在,11,个空档中放上,7,个相同的隔板,每个空档最多放一个,即可将白球分成,8,份,显然有 种不同的放法,所以名额分配方案有 种,.,结论,转化法,:,对于某些较复杂的、或较抽象的排列组合问题，可以利用转化思想,将其化归为简单的、具体的问题来求解,.,分析,此题若直接去考虑的话,就会比较复杂,.,但如果我们将其转换为等价的其他问题,就会显得比较清楚,方法简单,结果容易理解,.,回目录,70,练 习,（,1,）将,10,个学生干部的培训指标分配给,7,个不同的班级，每班至少分到一个名额，不同的分配方案共有 （ ）种。,（,2,）不定方程 的正整数解共有（ ）组,回目录,71,练习题,10个相同的球装5个盒中,每盒至少一,有多少装法？,2 .,x+y+z+w=100,求这个方程组的自然数解,的组数,回目录,72,小结：,把,n,个相同元素分成,m,份每份,至少,1,个元素,问有多少种不同分法的问题可以采用“隔板法”得出共有 种,.,回目录,73,间接法解题,74,正难则反总体淘汰策略,例11.从0,1,2,3,4,5,6,7,8,9这十个数字中取出三,个数，使其和为不小于10的偶数,不同的,取法有多少种？,解：这问题中如果直接求不小于10的偶数很,困难,可用总体淘汰法。,这十个数字中有5,个偶数5个奇数,所取的三个数含有3个偶数的取法有_,只含有1个偶数的取法有_,和为偶数的取法共有_,再淘汰和小于10的偶数共_,符合条件的取法共有_,9,013,015,017,023,025,027,041,045,043,+,- 9,+,有些排列组合问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中淘汰.,回目录,75,例：用,0,，,1,，,2,，,3,，,4,这五个数，组成没有重复,数字的三位数，其中,1,不在个位的数共有,_,种。,间接法,(,总体淘汰法,正难则反）,对于含有否定词语的问题，还可以从总体中把不符合要求的减去，此时应注意,既不能多减又不能少减。,分析,：,五个数组成三位数的全排列有 个，,0,排在首位的,有 个 ，,1,排在末尾的有 ，减掉这两种不合条件的排,法数，再加回百位为,0,同时个位为,1,的排列数 （为什么？）,故共有 种。,76,例,我们班里有,43,位同学,从中任抽,5,人,正、副班长、团支部书记至少有一人在内的抽法有多少种,?,解,43,人中任抽,5,人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有,1,人在内的抽法有 种,.,结论,去杂法,:,有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除,.,分析,此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况,.,而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便,.,这样就可以简化计算过程,.,回目录,77,（,1,）三个男生，四个女生排成一排，甲不在最左，乙不在最右，有几种不同方法？,（,2,）五人从左到右站成一排，其中甲不站排头，乙不站第二个位置，那么不同的站法有（ ）,A.120 B.96 C.78 D.72,直接,练 习,3,回目录,78,（,3,）,用,间接法解例,1,“6,个同学和,2,个老师排成一排照相，,2,个老师站中间，学生甲不站排头，学生乙不站排尾，共有多少种不同的排法？”,回目录,79,我们班里有43位同学,从中任抽5人,正、,副班长、团支部书记至少有一人在内的,抽法有多少种?,练习题,回目录,80,平均分组问题除法策略,“,分书问题,”,81,平均分组问题除法策略,例,12. 6本不同的书平均分成3堆,每堆2本共有,多少分法？,解: 分三步取书得 种方法,但这里出现,重复计数的现象,不妨记6本书为,ABCDEF,若第一步取,AB,第二步取,CD,第三步取,EF,该分法记为(,AB,CD,EF),则 中还有,(AB,EF,CD),(CD,AB,EF),(CD,EF,AB),(EF,CD,AB),(EF,AB,CD),共有 种取法 ,而,这些分法仅是(,AB,CD,EF),一种分法,故共,有 种分法。,平均分成的组,不管它们的顺序如何,都是一种情况,所以分组后要一定要除以 (,n,为均分的组数)避免重复计数。,回目录,82,1 将13个球队分成3组,一组5个队,其它两组4,个队, 有多少分法？,2.10名学生分成3组,其中一组4人, 另两组3人,但正副班长不能分在同一组,有多少种不同,的分组方法,（1540）,3.某校高二年级共有六个班级，现从外地转 入4名学生，要安排到该年级的两个班级且每班安排2名，则不同的安排方案种数为_,回目录,83,分清排列、组合、等分的算法区别,例,(1),今有,10,件不同奖品,从中选,6,件分给甲一件,乙二件和丙三件,有多少种分法,?,(2),今有,10,件不同奖品,从中选,6,件分给三人,其中,1,人一件,1,人二件,1,人三件,有多少种分法,?,(3),今有,10,件不同奖品,从中选,6,件分成三份,每份,2,件,有多少种分法,?,解：（,1,）,（,2,）,(3),回目录,84,练习,(1),今有,10,件不同奖品,从中选,6,件分成三份,二份各,1,件,另一份,4,件,有多少种分法,?,(2),今有,10,件不同奖品,从中选,6,件分给甲乙丙三人,每人二件有多少种分法,?,解,: (1),(2),回目录,85,小结：,排列与组合的区别在于元素是否有序,; m,等分的组合问题是非等分情况的,;,而元素相同时又要另行考虑,.,回目录,86,构造模型策略,例. 马路上有编号为1,2,3,4,5,6,7,8,9的,九只路灯,现要关掉其中的3盏,但不能关,掉相邻的2盏或3盏,也不能关掉两端的2,盏,求满足条件的关灯方法有多少种？,解：把此问题当作一个排队模型在6盏,亮灯的5个空隙中插入3个不亮的灯,有_ 种,一些不易理解的排列组合题如果能转化为,非常熟悉的模型，如占位填空模型，排队,模型，装盒模型等，可使问题直观解决,回目录,87,练习题,某排共有10个座位，若4人就坐，每人左右,两边都有空位，那么不同的坐法有多少种？,120,回目录,88,先选后排问题,89,八.排列组合混合问题先选后排策略,例.有5个不同的小球,装入4个不同的盒内,每盒至少装一个球,共有多少不同的装,法.,解:第一步从5个球中选出2个组成复合元共,有_种方法.再把5个元素(包含一个复合,元素)装入4个不同的盒内有_种方法.,根据分步计数原理装球的方法共有_,解决排列组合混合问题,先选后排是最基本,的指导思想.,此法与,相邻元素捆绑策略相似,吗?,回目录,90,练习题,一个班有6名战士,其中正副班长各1人,现从中选4人完成四种不同的任务,每人,完成一种任务,且正副班长有且只有1人,参加,则不同的选法有_ 种,192,回目录,91,3,名医生和,6,名护士被分配到,3,所学校为学生体检,每校分配,1,名医生和,2,名护士,不同的分配方法共有多少种,?,先选后排问题的处理方法,解法一：先组队后分校（先分堆后分配）,回目录,92,解法二：依次确定到第一、第二、第三所学校去的医生和护士,.,回目录,93,为支援西部开发,有,3,名教师去银川市三所学校任教,每校分配,1,人,不同的分配方法共有,_,种,(,用数字作答,).,练习,改为,4,名教师？,改为,5,名教师？,回目录,94,有甲、乙、丙三项任务,甲需,2,人承担,乙、丙各需,1,人承担,.,从,10,人中选派,4,人承担这三项任务,不同的选法共有多少种,?,回目录,95,四名同学分配到三个办公室去搞卫生,每个办公室至少去一名学生,不同的分配方法有多少种,?,回目录,96,1,、有甲、乙、丙三项工程，甲需要,2,人承担，乙、丙各需,1,人承担，从,10,人中选派,4,人承担这三项任务，不同的承担方法共有,_,种；,2,、某办公室有,5,人办公，现要排一个周轮值表，每人至少一天，其中甲不能在周六和周日，且甲肯定值两天，则不同的排表方式有,_,种；,3,、,学校决定下周对高一年级进行教学情况抽测。决定基础科抽两门，文科、理科各抽一门，技能科（音、体、美、信）抽一门。则可能有种抽取方法。,基础训练,回目录,97,练习,某学习小组有,5,个男生,3,个女生，从中选,3,名男生和,1,名女生参加三项竞赛活动，每项活动至少有,1,人参加，则有不同参赛方法,_,种,.,解：采用先组后排方法,:,回目录,98,小结：,本题涉及一类重要问题：问题中既有元素的限制，又有排列的问题，一般是先元素（即组合）后排列。,回目录,99,实验法（穷举法），（枚举法）,应用举例,100,实验法（穷举法）,题中附加条件增多，直接解决困难时，用实验逐步寻求规律有时也是行之有效的方法。,例,将数字,1,，,2,，,3,，,4,填入标号为,1,，,2,，,3,，,4,的四个方格内，每个方格填,1,个，则每个方格的标号与所填的数字均不相同的填法种数有（ ）,A.6 B.9 C.11 D.23,分析：此题考查排列的定义，由于附加条件较多，解法较为困难，可用实验法逐步解决。,第一方格内可填,2,或,3,或,4,。如填,2,，则第二方格中内可填,1,或,3,或,4,。,若第二方格内填,1,，则第三方格只能填,4,，第四方格应填,3,。,若第二方格内填,3,，则第三方格只能填,4,，第四方格应填,1,。,同理，若第二方格内填,4,，则第三方格只能填,1,，第四方格应填,3,。因而，第一格填,2,有,3,种方法。,不难得到，当第一格填,3,或,4,时也各有,3,种，所以共有,9,种。,回目录,101,实际操作穷举策略,例.设有编号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号盒,3,4,5,回目录,102,实际操作穷举策略,例.设有编号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,号球装5号盒时,4,5号球有也,只有1种装法,由分步计数原理有,2,种,回目录,103,练 习 ：（不对号入座问题）,（,1,）（,2004,湖北）将标号为,1,，,2,，,3,，,，,10,的,10,个球放入标号为,1,，,2,，,3,，,，,10,的,10,个盒子中，,每个盒内放一个球，恰好有,3,个球的标号与其所在盒子,的标号不一致的放入方法有,_,种,（,2,）编号为,1,、,2,、,3,、,4,、,5,的五个球放入编号为,1,、,2,、,3,、,4,、,5,的五个盒子里，至多有,2,个对号入座的情形有,_,种,109,直接法：,间接法：,回目录,104,注意区别“恰好”与“至少”,从,6,双不同颜色的手套中任取,4,只，其中恰好有一双同色的手套的不同取法共有（ ）,(A) 480,种（,B,）,240,种 （,C,）,180,种 （,D,）,120,种,小结：“恰好有一个”是“只有一个”的意思。“至少有一个”则是“有一个或一个以上”，可用分类讨论法求解，它也是“没有一个”的反面，故可用“排除法”。,解：,回目录,105,练习,从,6,双不同颜色的手套中任取,4,只，其中至少有一双同色手套的不同取法共有,_,种,解：,回目录,106,对于条件比较复杂的排列组合问题，不易用,公式进行运算，往往利用穷举法或画出树状,图会收到意想不到的结果,练习题,同一寝室4人,每人写一张贺年卡集中起来,然后每人各拿一张别人的贺年卡，则四张,贺年卡不同的分配方式有多少种？,(9),2.给图中区域涂色,要求相邻区,域不同色,现有4种可选颜色,则,不同的着色方法有_种,2,1,3,4,5,72,回目录,107,其它特殊方法,108,分解与合成策略,例. 30030能被多少个不同的偶数整除,分析：先把30030分解成质因数的乘积形式,30030=235 7 1113依题,意可知偶因数必先取2,再从其余5个,因数中任取若干个组成乘积，所有,的偶因数为：,例17.正方体的8个顶点可连成多少对异面,直线,回目录,109,解：我们先从8个顶点中任取4个顶点构成四,体共有体共_,每个四面体有,_,对异面直线,正方体中的8个顶点可连成,_对异面直线,6,658=174,分解与合成策略是排列组合问题的一种最,基本的解题策略,把一个复杂问题分解成几,个小问题逐一解决,然后依据问题分解后的,结构,用分类计数原理和分步计数原理将问,题合成,从而得到问题的答案 ,每个比较复,杂的问题都要用到这种解题策略,回目录,110,化归策略,例. 25人排成55方队,现从中选3人,要,求3人不在同一行也不在同一列,不同的,选法有多少种？,解：,将这个问题退化成,9人排成33方队,现从中选3人,要求3人不在同一行也不在同一列,有多少选法.这样每行必有1人从其中的一行中选取1人后,把这人所在的行列都划掉，,回目录,111,从,55方队中选取3行3列有_选法,所以从55方队选不在同一行也不在同,一列的3人有_选法。,处理复杂的排列组合问题时可以把一个问题退化成一个简要的问题，通过解决这个简要的问题的解决找到解题方法，从而进下一步解决原来的问题,如此继续下去.从33方队中选3人的方法,有_种。再从55方队选出33,方队便可解决问题,回目录,112,对应法,例,11,在,100,名选手之间进行单循环淘汰赛（即一场比赛失败要退出比赛），最后产生一名冠军，问要,举行几场？,分析：要产生一名冠军，需要淘汰掉冠军以外的所有选手，即要淘汰,99,名选手，淘汰一名选手需要,进行一场比赛，所以淘汰,99,名选手就需要,99,场比赛。,回目录,113,某城市的街区由12个全等的矩形区组成,其中实线表示马路，从,A,走到,B,的最短路,径有多少种？,练习题,B,A,回目录,114,特征分析,研究有约束条件的排数问题，须要紧扣题目所提供的数字特征，结构特征，进行推理，分析求解。,例,由,1,，,2,，,3,，,4,，,5,，,6,六个数字可以组成多少个无重复且是,6,的倍数的五位数？,分析数字特征：,6,的倍数既是,2,的倍数又是,3,的倍数。其中,3,的倍数又满足“各个数位上的数字之和是,3,的倍数”的特征。把,6,分成,4,组，（,3,，,3,），（,6,），（,1,，,5,），（,2,，,4,），每组的数字和都是,3,的倍数。因此可分成两类讨论；,第一类：由,1,，,2,，,4,，,5,，,6,作数码；首先从,2,，,4,，,6,中任选一个作个位数字有 ，然后其余四个数在其他数位上全排列有 ，所以,第二类：由,1,，,2,，,3,，,4,，,5,作数码。依上法有,回目录,115,（,1,）练习,:,（徐州二检）从,6,人中选,4,人组成,4100m,接力赛，其中甲跑第一棒，乙不跑最后一棒，有多少种选法？,分析：（一）直接法,（二）间接法,（,2,）,从正方体的,8,个顶点中选,4,个作四面体，则不同的四面体的个数为,。,练 习,58,（,3,）,一个三位数，其十位上的数字既,小于百位上的数字也小于个位上的数字,， 且个位百位上的数字不重复（如等）,那么这样的三位数有,个,回目录,116,例,袋中有,5,分硬币,23,个,1,角硬币,10,个,如果从袋中取出,2,元钱,有多少种取法,?,解,把所有的硬币全部取出来,将得到,0.0523+0.1010=2.15,元,所以比,2,元多,0.15,元,所以剩下,0.15,元即剩下,3,个,5,分或,1,个,5,分与,1,个,1,角,所以共有 种取法,.,结论,剩余法,:,在组合问题中