有约束条件的排列问题张用.pptx

《有约束条件的排列问题张用.pptx》由会员分享，可在线阅读，更多相关《有约束条件的排列问题张用.pptx（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、以人为标准进行分步，第一名同学有5种选择，第二名同学有5种选择，第三名同学也有5种选择，因此有例2：(1)有5本不同的书，从中选3本送给3名同 学，每人各1本，共有多少种不同的送法？(2)有5种不同的书，买3本送给3名同学，每人各1本，共有多少种不同的送法？有约束条件的排列问题课本例题3第2页/共63页百位十位个位千位万位例4、由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有多少个？有约束条件的排列问题2或41，3或2、4之一第6页/共63页百位十位个位千位万位例4、由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有多少个？有约束条件的

2、排列问题1或3或5百位十位个位千位万位2或45第7页/共63页百位十位个位千位万位例4、由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有多少个？有约束条件的排列问题第8页/共63页例5、6个人站成前后两排照相，要求前排2人，后排4人，那么不同的排法共有（）A.30种B.360种C.720种D.1440种C分排问题直排处理有约束条件的排列问题第9页/共63页例6、有4个男生和3个女生排成一排，按下列要求各有多少种不同排法：（1）男甲排在正中间；特殊元素（位置）优先法有约束条件的排列问题第10页/共63页例6、有4个男生和3个女生排成一排，按下列要求各有多少种不同排法

3、：（2）男甲不在排头，女乙不在排尾；女乙在排头时：女乙不在排头时：所以共有：720+3000=3720种。有约束条件的排列问题女乙不甲乙55第11页/共63页例6、有4个男生和3个女生排成一排，按下列要求各有多少种不同排法：（2）男甲不在排头，女乙不在排尾；有约束条件的排列问题间接法：第12页/共63页例6、有4个男生和3个女生排成一排，按下列要求各有多少种不同排法：（3）三个女生排在一起；相邻问题“捆绑法”有约束条件的排列问题第13页/共63页例6、有4个男生和3个女生排成一排，按下列要求各有多少种不同排法：（4）三个女生两两都不相邻；不相邻问题“插空法”有约束条件的排列问题第14页/共63

4、页例6、有4个男生和3个女生排成一排，按下列要求各有多少种不同排法：（5）全体站成一排，甲、乙、丙三人自左向右顺序不变；定序问题“消序法”有约束条件的排列问题定序问题“插空法”第15页/共63页例6、有4个男生和3个女生排成一排，按下列要求各有多少种不同排法：（6）若甲必须在乙的右边（可以相邻，也可以不相邻），有多少种站法？有约束条件的排列问题定序问题“消序法”定序问题“插空法”第16页/共63页例7、7位同学站成一排，共有多少种不同的排法？解：问题可以看作：7个元素的全排列A7750407位同学站成一排，其中甲站在中间的位置，共有多少种不同的排法？解：问题可以看作：余下的6个元素的全排列A6

5、6=720有约束条件的排列问题第17页/共63页7位同学站成一排，其中甲不站在首位，共有多少种不同的排法？解一：甲站其余六个位置之一有A61种，其余6人全排列有A66种，共有A61A66=4320。解二：从其他6人中先选出一人站首位，有A61，剩下6人（含甲）全排列，有A66，共有A61A66=4320。解三：7人全排列有A77，甲在首位的有A66，所以共有A77-A66=7A66-A66=4320。有约束条件的排列问题第18页/共63页（4）7位同学站成一排甲、乙只能站在两端的排法共有多少种？解：根据分步计数原理：第一步甲、乙站在两端有A22种；第二步余下的5名同学进行全排列有A55种则共有

6、A22A55=240种排列方法.甲乙乙甲abcdeebdcaA55A55A22A22有约束条件的排列问题第19页/共63页（5）7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？解：第一步从（除去甲、乙）其余的5位同学中选2位同学站在排头和排尾有A52种方法；第二步从余下的5位同学中选5位进行排列（全排列）有A55种方法，所以一共有A52A552400种排列方法有约束条件的排列问题间接法第20页/共63页（6）若甲不在排头、乙不在排尾,有多少种不同的排法？解法一（直接法）：以 甲作为分类标准,分为两类：第 一 类：先 安 排 甲 在 中 间,再 安 排 乙,有第二类：先安排甲在排尾,

