排列组合的应用.pptx

《排列组合的应用.pptx》由会员分享，可在线阅读，更多相关《排列组合的应用.pptx（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基本原理组合排列排列数公式组合数公式组合数性质应用问题知识结构知识结构第1页/共54页1、掌握优先处理元素（位置）法；2、掌握捆绑法；3、掌握插空法。4、隔板法5、分组分配问题：1、是否均匀；2、是否有组别。第2页/共54页一一.特殊元素和特殊位置优先策略特殊元素和特殊位置优先策略例例1.1.由由0,1,2,3,4,50,1,2,3,4,5可以组成多少个没有重复数字可以组成多少个没有重复数字 五位奇数五位奇数.分析分析:由于末位和首位有特殊要求由于末位和首位有特殊要求,应该优先安应该优先安 排排,以免不合要求的元素占了这两个位置以免不合要求的元素占了这两个位置 先排末位共有先排末位共有_ 然后

2、排首位共有然后排首位共有_ 最后排其它位置共有最后排其它位置共有_由分步计数原理得由分步计数原理得位置分析法和元素分析法是解决排列组合问题最常位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法用也是最基本的方法,若以元素分析为主若以元素分析为主,需先安排需先安排特殊元素特殊元素,再处理其它元素再处理其它元素.若以位置分析为主若以位置分析为主,需需先满足特殊位置的要求先满足特殊位置的要求,再处理其它位置再处理其它位置.第3页/共54页实战演练实战演练 练习一练习一 安排甲，乙，丙三人周一至周六值安排甲，乙，丙三人周一至周六值班，每人值班两天，其中甲不值周一，乙必须班，每人值班两天，其

3、中甲不值周一，乙必须值周六，问有多少种不同的安排方法？值周六，问有多少种不同的安排方法？分析：分析：先安排甲，再安排乙先安排甲，再安排乙.因甲不值周一，又因甲不值周一，又不能值周六，故甲有不能值周六，故甲有 种排法，从而此题结种排法，从而此题结论应为论应为 种安排方法种安排方法 第4页/共54页例2.2.（1 1）7 7位同学站成一排，共有多少种不同的排法？(2)7(2)7位同学站成两排(前3 3后4)4)，共有多少种不同的排法？(3)7(3)7位同学站成一排，其中甲站在中间的位置,共有多少种不同的排法？第5页/共54页(4)7(4)7位同学站成一排，甲、乙只能站在两端的排法共有多少种？解:将

4、问题分步第一步:甲乙站两端有 种第二步:其余5名同学全排列有 种答：共有2400种不同的排列方法。第6页/共54页(5)7(5)7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？解法一:(特殊位置法)第一步:从其余5位同学中找2人站排头和排尾,有 种;第二步:剩下的全排列,有 种;答：共有2400种不同的排列方法。第7页/共54页解法二:(特殊元素法)第一步:将甲乙安排在除排头和排尾的5个位置中的两个位置上,有 种;第二步:其余同学全排列,有 种;答：共有2400种不同的排列方法。(5)7(5)7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？第8页/共54页解法三:(排除

5、法)先全排列有 种,其中甲或乙站排头有 种,甲或乙站排尾的有 种,甲乙分别站在排头和排尾的有 种.答：共有2400种不同的排列方法。(5)7(5)7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？第9页/共54页优限法:对于“在”与“不在”等类似有限制条件的排列问题,常常使用“直接法”(主要为“特殊位置法”和“特殊元素法”)或者“排除法”,即优先考虑限制条件.这种方法就是优限法.第10页/共54页例2.2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。若三个女孩要站在一起，有多少种不同的排法？解：将三个女孩看作一人与四个男孩排队，有 种排

6、法，而三个女孩之间有 种排法，所以不同的排法共有：（种）。捆捆 绑绑 法法二二.相邻元素捆绑策略相邻元素捆绑策略第11页/共54页若三个女孩要站在一起，四个男孩也要站在一起，有多少种不同的排法？不同的排法有：（种）说一说说一说捆绑法一般适用于 问题的处理。相邻例2.2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。要求某几个元素必须排在一起的问题要求某几个元素必须排在一起的问题,可以用捆绑可以用捆绑法来解决问题法来解决问题.即将需要相邻的元素合并为一个元即将需要相邻的元素合并为一个元素素,再与其它元素一起作排列再与其它元素一起作排列,同时要注意合并

