排列组合相邻相间专题讲解.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,排列组合相邻相间专题讲解,相邻元素捆绑策略,例.7人站成一排,其中甲乙相邻且丙丁相,邻,共有多少种不同的排法.,甲,乙,丙,丁,由分步计数原理可得共有,种不同的排法,=480,解：可先将甲乙两元素捆绑成整体并看成,一个复合元素，同时丙丁也看成一个,复合元素，再与其它元素进行排列，,同时对相邻元素内部进行自排。,要求某几个元素必须排在一起的问题,可以用,捆绑法来解决问题.即将需要相邻的元素合并,为一个元素,再与其它元素一起作排列,同时,要注意合并元素内部也必须排列,.,回目录,例,5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法?,解,因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法.,结论,捆绑法:,要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列.,分析,此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题.,回目录,某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为（）,练习题,20,回目录,有8本互不相同的书,其中数学书3本,外文书2本,其他书3本.若将这些书排成一列放在书架上,则数学书恰好排在一起,外文书也恰好排在一起的排法共有_ 种(结果用数 值表示).,回目录,不相邻问题插空策略,例3.一个晚会的节目有4个舞蹈,2个相声,3个,独唱,舞蹈节目不能连续出场,则节目的出,场顺序有多少种？,解:分两步进行第一步排2个相声和3个独唱共,有,种，,第二步将4舞蹈插入第一步排,好的6个元素中间包含首尾两个空位共有,种,不同的方法,由分步计数原理,节目的,不同顺序共有,种,相,相,独,独,独,元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端,回目录,不相邻问题插空法,对于某几个元素不相邻得排列问题，可先将其它,元素排好，然后再将不相邻的元素在已排好的元素,之间及两端的空隙之间插入即可。,例5 7人站成一排照相，要求甲，乙，丙三人不相邻，分别有多少种站法？,分析：可先让其余4人站好，共有 种排法，再在这4人之间及两端的5个“空隙”中选三个位置让甲、乙、丙插入，则有 种方法，这样共有 种不同的排法。,回目录,某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为（）,30,练习题,回目录,（1）三个男生，四个女生排成一排，男生、女生各站一起，有几种不同方法？,（2）,三个男生，四个女生排成一排，,男生之间、女生之间不相邻，有几种不同排法？,捆绑法：,插空法：,（3）,(2005 辽宁)用、,组成没有重复数字的八位数，要求与相邻，与相邻，与相邻，而与不相邻，这样的八位数共有_个（用数字作答）,练 习,回目录,(3)(2005 辽宁)用、,组成没有重复数字的八位数，要求与相邻，,与相邻，与相邻，而与不相邻，,这样的八位数共有_个（用数字作答）,将与，与，与捆绑在一起排成一列,有 种，再将、插入4个空位中的两个,有 种，故有 种,引申:用、组成没有重复数字,的六位数，要求与相邻，与相邻，与,相邻，现将7、8 插进去，仍要求与相邻，与,相邻，与相邻，那么插法共有_种,（用数字作答）,回目录,“相邻”用“捆绑”，“不邻”就“插空”,例 七人排成一排，甲、乙两人必须相邻，且甲、乙都不与丙相邻，则不同的排法有（）种,960种 （B）840种 （C）720种 （D）600种,解：,另解：,回目录,练习,某城新建的一条道路上有12只路灯，为了节省用电而不影响正常的照明，可以熄灭其中三盏灯，但两端的灯不能熄灭，也不能熄灭相邻的两盏灯，可以熄灭的方法共有（）,（A）种（B）种（C）种（D）种,解：,回目录,例,学校组织老师学生一起看电影，同一排电影票12张。8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的坐法？,解,先排学生共有 种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有 种选法.根据乘法原理,共有的不同坐法为 种.,结论,插入法:,对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.,分析,此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就要特殊对待.所涉及问题是排列问题.,回目录,小结：,以元素相邻为附加条件的应把相邻元素视为一个整体，即采用“捆绑法”；以某些元素不能相邻为附加条件的,可采用“插空法”。“插空”有同时“插空”和有逐一“插空”,并要注意条件的限定.,回目录,重排问题求幂策略,例.把6名实习生分配到7个车间实习,共有,多少种不同的分法,解:完成此事共分六步:把第一名实习生分配,到车间有,种分法.,7,把第二名实习生分配,到车间也有7种分,法，,依此类推,由分步计,数原理共有 种不同的排法,允许重复的排列问题的特点是以元素为研究,对象，元素不受位置的约束，可以逐一安排,各个元素的位置，一般地n个不同的元素没有限,制地安排在m个位置上的排列数为 种,n,m,回目录,