7、再安排其他人,有共有：3720种方法有约束条件的排列问题直接法第21页/共63页解法二（间接法）：所有排法中除去不符合的.共 有：3720种 方 法 所有排法：甲在排头：乙在排尾：甲在排头、乙在排尾：有约束条件的排列问题间接法第22页/共63页例8、四位男生、三位女生排队照相，根据下列要求，各有多少不同的排法（1）七个人排一列，四个男生必须连排在一起有约束条件的排列问题（1 1）捆绑法：四个男生看作一个元素和三个女生共四）捆绑法：四个男生看作一个元素和三个女生共四个元素有个元素有A A4 44 4种排法种排法,四个男生全排列有四个男生全排列有A A4 44 4 种排法种排法由乘法原理共有由乘法

8、原理共有第23页/共63页例8、四位男生、三位女生排队照相，根据下列要求，各有多少不同的排法（2）男女生相间排列有约束条件的排列问题 男女男女男女男 共有A44 A33=144第24页/共63页例9、将5列车停在5条不同的轨道上，其中a列车不停在第一轨道上，b列车不停在第二轨道上，那么不同的停放方法有（）（A）120种 （B）96种 （C）78种 （D）72种 特殊元素（或位置）优先安排B第25页/共63页先算出5列火车排5条铁轨的排法，然后扣除掉A列车停在第一轨道上的方法总数，再扣除掉B列车停在第二轨道上的方法总数，再加上前面重复扣除的既满足A列车停在第一轨道上、又满足B列车停在第二轨道上的

9、方法总数，就是所求的不同的停放方法。例9、将5列车停在5条不同的轨道上，其中a列车不停在第一轨道上，b列车不停在第二轨道上，那么不同的停放方法有（）（A）120种 （B）96种 （C）78种 （D）72种 特殊元素（或位置）优先安排解法2：第26页/共63页第27页/共63页第28页/共63页不相邻问题“插空法”第29页/共63页不相邻问题“插空法”、捆绑法第30页/共63页七人排成一排，甲、乙两人必须相邻，且甲、乙都不与丙相邻，则不同的排法有（）种(A)960种（B）840种 C）720种 （D）600种“相邻”用“捆绑”，“不邻”就“插空”第31页/共63页从7盆不同的盆花中选出5盆摆放在

10、主席台前，其中有两盆花不宜摆放在正中间，则一共有_种不同的摆放方法。第32页/共63页例8：一天要排语、数、英、体、班会六节课，要求上午的四节课中，第一节不排体育课，数学排在上午；下午两节中有一节排班会课，问共有多少种不同的排法？分析：共是6节课讨论）上午第一节不能是体育、班会，则第一节就有4种可能第二节开始不能是班会，减去前面一节，还有4种第三节减去2节+班会,有3种可能第四节减去3节+班会,有2种可能第5节（早上排了4节了），下午：剩下一节跟班会有2种可能，第6节全部排好了就一节课1种可能。共443221=192；有约束条件的排列问题数、班在下午全排体排在上午第一节外的某节剩下的全排第34

11、页/共63页法一）1）当体育课被安排在下午，则在除班会以外的四节课在上午可以随便安排，共有 种可能，再有下午的体育和班会共有 =2种排法，所以共有 =48种方法。2）当体育课被安排在上午，则在除班会以外的四节课中必须选出一门课与班会一起被安排在下午，共有 种排法。在余下的三门课与体育课共四节被安排在上午：上午第一节有3种选法，第二节有3种选法，第三节有2种选法，第四节有1种选法。即 =3321种。共有（）.（）=144种。由1）2）共48+144=192，而数在下午有36种；综上：有48+144-36=156种。法二）数在上午其它三节中的一节第一节排（除数、体、班）其它三门课中的一门剩下三门课