7、元素同时要注意合并元素内部也必须排列内部也必须排列.第12页/共54页若三个女孩互不相邻，有多少种不同的排法？解：先把四个男孩排成一排有解：先把四个男孩排成一排有 种排法，在每一排种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入列中有五个空档（包括两端），再把三个女孩插入空档中有空档中有 种方法，所以共有：种方法，所以共有：（种）（种）排法。排法。插插 空空 法法例2.2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。三三.不相邻问题插空策略不相邻问题插空策略元素不相邻问题可先把没有位置要求的元素进行排元素不相邻问题可先把没有位置要求的

8、元素进行排队，再把不相邻元素插入相应空隙中队，再把不相邻元素插入相应空隙中。第13页/共54页男生、女生相间排列，有多少种不同的排法？解：先把四个男孩排成一排有解：先把四个男孩排成一排有 种排法，在每一排种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入列中有五个空档（包括两端），再把三个女孩插入空档中有空档中有 种方法，所以共有：种方法，所以共有：（种）（种）排法。排法。插插 空空 法法例2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。第14页/共54页甲、乙两人的两边必须有其他人，有多少种不同的排法？解：先把其余五人排成一排有 种排

9、法，在每一排列中有四个空档（不包括两端），再把甲、乙插入空档中有 种方法，所以共有：（种）排法。插插 空空 法法例2.2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。第15页/共54页例2 2七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成两排照相留念。若前排站三人，后排站四人，其中的A.BA.B两小孩必须站前排且相邻，有多少种不同的排法？AB解：A，B两小孩的站法有：（种），其余人的站法有 （种），所以共有 （种）排法。第16页/共54页 练习二练习二 7 7人站成一排，其中人站成一排，其中A A、B B两人必须相邻，且两

10、人必须相邻，且C C、D D两人不能相邻有多两人不能相邻有多少种不同的排法？少种不同的排法？种种练习三练习三 有有1010个座位，安排给个座位，安排给6 6个人就座，个人就座，其中空位不相邻的做法有多少种？其中空位不相邻的做法有多少种？种种实战演练实战演练第17页/共54页 解：解：把此问题当作一个排队模型在把此问题当作一个排队模型在6 6个空座的个空座的5 5个空隙中插入个空隙中插入3 3个人有个人有 种种.练习五练习五 某城新建的一条道路上有某城新建的一条道路上有1212只路灯只路灯,为了为了节省用电而不影响正常的照明，可以熄灭其中三节省用电而不影响正常的照明，可以熄灭其中三盏灯，但两端的

11、灯不能熄灭，也不能熄灭相邻的盏灯，但两端的灯不能熄灭，也不能熄灭相邻的两盏灯，可以熄灭的方法共有多少种两盏灯，可以熄灭的方法共有多少种？解：解：把此问题当作一个排队模型在把此问题当作一个排队模型在9 9盏亮灯的盏亮灯的8 8个空隙中插入个空隙中插入3 3个不亮的灯有个不亮的灯有 种种.思维转化思维转化练习四练习四 某排共有某排共有9 9个座位，若个座位，若3 3人坐在座位上，每人左人坐在座位上，每人左右都有空位，则不同的坐法有多少种右都有空位，则不同的坐法有多少种？第18页/共54页将将n个相同的元素按顺序分成个相同的元素按顺序分成m份，每份份，每份至少一个元素至少一个元素,每一种插板方法对应

12、一种分法共有每一种插板方法对应一种分法共有_ 种分法种分法.四四.元素相同问题隔板策略元素相同问题隔板策略例例3 3 有有1010个运动员名额，在分给个运动员名额，在分给7 7个班，每班至少一个班，每班至少一个个,有多少种分配方案？有多少种分配方案？分析：分析：因为因为1010个名额没有差别，把它们排成一排个名额没有差别，把它们排成一排.在个空隙中选在个空隙中选个位置个位置插入隔板，插入隔板，可可把名额分成份，对应地分给个班级，把名额分成份，对应地分给个班级，相邻名额之间形成个空隙相邻名额之间形成个空隙.可以用可以用m-1-1块隔板插入块隔板插入n个个元素排成一排的元素排成一排的n-1-1个空

