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

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