12、中选一门与班会放在下午两节全排最后的两门课无限制全排分析：共是6节课综上：48+108=156.第35页/共63页3：三名女生和五名男生排成一排，如果女生全排在一起，有多少种不同排法？如果女生全分开，有多少种不同排法？如果两端都不能排女生，有多少种不同排法？如果两端不能都排女生，有多少种不同排法？A66A33=4320A55A63=14400A52A66=14400A52A66+2A31A51A66=36000或A88-A32A66=36000第36页/共63页练习：某小组7人排队照相，以下各有几种不同的排法？1）若排成两排，前排3人，后排4人；2）若排成两排，前排3人，后排4人，甲必排在前排

13、，乙必排在后排；3）甲不在左端，乙不在右端；4）甲乙不相邻；5）甲、乙、丙均不相邻；6）甲乙必须间隔2人；第37页/共63页小结：1对有约束条件的排列问题，应注意如下类型：某些元素不能在或必须排列在某一位置；某些元素要求连排（即必须相邻）；某些元素要求分离（即不能相邻）；某些元素要求顺序一定；2基本的解题方法：（）有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）法（优先法）；特殊元素,特殊位置优先安排策略第38页/共63页（）某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列，这种方法称为“捆绑法”；相邻问

14、题捆绑处理的策略（）某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空挡，这种方法称为“插空法”；不相邻问题插空处理的策略（4）某些元素顺序一定时，可以用总排列数除以这几个元素的全排列数，这种方法称为“倍除法”；定序问题倍除处理的策略第39页/共63页第40页/共63页第41页/共63页练）课本P27页4、5、6、7；第42页/共63页第43页/共63页第44页/共63页第45页/共63页思：某排共有10个座位,若4人就坐,每人左右两边都有空位,那么不同做法有多少种?分析：4人选位A（44）=24,然后4人旁边插空需5个空位,剩余的1个任意放在这5个空中的一个即5种，共24*5=

15、120。另析：两端的座位要空着，中间4个位包括两端共有5个空，4人插入5空中，共A（54）=120。第46页/共63页1：有4个男生和3个女生排成一排，按下列要求各有多少种不同排法：（3）甲、乙两同学必须相邻，而且丙不能站在排头和排尾？（4）若甲、乙两名女生相邻，且不与第三名女生相邻？（1）7位同学站成一排，甲、乙只能站在两端？（2）7位同学站成一排，甲、乙不能站在两端？（5）甲、乙、丙3名同学必须相邻，而且要求乙、丙分别站 在甲的两边？第47页/共63页3、1）因为a不等于0，先确定a，有A(4,1)=4；然后从剩下4个数中选2个，有A(4,2)=43=12，故可以组成412=48个不同的一

16、元二次方程。2）(1)c=0时，方程总有解，A(4,2)=43=12；(2)c不等于0，b=0时，方程总无解；(3)a，b，c均不为0时，满足b2-4*a*c大于等于0，才有解,只有：52-4*1*3，52-4*3*1，72-4*1*3，72-4*1*5，共6种可能，所以有实数解的方程有12+6=18个变式：只有当直线是Y=-AX/B才有18条，分别是A=0,或B=0时2条，其余的即A、B取非0数时Y=-AX/B;共4*5=20种组合。由于1/2=3/6;1/3=2/6;2/1=6/3;3/1=6/2。减去重复的四种，答案：2+20-4=18。第48页/共63页一、无限制条件的排列问题1.从5

17、种不同的蔬菜种子中选3种分别种在3块不同土质的土地上，共有多少种不同的种法？分析：把5个种子分别标上1,2,3,4,5,用123表示种子1种在第1块土地上，种子2种在第2块土地上，种子3种在第3块土地上，因此3个数的一个排列就是一种种植方法，从5个不同数中取出3个数的一个排列就是一种种植方法，多少个排列就有多少种种法。第49页/共63页2.公共汽车上有4位乘客，其中任何两个人都不在同一车站下车，汽车沿途停靠6个站，那么这4位乘客不同的下车方法有多少种？分析：个车站分别标上1,2,3,4,5,6,如1246表示第一位乘客在1号站下，第二位乘客在2号站下，第三位乘客在4号站下，第四位乘客在6号车站

