排列(优限法、捆绑法、插空法的运用-).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,排列的简单应用,2,排列的简单应用,目的：,理解掌握含有特殊限制条件的排队问题的解决方法，进一步培养分析问题、解决问题的能力,重点：,优限法、捆绑法、插空法的运用,3,一、【概念复习】,：,1,排列的定义,，理解排列定义需要注意的几点问题；,从n个不同元素中，任取m(m,n,)个元素（这里的被取元素各不相同）按照,一定的顺序,排成一列，叫做,从n个不同元素中取出m个,元素的,一个排列.,2,排列数的定义，排列数的计算公式,4,3练习：7位同学站成一排，共有多少种不同的排法？,解：问题可以看作：7个元素的全排列A,7,7,5040,7位同学站成一排，其中甲站在中间的位置，共有多少种不同的排法？,解：问题可以看作：余下的6个元素的全排列A,6,6,=720,7位同学站成一排，其中甲不站在首位，共有多少种不同的排法？,解一：甲站其余六个位置之一有A,6,1,种，其余6人全排列有A,6,6,种，共有A,6,1,A,6,6,=4320。,解二：从其他6人中先选出一人站首位，有A,6,1,，剩下6人（含甲）全排列，有A,6,6,，共有A,6,1,A,6,6,=4320。,解三：7人全排列有,A,7,7,，甲在首位的有A,6,6,，所以共有 A,7,7,-A,6,6,=7 A,6,6,-A,6,6,=4320。,5,二、新课,：,例：,7位同学站成一排,甲、乙只能站在两端的排法共有多少种？,解：根据分步计数原理：第一步 甲、乙站在两端有,A,2,2,种；第二步 余下的5名同学进行全排列有,A,5,5,种 则共有,A,2,2,A,5,5,=240,种排列方法,甲,乙,乙,甲,a,b,c,d,e,e,b,d,c,a,A,5,5,A,5,5,A,2,2,A,2,2,6,甲、乙不能站在排头和排尾的排法共有多少种？,解法一：第一步 从（除去甲、乙）其余的5位同学中选2位同学站在排头和排尾有,A,5,2,种方法；第二步 从余下的5位同学中选5位进行排列（全排列）有,A,5,5,种方法，所以一共有,A,5,2,A,5,5,2400,种排列方法,解法二：若甲站在排头有,A,6,6,种方法；若乙站在排尾有,A,6,6,种方法；若甲站在排头且乙站在排尾则有,A,5,5,种方法所以甲不能站在排头，乙不能排在排尾的排法共有,A,7,7,2 A,6,6,A,5,5,=2400,种,小 结一：,对于“,在,”与“,不在,”等,有,特殊元素或特殊位置,的排列问题，通常是,先排特殊元素或特殊位置,，称为,优先处理特殊元素（位置）法,（,优限法,）。,优限法,7,甲、乙两同学必须,相邻,的排法共有多少种？,解：先将甲、乙两位同学“,捆绑,”在一起看成一个元素与其余的5个元素（同学）一起进行全排列有,A,6,6,种方法；再将甲、乙两个同学“松绑”进行排列有,A,2,2,种方法所以这样的排法一共有,A,6,6,A,2,2,1440种,拓展：甲、乙和丙三个同学都相邻的排法共有多少种？,解：方法同上，一共有,A,5,5,A,3,3,720种,解法一：将甲、乙两同学“,捆绑,”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的5个元素中选取2个元素放在排头和排尾，有,A,5,2,种方法；将剩下的4个元素进行全排列有,A,4,4,种方法；最后将甲、乙两个同学“,松绑,”进行排列有,A,2,2,种方法所以这样的排法一共有,A,5,2,A,4,4,A,2,2,960种方法,甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？,8,解法二：,将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，若丙站在排头或排尾有,2A,5,5,种方法，所以丙不能站在排头和排尾的排法有,（,A,6,6,-2A,5,5,）,A,2,2,=960,种方法,小结二：,对于相邻问题，常用“,捆绑法,”（,先捆后松,）,解法三,：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的四个位置选择共有,A,4,1,种方法，,再将其余的5个元素进行全排列共有,A,5,5,种方法，最后将甲、乙两同学“松绑”，所以这样的排法一共有,A,4,1,A,5,5,A,2,2,960种方法,捆绑法,9,甲、乙两同学,不能相邻,的排法共有多少种？,解法一：,（,排除法,）,A,7,7,-A,6,6,A,2,2,=3600,解法二：,（,插空法,）先将其余五个同学排好有,A,5,5,种方法，此时他们留下六个位置（就称为“,空,”），再将甲、乙同学分别插入这六个位置（,空,）有,A,6,2,种方法，,c,b,a,d,e,所以一共有,A,5,5,A,6,2,=3600,种方法,乙,甲,10,拓展：,甲、乙和丙三个同学都,不能相邻,的排法共有多少种？,解：先将,其余四个,同学排好有,A,4,4,种方法，此时他们留下五个“,空,”，再将甲、乙和丙三个同学分别插入这,五个“空”,有,A,5,3,种方法，所以一共有,A,4,4,A,5,3,1440,种,小结三,：,对于,不相邻,问题，常用“,插空法,”（,特殊元素,后,考虑,）,插空法,11,三、练习：,三名女生和五名男生排成一排，,如果女生,全排在一起,，有多少种不同排法？,如果女生,全分开,，有多少种不同排法？,如果两端,都不能,排女生，有多少种不同排法？,如果两端,不能都,排女生，有多少种不同排法？,A,6,6,A,3,3,=4320,A,5,5,A,6,3,=14400,A,5,2,A,6,6,=14400,A,5,2,A,6,6,+2A,3,1,A,5,1,A,6,6,=36000,或,A,8,8,-A,3,2,A,6,6,=36000,12,某些元素,不能在或必须排列在,某一位置；,某些元素要求,连排（即必须相邻）,；,某些元素要求,分离（即不能相邻）,；,某些元素要求,必须相邻,时，可以先将这些元素,看作一个,元素，,与其他,元素排列后，,再考虑,相邻元素的,内部,排列，这种方法称为“,捆绑法,”；,某些元素,不相邻,排列时，可以,先排其他,元素，再将这些,不相邻,元素,插入空挡,，这种方法称为“,插空法,”。,有,特殊元素或特殊位置,的排列问题，通常是,先排特殊元素或特殊位置,，称为,优先处理特殊元素（位置）法,“,优限法”,；,2,基本的,解题方法,：,1对有,约束条件的排列问题,，应注意如下类型：,四、小结：,13,创新练习,某班8运动员在运动会后排成一排照像留念，,（1）若甲乙两人之间必须间隔一人，有多少种不同排法？,（2）若甲乙两人之间至少间隔两人，有多少种不同排法？,14,