13、隙中个空隙中,所有分法数为所有分法数为一班二班三班四班五班六班七班第19页/共54页实战演练实战演练练习七练习七 求方程求方程x+y+z+w=100的正整数解的组数的正整数解的组数.练习六练习六 1010个相同的球装入有编号的个相同的球装入有编号的5 5个盒中个盒中,每盒至少一个，有多少装法？每盒至少一个，有多少装法？第20页/共54页五五.排列组合混合问题先选后排策略排列组合混合问题先选后排策略例例4 4 有有5 5个不同的小球个不同的小球,装入装入4 4个不同的盒内个不同的盒内,每盒每盒至少装一个球至少装一个球,共有多少不同的装法共有多少不同的装法?根据分步计数原理装球的方法共有根据分步计

14、数原理装球的方法共有_解决排列组合混合问题解决排列组合混合问题,先选后排是最基本先选后排是最基本的指导思想的指导思想.解:第一步从5个球中选出2个组成复合元共有_种方法.第二步把4个元素(包含一个复合元素)装入4个不同的盒内有_种方法.第21页/共54页 练习九练习九 某学习小组有某学习小组有5 5个男生个男生3 3个女生，从中个女生，从中选选3 3名男生和名男生和1 1名女生参加三项竞赛活动，每项名女生参加三项竞赛活动，每项活动至少有活动至少有1 1人参加，则有不同参赛方法多少种人参加，则有不同参赛方法多少种.解：采用解：采用先组后排先组后排方法方法:练习八练习八 从从1 1到到7 7的的7

15、 7个数字中取个数字中取2 2个偶数个偶数3 3个奇数，个奇数，其中其中2 2个偶数排在一起，问组成没有重复数字的个偶数排在一起，问组成没有重复数字的5 5位数？位数？解：采用解：采用先组后排先组后排方法方法:实战演练实战演练第22页/共54页例5.5.(1)(1)将四个小球分成两组，每组两个，有多少分法？3种六 分组问题第23页/共54页(2)(2)将四个小球分给两人，每人两个,有多少分法？甲甲乙乙6种第24页/共54页(3)(3)将四个小球分成两组，一组三个，一组一个，有多少分法？4种第25页/共54页(4)(4)将四个小球分给两人，一人三个,一人一个，有多少分法？甲乙甲乙8种第26页/共

16、54页第27页/共54页若分成的m组是有组别的，只需在原来的分组基础上再第28页/共54页例6.有6本不同的书，分成3堆.（1）如果每堆2本，有多少种分法？（2）如果分成一堆1本，一堆2本，一堆3本，有多少种分法？分析:这与例2不同，区别在于把 6本不同的书分给甲、乙、丙3人，每人2本，相当于把6本不同的书先分成3堆，再把分得的3堆分给甲、乙、丙3人.第29页/共54页例6.有6本不同的书，分成4堆.（3）如果一堆3本，其余各堆各1本，有多少种分法？（4）如果每堆至多2本，至少1本，有多少种分法？第30页/共54页注意：注意：分组分配问题主要有分组后分组分配问题主要有分组后有分配对象有分配对象

17、(即组本身即组本身有序有序)的的均分均分与与不均分不均分问题及分组后问题及分组后无分配对象无分配对象(即组本即组本身无序身无序)的的均分均分与与不均分不均分问题四种类型，常见的情形有问题四种类型，常见的情形有以下几种以下几种:(2)均匀、有序分组:把n个不同的元素分成有序的m组，每组r个元素，则共有 种分法.(其中mr=n)(1)均匀、无序分组:把n个不同的元素分成无序的m组，每组r个元素，则共有 种分法.(其mr=n)第31页/共54页(3)非均匀、无序分组:把n个不同的元素分成m组，第1组r1个元素，第2组r2个元素，第3组r3个元素，第m组rm个元素，则共有 种分法.(其中r1+r2+r

18、3+rm=n)(4)非均匀、有序分组:把n个不同的元素分成m组，第1组r1个元素，第2组r2个元素，第3组r3个元素，第m组rm个元素，再分给m个人，则共有 种分法.(其中r1+r2+r3+rm=n)第32页/共54页(5)局部均匀分组:把n个不同的元素分成m组，其中m1个组有r1个元素，m2个组有r2个元素，mk个组有rk个元素，则共有 种分法.(其中m1r1+m2r2+m3r3+mkrk=n)第33页/共54页练习:9件不同的玩具，按下列方案有几种分法？1.甲得2件，乙得3件，丙得4件，有多少种分法？2.一人得2件，一人得3件，一人得4件，有多少种分法？3.每人3件，有多少种分法？4.平均