18、下，不同的排列表示不同的下法，有多少个不同的排列就有多少种不同的下法，共有A46=6543=360第50页/共63页5.某信号兵用红、黄、蓝3面旗从上到下挂在竖直的旗杆上表示信号,每次可以任挂1面,2面或3面,并且不同的顺序表示不同的信号,一共可以表示多少种不同的信号？第51页/共63页例2.用0,1,2,3,4,5可组成多少个无重复数字的1)五位数2)六位偶数3)大于213045的自然数1)解1.位置分析法：首位是特殊位置，0不能排，有5种排法，其余4个位置有A45种排法，由乘法原理知共有5 A45=55432=600第52页/共63页解2.（间接法）6个数中取5个数的排列中有不满足要求的数

19、如02134等，0这样的数共有A56-A45=6002)可分为两类，第一类是个位为0的有A55个，第二类个位不是0,个位有两种排法，首位有4种排法，中间四位有A44种排法，第二类共有24A44=192,由加法原理共有A55+192=312第53页/共63页形如2134,2135的数有A12A22形如21054有一个因此满足要求的数共有449个3)形如3,4,5,这样的数都是满足条件的数共有A13A55 形如 23，24，25这样的数都是满足条件的数共有A13A44形如214,215这样的数都是满足条件的数共有A12A33第54页/共63页解：连续命中的3枪和命中的另一枪被未命中的4枪所隔开，如

20、图表示没有命中，_命中的三枪看作一个元素和另外命中的一枪共两个元素插到五个空档中有A25=54=20种排法2.某人射击8枪，命中4枪，4枪命种恰好3枪连在一起的不同种数有多少？第55页/共63页 3.一排8个座位，3人去坐，每人两边至少有一个空座的坐法有多少种？4、一排长椅上共有10个座位，现有4人就座，恰有五个连续空位的坐法种数为。（用数字作答）480第56页/共63页解法二：可以画一个树状图，知满足要求的拿法 有9种（四)其他问题同室4名学生各写一张贺卡，放在一起，然后各人从中各拿一张，但均不能拿自己写的那张，共有多少种拿法？解法一：第一步第一个同学从中拿一张贺卡，满足要求的拿法有3种，第

21、二步考虑被第一个同学拿走贺卡的那个同学也有3种拿法，第三步、第四步各有一种拿法，由乘法原理共有3311=9第57页/共63页1.四位男生、三位女生排队照相，根据下列要求，各有多少不同的排法七个人排一列，三个女生任何两个都不能相邻排在一起七个人排一列，四个男生必须连排在一起男女生相间排列 巩固练习第58页/共63页 男女男女男女男 共有A44 A35=144插空法：先排四个男生共有插空法：先排四个男生共有A A4 44 4种排法种排法_X_X_X_X _X_X_X_X _ 在五个空挡中选出三个空档插进去三个女生有在五个空挡中选出三个空档插进去三个女生有A A3 35 5种排法种排法由乘法原理解共

22、有由乘法原理解共有A A4 44 4 A A3 35 5=1440=1440捆绑法：四个男生看作一个元素和三个女生共四个元素捆绑法：四个男生看作一个元素和三个女生共四个元素有有A A4 44 4种排法种排法,四个男生全排列有四个男生全排列有A A4 44 4 种排法种排法由乘法原理共有由乘法原理共有A A4 44 4 A A4 44 4=576=576第59页/共63页2.7人排成一排，（1）甲、乙和丙三个同学都相邻的排法共有多少种？解：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的5个元素中选取2个元素放在排头和排尾，有A52种方法；

23、将剩下的4个元素进行全排列有A44种方法；最后将甲、乙两个同学“松绑”进行排列有A22种方法所以这样的排法一共有A52A44A22960种方法（2）甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？一共有A55A33720种第60页/共63页某些元素不能在或必须排列在某一位置；某些元素要求连排（即必须相邻）；某些元素要求分离（即不能相邻）；某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列，这种方法称为“捆绑法”；某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空挡，这种方法称为“插空法”。有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）法“优限法”；2基本的解题方法：1对有约束条件的排列问题，应注意如下类型：小结：第61页/共63页创新练习某班8运动员在运动会后排成一排照像留念，（1）若甲乙两人之间必须间隔一人，有多少种不同排法？（2）若甲乙两人之间至少间隔两人，有多少种不同排法？第62页/共63页谢谢您的观看！第63页/共63页