Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,解排列组合问题的十六种常用策略,第一页，共36页。,三,.,特殊元素和特殊位置优先策略,四,.,相邻元素捆绑策略,五,.,不相邻问题插空策略,六,.,定序问题空位插入策略,七,.,重排问题求幂策略,八,.,多排问题直排策略,九,.,排列组合混合问题先选后排策略,十,.,小集团问题先整体后局部策略,十一,.,元素相同问题隔板策略,二,.,正难则反总体淘汰策略,十二,.,平均分组问题除法策略,一合理分类与准确分步策略,十三,.,构造模型策略,十四,.,实际操作穷举策略,十五,.,分解与合成策略,十六,.,化归策略,解排列组合问题的十六种常用策略,第二页，共36页。,一,.,合理分类与分步策略,例,13.,在一次演唱会上共,10,名演员,其中,8,人能,唱歌,5,人会跳舞,现要演出一个,2,人,唱歌,2,人伴舞的节目,有多少选派方法,?,解：,10,演员中有,5,人只会唱歌，,2,人只会跳舞,3,人为全能演员。,以只会唱歌的,5,人是否,选上唱歌为标准进行分类,.,只会唱歌,的,5,人中没有人选上唱歌共有,_,种,只会唱的,5,人中只有,1,人选上唱歌,_,种,只会唱的,5,人中只有,2,人,选上唱歌有,_,种，由分类计数原理,共有,_,种。,+,+,第三页，共36页。,本题还有如下分类标准：,*,以,3,个全能演员是否选上唱歌人员为标准,*,以,3,个全能演员是否选上跳舞人员为标准,*,以只会跳舞的,2,人是否选上跳舞人员为标准,都可经得到正确结果,解含有约束条件的排列组合问题，可按元素,的性质进行分类，按事件发生的连续过程分,步，做到标准明确。分步层次清楚，不重不,漏，分类标准一旦确定要贯穿于解题过程的,始终。,第四页，共36页。,练习题,例：,3,成人,2,小孩乘船游玩,A,号船最多乘,3,人,B,号船最多乘,2,人,C,号船只能乘,1,人,他们任选,2,只船或,3,只船,但小孩不能单独乘一只船,这,3,人共有多少乘船方法,.,首先人数可以有以下分配,A3,B2,C0,；,A3,B1,C1,；,A2,B2,C1,分情况讨论,A3,B2,C0,所有可能 减去小孩独乘的可能,(,只有一种就是两个小孩都在,B,上,),种乘法,A2,B2,C1,首先,A,、,B,、,C,上肯定都有一个大人，所以有,种乘法,A3,B1,C1 BC,上肯定都是一个大人 ，剩下一个大人和两个小孩乘,A,没得选：种乘法,共计：,9+6+12=27,种乘座方法。,第五页，共36页。,二,.,正难则反总体淘汰策略,例,11.,从,0,1,2,3,4,5,6,7,8,9,这十个数字中取出三,个数，使其和为不小于,10,的偶数,不同的,取法有多少种？,解：这问题中如果直接求不小于,10,的偶数很,困难,可用总体淘汰法。,这十个数字中有,5,个偶数,5,个奇数,所取的三个数含有,3,个偶数的取法有,_,只含有,1,个偶数的取法有,_,和为偶数的取法共有,_,再淘汰和小于,10,的偶数共,_,符合条件的取法共有,_,9,013,015,017,035,213,215,024,413,026,+,-9,+,有些排列组合问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中淘汰,.,第六页，共36页。,1.,某班里有,43,位同学,从中任抽,3,人,正、,副班长、团支部书记至少有一人在内的,抽法有多少种,?,练习题,2.,从,4,名男生和,3,名女生中选出,4,人参加某个座 谈会，若这,4,人中必须既有男生又有女生，则不同的选法共有,_,第七页，共36页。,三,.,特殊元素和特殊位置优先策略,例,1.,由,0,1,2,3,4,5,可以组成多少个没有重复数字,五位奇数,.,解,:,由于末位和首位有特殊要求,应该优先安,排,以免不合要求的元素占了这两个位置,先排末位共有,_,然后排首位共有,_,最后排其它位置共有,_,由分步计数原理得,=288,第八页，共36页。,7,种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？,练习题,第九页，共36页。,四,.,相邻元素捆绑策略,例,2.7,人站成一排,其中甲乙相邻且丙丁相,邻,共有多少种不同的排法,.,甲,乙,丙,丁,由分步计数原理可得共有,种不同的排法,=480,解：可先将甲乙两元素捆绑成整体并看成,一个复合元素，同时丙丁也看成一个,复合元素，再与其它元素进行排列，,同时对相邻元素内部进行自排。,要求某几个元素必须排在一起的问题,可以用,捆绑法来解决问题,.,即将需要相邻的元素合并,为一个元素,再与其它元素一起作排列,同时,要注意合并元素内部也必须排列,.,第十页，共36页。,五,.,不相邻问题插空策略,例,3.,一个晚会的节目有,4,个舞蹈,2,个相声,3,个,独唱,舞蹈节目不能连续出场,则节目的出,场顺序有多少种？,解,:,分两步进行第一步排,2,个相声和,3,个独唱共,有,种，,第二步将,4,舞蹈插入第一步排,好的,5,个元素中间包含首尾两个空位共有,种,不同的方法,由分步计数原理,节目的,不同顺序共有,种,相,相,独,独,独,元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端,第十一页，共36页。,某班新年联欢会原定的,5,个节目已排成节目单，开演前又增加了两个新节目,.,如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为（）,练习题,某人射击,8,枪，命中,4,枪，,4,枪命中恰好有,3,枪连在一起的情形的不同种数为（）,第十二页，共36页。,六,.,定序问题空位插入策略,例人排队,其中甲乙丙,3,人顺序一定共有多,少不同的排法,解,:,（,空位法,）设想有,7,把椅子让除甲乙丙以外,的四人就坐共有,种方法，其余的三个,位置甲乙丙共有,种坐法，则共有,种,方法,1,第十三页，共36页。,（,插入法,),先排甲乙丙三个人,共有,1,种排法,再,把其余,4,四人,依次,插入共有,方法,练习题,10,人身高各不相等,排成前后排，每排,5,人,要,求从左至右身高逐渐增加，共有多少排法？,4*5*6*7,第十四页，共36页。,七,.,重排问题求幂策略,例,5.,把,6,名实习生分配到,7,个车间实习,共有,多少种不同的分法,解,:,完成此事共分六步,:,把第一名实习生分配,到车间有,种分法,.,7,把第二名实习生分配,到车间也有,7,种分法，,依此类推,由分步计,数原理共有 种不同的排法,允许重复的排列问题的特点是以元素为研究,对象，元素不受位置的约束，可以逐一安排,各个元素的位置，一般地,n,不同的元素没有限,制地安排在,m,个位置上的排列数为 种,n,m,第十五页，共36页。,某,8,层大楼一楼电梯上来,8,名乘客,他们,到各自的一层下电梯,下电梯的方法,（）,练习题,第十六页，共36页。,八,.,多排问题直排策略,例人排成前后两排,每排,4,人,其中甲乙在,前排,丁在后排,共有多少排法,解,:8,人排前后两排,相当于,8,人坐,8,把椅子,可以,把椅子排成一排,.,先在前,4,个位置排甲乙两,个特殊元素有,_,种,再排后,4,个位置上的,特殊元素有,_,种,其余的,5,人在,5,个位置,上任意排列有,_,种,则共有,_,种,.,前排,后排,一般地,元素分成多排的排列问题,可归结为一排考虑,再分段研究,.,第十七页，共36页。,九,.,排列组合混合问题先选后排策略,例,8.,有,5,个不同的小球,装入,4,个不同的盒内,每盒至少装一个球,共有多少不同的装,法,.,解,:,第一步从,5,个球中选出,2,个组成复合元共,有,_,种方法,.,再把,5,个元素,(,包含一个复合,元素,),装入,4,个不同的盒内有,_,种方法,.,根据分步计数原理装球的方法共有,_,解决排列组合混合问题,先选后排是最基本,的指导思想,.,此法与,相邻元素捆绑策略相似,吗,?,第十八页，共36页。,练习题,一个班有,6,名战士,其中正副班长各,1,人,现从中选,4,人完成四种不同的任务,每人,完成一种任务,且正副班长有且只有,1,人,参加,则不同的选法有,_,种,第十九页，共36页。,十,.,小集团问题先整体后局部策略,例,9.,用,1,2,3,4,5,组成没有重复数字的五位数,其中恰有两个偶数夹,1,这两个奇数之,间,这样的五位数有多少个？,解：把,当作一个小集团与排队,共有,_,种排法，再排小集团内部共有,_,种排法，由分步计数原理共有,_,种排法,.,3,1245,小集团,小集团排列问题中，先整体后局部，再结合其它策略进行处理。,第二十页，共36页。,.,计划展出,10,幅不同的画,其中,1,幅水彩画,幅油画,幅国画,排成一行陈列,要求同一,品种的必须连在一起，并且水彩画不在两,端，那么共有陈列方式的种数为,_,2.5,男生和女生站成一排照像,男生相邻,女,生也相邻的排法有,_,种,第二十一页，共36页。,十一,.,元素相同问题隔板策略,例,10.,有,10,个运动员名额，在分给,7,个班，每,班至少一个,有多少种分配方案？,解：因为,10,个名额没有差别，把它们排成,一排。相邻名额之间形成个空隙。,在个空档中选个位置插个隔板，,可把名额分成份，对应地分给个,班级，每一种插板方法对应一种分法,共有,_,种分法。,一班,二班,三班,四班,五班,六班,七班,将,n,个相同的元素分成,m,份（,n,，,m,为正整数）,每份至少一个元素,可以用,m-1,块隔板，插入,n,个元素排成一排的,n-1,个空隙中，所有分法数为,第二十二页，共36页。,练习题,10,个相同的球装,5,个盒中,每盒至少一个，有多少装法？,第二十三页，共36页。,十二,.,平均分组问题除法策略,例,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,为均分的组数,),避免重复计数。,第二十四页，共36页。,1,将,13,个球队分成,3,组,一组,5,个队,其它两组,4,个队,有多少分法？,2.,某校高二年级共有六个班级，现从外地转 入,4,名学生，要安排到该年级的两个班级且每班安排,2,名，则不同的安排方案种数为,_,第二十五页，共36页。,十三,.,构造模型策略,例,14.,马路上有编号为,1,2,3,4,5,6,7,8,9,的,九只路灯,现要关掉其中的,3,盏,但不能关,掉相邻的,2,盏或,3,盏,也不能关掉两端的,2,盏,求满足条件的关灯方法有多少种？,解：把此问题当作一个排队模型在,6,盏,亮灯的,5,个空隙中插入,3,个不亮的灯,有,_,种,一些不易理解的排列组合题如果能转化为,非常熟悉的模型，如占位填空模型，排队,模型，装盒模型等，可使问题直观解决,第二十六页，共36页。,练习题,某排共有,10,个座位，若,4,人就坐，每人左右,两边都有空位，那么不同的坐法有多少种？,第二十七页，共36页。,现从中选4人完成四种不同的任务,每人,有 种，,前排,丁在后排,共有多少排法,盏,求满足条件的关灯方法有多少种？,由分步计数原理可得共有,邻,共