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