排列组合经典例题总结.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,解排列组合问题的常用策略,基,本,原,理,组合,排列,排列数公式,组合数公式,组合数性质,应,用,问,题,知识结构网络图：,两个原理的区别与联系：,做一件事或完成一项工作的方法数,直接（,分类,）完成,间接（,分步骤,）完成,做一件事，完成它可以有,n,类办法，第,i,类办法中有,m,i,种不同的方法，那么完成这件事共有,N=m,1,+m,2,+m,3,+m,n,种不同的方法,做一件事，完成它可以有,n,个步骤，做第,i,步中有,m,i,种不同的方法，那么完成这件事共有,N=m,1,m,2,m,3,m,n,种不同的方法,.,排列和组合的区别和联系：,从,n,个不同元素中取出,m,个元,素，,按一定的顺序,排成一列,从,n,个不同元素中取出,m,个元,素，,把它并成,一组,所有排列的的个数,所有组合的个数,一.特殊元素和特殊位置优先策略,例1.由0,1,2,3,4,5可以组成多少个没有重复数字,五位奇数.,解:由于末位和首位有特殊要求,应该优先安,排这两个位置,.,先排末位共有_,然后排首位共有_,最后排其它位置共有_,由分步计数原理得,=288,位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。,7,种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？,练习,1,解一：分两步完成；,第一步选两葵花之外的花占据两端和中间的位置,第二步排其余的位置,：,解二：第一步由葵花去占位,：,第二步由其余元素占位：,二.相邻元素捆绑策略,例2.7人站成一排,其中甲乙相邻且丙丁相,邻,共有多少种不同的排法.,甲,乙,丙,丁,由分步计数原理可得共有,种不同的排法,=480,解：可先将甲乙两元素捆绑成整体并看成,一个复合元素，同时丙丁也看成一个,复合元素，再与其它元素进行排列，,同时对相邻元素内部进行自排。,要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也必须排列,.,七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成一排照相留念,。,若三个女孩要站在一起，四个男孩也要站在一起，共有多少种不同的排法？,练习,2,三.不相邻问题插空策略,例3.一个晚会的节目有4个舞蹈,2个相声,3个,独唱,舞蹈节目不能连续出场,则节目的出,场顺序有多少种？,解:分两步进行第一步排2个相声和3个独唱共,有,种，,第二步将4舞蹈插入第一步排,好的5个元素中间包含首尾两个空位共有,种,不同的方法,由分步计数原理,节目的,不同顺序共有,种,相,相,独,独,独,元素相离问题,可先把没有位置要求的元素进行排队,再把不相邻元素插入中间和两端,.,马路上有编号为,1,、,2,、,3,9,的九盏路灯，为节约用电，现要求把其中,3,盏灯关掉，但不能关掉相邻的,2,盏或,3,盏，也不能关掉两端的路灯，则满足条件的关灯方法有多少种。,练习3,不同的关灯方法有,：,（种）,四.定序问题缩,倍,(,空位,.,插入,),策略,例4.7人排队,其中甲乙丙3人顺序一定共有多,多少种不同的排法,.,解:,(,缩,倍,法,)对于某几个元素顺序一定的排列,问题,可先把这几个元素与其他元素一起,进行排列,然后用总排列数除以,这几个元,素之间的全排列数,则共有不同排法种数,是：,（,空位法,）设想有7把椅子让除甲乙丙以外,的四人就坐共有,种方法，其余的三个,位置甲乙丙共有,种坐法，则共有,种,方法,1,思考,:,能否让甲乙丙先坐,?,（,插入法,)先排甲乙丙三个人,共有1种排法,再,把其余4四人,依次,插入共有,方法,4*5*6*7,定序问题可以用缩,倍,法，还可转化为插,空模型处理,练习题,4,10人身高各不相等,排成前后排，每排5人,要,求从左至右身高逐渐增加，共有多少种排法？,五.多排问题直排策略,例,5.8,人排成前后两排,每排4人,其中甲乙在,前排,丁在后排,共有多少排法,解:8人排前后两排,相当于8人坐8把椅子,可以,把椅子排成一排.,先在前4个位置排甲乙两,个特殊元素有_种,再排后4个位置上的,特殊元素有_种,其余的5人在5个位置,上任意排列有_种,则共有_种.,前排,后排,一般地,元素分成多排的排列问题,可归结为一排考虑,再分段研究,.,10名学生分坐两行，要求面对面坐下，但其中甲乙两位同学不可相邻也不可面对面，有多少种坐法？,练习题,5,共有,(1),甲在两端：,(2),甲不在两端：,六.排列组合混合问题先选后排策略,例,6.,有5个,不同,的小球,装入4个不同的盒内,每盒至少装一个球,共有多少不同的装,法.,解:第一步从5个球中选出2个组成复合元共,有_种方法.再把5个元素(包含一个复合,元素)装入4个不同的盒内有_种方法.,根据分步计数原理装球的方法共有_,解决排列组合混合问题,先选后排是最基本,的指导思想.,练习题,6,某种产品有,4,只次品和,6,只正品，每只均不,同且可区分，今每次取出一只测试，直到,4,只次品全部测出为止，则最后一只次品恰,好在第五次测试中被发现的不同情况有多少种？,七.相同元素分配问题隔板策略,例,7.,有10个三好学生名额，分给7个班，每,班至少一个,有多少种分配方案？,解：因为10个名额,没有差别,，把它们排成,一排。相邻名额之间形成个空隙。,在个空档中选个位置插个隔板，,可把名额分成份，对应地分给个,班级，每一种插板方法对应一种分法,共有_种分法。,一班,二班,三班,四班,五班,六班,七班,将,n,个相同的元素分成,m,份（,n，m,为正整数）,每份至少一个元素,可以用,m-1,块隔板，插入,n,个元素排成一排的,n-1,个空隙中，所有分法数为,练习题,7,有编号为,1,、,2,、,3,的,3,个盒子和,10,个相同的小球，现把这,10,个小球全部装入,3,个盒子中，使得每个盒子所装球数不小于盒子的编号数，这种装法共有多少种,?,八,.,正难则反间接法,例,8.四面体的顶点和各棱中点共10个点，,从中取4个不共面的点，不同的取法有,多少种？,取出的4点不共面情形复杂，故采用间接法。取出的4点共面有三类：,（1）过四面体的一个面有 种；,（2）过四面体的一条棱上的三个点和对棱,的中点的平面有6种；,（3）,过四面体的四条棱的中点且与另两条棱平,行的平面有3种；,故取4个不共面的点有,以一个正方体的顶点为顶点，能组成多少个不同的四面体？,练习8,解排列组合题的常用方法,6.,排列组合混合题,先选后排法,1.,特殊元素优先考虑,2.,不相邻问题,插空,法,3.,相邻问题,捆绑法,4.,定序问题,缩倍法,5.,多排问题,直排法,7.,相同元素分配问题,隔板法,8,.,正难则反,间接法,练习1.,（,1,）,6,本不同的书分给,5,名同学每,人一本，有多少种不同分法？,（,2,）,5,本相同的书分给,6,名同学每人至,多一本，有多少种不同的分法？,（,3,）,6,本不同的书全部分给,5,名,同学每人至少一本，有多,少种不同的分法？,1.分配问题,捆绑法,第2课时 排列组合综合应用,练习1,（,5,）,6,本不同的书分给甲、乙、丙,3,名同学,每人,两,本，有多少种不同分法？,（,4,）,6,本不同的书分给,3,名同学，甲,1,本、乙,2,本、丙,3,本，有多少种不同的分法？,分配问题,捆绑法,练习1,（,6,）,8,本不同的书分给,3,名同学，其中,1,名同,学,2,本、另两人,3,本，有多少种不同分法？,分配问题,练习1,（,7,）,7,名志愿者中安排,6,人在周六、周日两天参加社会公益活动，若每天安排,3,人，者有多少种不同的安排方法？,分配问题,练习1：,（,8,）将,5,名实习教师分配到高一年级的,3,个班实习，每个班至少,1,名，最多,2,名，则不同的分配方案有多少？,分配问题,练习2：,（,1,）,7,个,相同,的小球，任意放入,4,个不同的盒子中，共有多少种不同的方法？,分配问题,解：,相当于将,7,个小球用,3,块隔板分成,4,份,隔板法,练习2：,（,2,）,7,个,相同,的小球，任意放入,4,个不同的盒子中，每个盒子,至少,有,1,个小球的不同放法有多少种？,分配问题,解：,将,7,个小球用,3,块隔板分,成,4,份但盒子又不能空,隔板法,练习3：四面体的一个顶点是,A,，从其它顶点和各棱中点中取,3,个点，使他们和点,A,在同一个平面上，则共有多少种不同的取法？,2.组图形问题,练习4：用正方体的,8,个顶点共可以组成多少个不同的四面体？,2.组图形问题,练习5：,10,双不相同的鞋子混装在一只口袋中，从中任取,4,只，试求符合下列各种情形的方法数？,先成双后成单,（,1,）,4,只鞋子恰成两双；,(2)4,只鞋子没有成双；,(,3,)4,只鞋子恰有2只成双；,练习6：,8,名外交工作者，其中,3,人只会英语，,2,人只会日语，,3,人既会英语又会日语，现从则,8,人中选,3,个会英语，,3,个会日语的人去完成一项任务，有多少种不同的选法？,3.选人问题,例,10,：给下面的,5,个行政区域涂色，要求相邻区域不同色，现有,4,种颜色可供选择，问共有多少种不同的涂色方案？,4.涂色问题,2,3,1,5,4,练习7,：用,4,种颜色给下面的,5,个行政区域涂色，要求相邻区域不同色，问共有多少种不同的涂色方案？,练习8：,6,本不同的书分给甲、乙、丙三人，每人至少一本，有多少种不同的分法？,5.综合问题,练习9：从,5,男,3,女中选,5,人担任,5,门不同学科的课代表，求符合下列条件的不同选法？,5综合问题,（,1,）有女生担人数必须少于男生；,（,2,）男生只能担任数学化学物理课代表；,练习10：,3,张卡片正反面分别写着数字,0,与,1,、,3,与,4,、,5,与,6,，将三张卡片并排组成三位数，共可以组成多少个不同的三位数？,5综合问题,