19、分成三堆，有多少种分法？5.分为2、2、2、3四堆，有多少种分法？解：解：第34页/共54页感悟感悟 分享分享 （一）解决排列组合一）解决排列组合一）解决排列组合一）解决排列组合16161616字方针是解排列组合的基本规律，字方针是解排列组合的基本规律，字方针是解排列组合的基本规律，字方针是解排列组合的基本规律，即即即即分类相加，分步相乘，有序排列，无序组合分类相加，分步相乘，有序排列，无序组合分类相加，分步相乘，有序排列，无序组合分类相加，分步相乘，有序排列，无序组合.（二）几种解题策略（二）几种解题策略（二）几种解题策略（二）几种解题策略1.1.1.1.特殊元素和特殊位置优先策略特殊元素和

20、特殊位置优先策略特殊元素和特殊位置优先策略特殊元素和特殊位置优先策略2.2.2.2.相邻元素捆绑策略相邻元素捆绑策略相邻元素捆绑策略相邻元素捆绑策略3.3.3.3.不相邻问题插空策略不相邻问题插空策略不相邻问题插空策略不相邻问题插空策略4.4.元素相同问题隔板策略元素相同问题隔板策略你掌握了哪些探求问题你掌握了哪些探求问题的方法和数学思想？的方法和数学思想？由由特特殊殊到到一一般般类类比比、归归纳纳、转转化化第35页/共54页例例6:从从6个学校中选出个学校中选出30名学生参加数学竞赛名学生参加数学竞赛,每校至少每校至少有有1人人,这样有几种选法这样有几种选法?分析:问题相当于把30个相同的球

21、放入6个不同盒子(盒子不能空的)有几种放法?这类问题可用“隔板法”处理.小结：把n个相同元素分成m份，每份至少1个元素，问有多少种不同分法的问题可以采用“隔板法”.共有：第36页/共54页变式1:将7只相同的小球全部放入4个不同盒子，每盒至少1球的放法有多少种？变式2:将7只相同的小球全部放入4个不同盒子，每盒可空，不同的放法有多少种？第37页/共54页课堂练习：课堂练习：1、4个学生和3个老师排成一排照相，老师不能排两端，且老师必须排在一起的不同排法种数是（）A.B.C.D.D2、计划展出10幅不同的画，其中1幅水彩画，4幅油画，5幅国画，排成一行陈列，要求同一品种的画必须连在一起，那么不同

22、的陈列方式有（）B3、在7名运动员中选出4名组成接力队，参加4100米接力赛，那么甲、乙两人都不跑中间两棒的安排方法有多少种？第38页/共54页练习2:将5个人分成4个组，每组至少1人，则分组的种数是多少？练习1:将12个人分成2，2，2，3，3的5个组，则分组的种数是多少？第39页/共54页练习3:9件不同的玩具，按下列方案有几种分法？1.甲得2件，乙得3件，丙得4件，有多少种分法？2.一人得2件，一人得3件，一人得4件，有多少种分法？3.每人3件，有多少种分法？4.平均分成三堆，有多少种分法？5.分为2、2、2、3四堆，有多少种分法？解：解：第40页/共54页课堂小结：课堂小结：1、对限制

23、条件较复杂的排列组合应用题，要周密分析，、对限制条件较复杂的排列组合应用题，要周密分析，设计出合理的方案，把复杂问题分解成若干个简单的设计出合理的方案，把复杂问题分解成若干个简单的基本问题后再用两个计数原理来解决；基本问题后再用两个计数原理来解决；2、一般情况下应遵循先取元素，后排列的原则；、一般情况下应遵循先取元素，后排列的原则；3、对于某些特殊问题要能熟练使用相应方法解决，如：、对于某些特殊问题要能熟练使用相应方法解决，如：隔板法、均匀分组（局部均匀分组）等问题隔板法、均匀分组（局部均匀分组）等问题.第41页/共54页课堂小结：课堂小结：基本的解题方法：有特殊元素或特殊位置的排列问题，通常

24、是先排特有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）殊元素或特殊位置，称为优先处理特殊元素（位置）法（优先法）；法（优先法）；某些元素要求必须相邻时，可以先将这些元素看作某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内一个元素，与其他元素排列后，再考虑相邻元素的内部排列，这种方法称为部排列，这种方法称为“捆绑法捆绑法”；某些元素不相邻排列时，可以先排其他元素，再将某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空挡，这种方法称为这些不相邻元素插入空挡，这种方法称为“插空法插空法”；在处理排列问

25、题时，一般可采用直接和间接两种在处理排列问题时，一般可采用直接和间接两种思维形式，从而寻求有效的解题途径，这是学好排列思维形式，从而寻求有效的解题途径，这是学好排列问题的根基问题的根基第42页/共54页第43页/共54页 用0-50-5这六个数字可以组成没有重复的（1 1）四位偶数有多少个？奇数？（5 5）十位数比个位数大的三位数？（2 2）能被5 5整除的四位数有多少？（3 3）能被3 3整除的四位数有多少？（4 4）能被2525整除的四位数有多少？（6 6）能组成多少个比240135240135大的数？若把 所组成的全部六位数从小到大排列起来，那么240135240135是第几个数？备选题

26、第44页/共54页有约束条件的排列问题例4：有4个男生和3个女生排成一排，按下列要求各有多少种不同排法：（1）男甲排在正中间；（2）男甲不在排头，女乙不在排尾；（3）三个女生排在一起；（4）三个女生两两都不相邻；（5）全体站成一排，甲、乙、丙三人自左向右顺序不变；（6 6）若甲必须在乙的右边（可以相邻，也可以不相邻），有多少种站法？对于相邻问题，常用对于相邻问题，常用“捆绑法捆绑法”对于不相邻问题，常用对于不相邻问题，常用“插空法插空法”第45页/共54页【例例3】用用0到到9这这10个数字可以组成多少个没有重个数字可以组成多少个没有重复数字的三位数？复数字的三位数？特殊位置“百位”，特殊元素

27、“0”百位十位个位法1：法2：百位百位 十位十位 个位个位0百位百位 十位十位 个位个位0百位百位 十位十位 个位个位第46页/共54页【例例3】用用0到到9这这10个数字可以组成多少个没有重个数字可以组成多少个没有重复数字的三位数？复数字的三位数？特殊位置“百位”，特殊元素“0”法3：第47页/共54页百位十位个位千位万位变式：由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有多少个？有约束条件的排列问题第48页/共54页百位十位个位千位万位变式：由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有多少个？有约束条件的排列问题第49页/共

28、54页例3 3：某信号兵用红，黄，蓝3 3面旗从上到下挂在竖直的旗杆上表示信号，每次可以任挂1 1面、2 2面或3 3面，并且不同的顺序表示不同的信号，一共可以表示多少种不同的信号？解：分3类：第一类用1面旗表示的信号,有_种；第二类用2面旗表示的信号,有_种；第三类用3面旗表示的信号,有_种，由分类计数原理，所求的信号种数是：，答：一共可以表示15种不同的信号.第50页/共54页四、分类组合,隔板处理例例5、从从6个学校中选出个学校中选出30名学生参加数学竞赛名学生参加数学竞赛,每每校至少有校至少有1人人,这样有几种选法这样有几种选法?分析:问题相当于把个30相同球放入6个不同盒子(盒子不能

29、空的)有几种放法?这类问可用“隔板法”处理.解:采用“隔板法”得:第51页/共54页练习：1、将8个学生干部的培训指标分配给5个不同的班级，每班至少分到1个名额，共有多少种不同的分配方法？2、从一楼到二楼的楼梯有17级，上楼时可以一步走一级，也可以一步走两级，若要求11步走完，则有多少种不同的走法？第52页/共54页一、等分组与不等分组问题例2、6本不同的书，按下列条件，各有多少种不同的分法；（1）分给甲、乙、丙三人，每人两本；（2）分成三份，每份两本；（3）分成三份，一份1本，一份2本，一份3本；（4）分给甲、乙、丙3人，一人1本，一人2本，一人3本；（5）分给甲、乙、丙3人，每人至少一本；（6）分给5个人，每人至少一本；（7）6本相同的书，分给甲乙丙三人，每人至少一本。有序有序无序无序第53页/共54页感谢您的观看。第54页/共54页