计数原理+排列组合复习课(高三一轮复习)ppt课件.ppt

《计数原理+排列组合复习课(高三一轮复习)ppt课件.ppt》由会员分享，可在线阅读，更多相关《计数原理+排列组合复习课(高三一轮复习)ppt课件.ppt（42页珍藏版）》请在三一办公上搜索。

1、计数应用题中的典型问题和典型方法,【例1】有两个袋子，其中一个袋子装有20个红色小球，每个 球上标有1至20中的号码，另一个袋子装有白色小球15 个，每个球上标有1至15中的号码， (1)从袋子中任取一个小球，有多少种不同的取法？ (2)从袋中任取红白球各一个，有多少种不同的取法？,点评：分清是“分类”还是“分步”是区别应用这两个原理的关键所在,分析：分类：方法可分类，类与类是并列关系，一类方法能完成一件事 ； 分步：过程需分步，步与步是前后相继的关系，一步不能完成一件事情，几步共同才,解： (1)分两类：从红球中任取一个有20种不同的取法,从白球中任取一个有15种不同的取法,由分类计数原理得

2、201535(种), 即共35种不同取法,(2)分两步： 从红球中任取一个有20种不同的取法；,从白球中任取一个有15种不同的取法，,由分步计数原理得2015300(种),即共300种不同取法,能完成一件事。,1、分类、分步两个原理的区别与联系,名称,内容,【巩固练习】已知集合M3,2,1,0,1,2,P(a,b)是平面 上点， (1) P可表示多少个不同的点？ (2) P可表示多少个坐标轴上的点？,(2)分三类： 第一类：P为x轴上(除原点)的点有5种， 第二类：P为y轴上(除原点)的点有5种， 第三类：P为原点有1种， 由分类计数原理得55111(种)， P可表示11个坐标轴上的点,解：(

3、1)分两步： 第一步：先确定横坐标a有6种不同的选法； 第二步：再确定纵坐标b有6种不同的选法， 由分步计数原理得6636 (种)， P可表示36个不同的点,【例2】用五种不同颜色给图中四个区域涂色，每个区域涂一 种颜色 ， (1)共有多少种不同的涂色方法？ (2)若要求相邻(有公共边)的区域不同色，那么共有多少 种不同的涂色方法？,1,2,3,4,解：(1)由分步计数原理可知，共有 =625种 ；,(2)只有2和4可同色。若2，4不同色有 种， 若2，4同色，有 种，共有120+60=180种。,分析：,有5种,有5种,有5种,有5种,分析：,1,2,3,4,= 420（种）,解：,按颜色分

4、类，有三类不同的着色方法：,（1）涂5色：有 种；,（2）涂4色：有 种.,由分类计数原理，不同的着色方法有：,（3）涂3色：有 种.,练习如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有5种颜色可供选择，则不同的着色方法共有 种（以数字作答）.,【例3】有4名学生报名参加数学、物理、化学竞赛，每人限 报一科，有多少种不同的报名方法？ 有4名学生争夺数学、物理、化学竞赛的冠军，有多,少 种不同的结果？,分析：4名学生报名参加竞赛，不得兼报，是“人选科目”，每人都有3种不同的 报名方法，可把4名学生报名视为4个步骤 ，用分步计数原理 ； 4名学生争夺三项冠军，因每

5、位冠军只能是一名学生获得，故应是“科目选 人”，每个科目的冠军都有4种可能，将3个科目选冠军视为3个步骤，也应 用分步计数原理,解：4名学生中，每人都要选报数学、物理、化学中的一科， 根据分步计数原理，共有 种报名方法,4名学生争夺数学、物理、化学三项冠军，每一项冠军都有4种不同的结果 ，共有 种不同的结果 。,2、排列和组合的区别和联系,【算一算】,(1)计算,(2)解方程,(3),排列应用题的求解应着眼的三个方面：(1)问题的结果是否与顺序有关，能否归结为排列问题；(2)问题中的几个元素指的是什么，m个元素的一个排列对应着 的事件是什么；(3)从n个元素中每次取出m个元素的一个排列对应着的

6、事件是 什么,一、特殊优先原则 在有限制的问题中，优先考虑特殊元素或特殊位置,三大原则：,二、先取后排原则先取后排原则也是解排列组合问题的总原则，尤其是排列与组合的综合问题 。,三、正难则反原则若从正面直接解决问题有困难时，则考虑排除法：先不管约束条件，求出总数，再剔除不合要求的部分,采用策略：（1）特殊位置/元素优先排列的策略：（2）合理分类与准确分步的策略；（3）排列、组合混合问题先选后排的策略；（4）正难则反、等价转化的策略；（5）相邻问题捆绑处理的策略；（6）不相邻问题插空处理的策略；（7）定序问题除法处理的策略；（8）分排问题直排的策略 （一排考虑，分段研究）.,排列: 顺序；,【例

7、1 】7人按下述要求排成一列，分别有多少种不同的站法？ (1)甲不站在两端；(2)甲、乙必须站在两端；(3)甲、乙 不相邻；(4)甲、乙必须相邻；(5)甲、乙之间相隔2人； (6)甲在乙的前面(可以不相邻),a,c,b,d,e,g,f,分析：,由于元素甲、乙有特殊要求，故可采用优先元素或位置优先排列,解：(1)(特殊位置分析法)由于甲不站在两端，可先从除甲外 的6人中任选2人站于两端共有 种方法，再将所剩5 人在所剩5个位置上进行全排列有 种方法，故共有 种不同的站法,(间接法)7人全排列共有 种，其中甲在两端者有 种，故甲不在两端的所有站法，共有 种,(特殊元素分析法)由于甲不站在两端，故甲

8、只能站在中间五 个 位置之一，有 种，余下的6人进行全排列共有 种， 由分步计数原理得，共有种 不同的站法,(2)先排甲、乙于两端有 种排法，再让余下的5人进行排 有 种，故甲、乙站在两端的所有排法有 种排法,(3)(插空法)由于甲、乙不相邻，故先排除了甲、乙以外的5人， 有 种排法，再将甲、乙两人插入6个空档有 种，由分 步计数原理得:甲、乙不相邻的排法有 种不同的排法,a,c,b,d,e,分析,(间接法)7人全排列有 种，其中甲、乙相邻者有 种，从而甲、乙不相邻者有 种不同的排法,(4)(捆绑法)设想将甲、乙2人并作一人，与其余5人进行全排列， 共有 种排法，又此2人的位置可交换，即有 种

9、排法，于 是共有 种不同的排法,a,c,b,d,e,g,f,分析,(5)先从另5人中选2人排于甲、乙之间，有 种排法，又甲、乙 2人的排法有 种，最后将甲、乙及其中间2人共4人并作一 个元素，与其余3人排列列有 种排法，故共有 种 不同的排法,(6)(整体、对称法)注意到甲在乙前与甲在乙后的排法一样多， 故共有 种排法,点评：“先”与“后”，“并”与“插”都是辨证的，是可以互相转化的，在处理限位排列问题时，应灵活运用上述方法与策略,考点四定序问题消序(定序元素后排)策略 【例3】 7人排队, 其中甲乙丙 3 人顺序一定共有多少不同的排法？,【练】 用 1,2,3,4,5,6,7,8,9 组成没

10、有重复数字的十位数字小于个位数字的五位数共有多少个？,【练】某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为（ ）,30,考点六.多排问题直排策略,例7.8人排成前后两排,每排4人,其中甲乙在 前排,丁在后排,共有多少排法？,解:8人排前后两排,相当于8人坐8把椅子,可以 把椅子排成一排.,一般地,元素分成多排的排列问题,可归结为一排考虑,再分段研究.,点拨: 先不考虑定序的条件, 排好后再除以要求定序的 元素的全排列数.,变式 10人身高各不相等, 排成前后排, 每排5人, 要求 从左至右身高逐渐增

11、加，共有多少排法？,【小试牛刀】,(1)从a,b,c,d 4名学生中选出2名完成一件工作，有多少种不同的选法？,(2)从a,b,c,d 4名学生中选出2名完成两件不同的工作，有多少种不同的选法？,组合：无顺序,问题：将4本不同的书，按下列要求分组有多少不同的分法？,(1)分成两组，一组3本，另一组1本；,(2)平均分成两组；,分组问题,分组不定向分配问题,(3)分成三组，一组2本，另两组各1本；,(4)分给甲、乙两人，甲3本，乙1本；,(5)分给甲、乙两人，1人3本，另1人1本；,1.把abcd分成平均两组,ab,cd,ac,bd,ad,bc,有_多少种分法？,cd,bd,bc,ad,ac,a

12、b,这两个在分组时只能算一个,平均分成的组，不管它们的顺序如何，都是一种情况，所以分组后要除以Amm，即m!，其中m表示组数。,分组问题,2.把abcdef分成平均三组,有_多少种分法？,分组问题,这6个在分组时只能算一个,平均分成的组，不管它们的顺序如何，都是一种情况，所以分组后要除以Amm，即m!，其中m表示组数。,1.把abcd分成两组，一组3个，一组1个，,abc,d,abd,c,acd,b,有_多少种分法？,bcd,a,分组总共有4种,分组问题:(不平均分组 ),有 种方法；,可先分3本的一组，再分1本的一组，这是连续进行的过程，因此应采用分步法,将4本不同的书，按下列要求分组有多少

13、不同的分法？,范例,(1)分析：,解：,第1步：从4本书中任取3本分给3本的一组，,第2步：余下的1本书分给1本的一组，,根据乘法原理，共有 =4 种不同分法,分组问题,(1)分成两组，一组3本，另一组1本；,分二步,有 种分法；,不平均分组， 无分配目标,范例,将4本不同的书，按下列要求分组有多少不同的分法？,有 种方法；,解：,由于分步处理过程使分组产生了顺序，要用“除法”消序,第二步，再分余下的2本书得到另一组，,有 种分法；,故符合要求的分法有 =3 种不同分法,(2)平均分成两组；,第一步，先从4本书中分得2本得到一组，,全部平均分配， 无分配目标,范例,将4本不同的书，按下列要求分

14、组有多少不同的分法？,有 种分法；,解：,由于分步处理使后面二组产生了先后顺序，要用“除法”消序,第二步，再从余下的2本书中分1本得到另一组，,有 种分法；,故符合要求的分法有 =3 种不同分法,(3)分成三组，一组2本，另两组各1本；,第一步，先从4本书中分2本得到一组，,部分平均分配， 无分配目标,第三步，余下最后1本书得到最后一组，,有 种分法；,问题：将4本不同的书，按下列要求分组有多少不同的分法？,(1)分成两组，一组3本，另一组1本；,(2)平均分成两组；,1.非均分无分配对象的问题,一、分组不分配问题,分组不定向分配问题,2. 均匀分组无分配对象的问题,3.部分均分无分配对象的问

15、题,(3)分成三组，一组2本，另两组各1本；,将4本不同的书，按下列要求分组有多少不同的分法？,(4)分给甲、乙两人，甲3本，乙1本；,(5)分给甲、乙两人，1人3本，另1人1本；,分组且分配问题,分组定向分配问题,分组不定向分配问题,有 种方法；,可先分给甲，再分给乙，这是连续进行的过程，因此应采用分步法,(2)分析：,解：,第1步：甲从4本书中分得3本，,第2步：乙分得余下的1本书，,根据乘法原理，共有 =4 种不同分法,分二步：,有 种分法；,不平均分组， 有分配目标且明确,有 种分法；,解：,第1步：先从4本书中分得3本得到一组，,第2步：余下的1本书得到另一组，,有 种分法；,根据乘

16、法原理，共有 =8 种不同分法,第3步：将分好的两组再分给甲、乙两人，,有 种分法；,不平均分组，有分配目标，但不明确,【典型例题】12本不同的书，按下列方法分堆，共有多少种不 同的方法？,(1)分成A、B、C三堆，每堆4本； (2)分成A、B、C三堆，A为6本，B、C各为3本； (3)平均分成三堆，每堆4本； (4)分成三堆，其中一堆6本，另两堆各3本； (5)分成五堆，其中两堆每堆3本，另外三堆每堆2本,分析：,4,4,4,4,4,4,A,B,C,?,堆有编号，分堆有顺序 ；平均分堆，堆无编号，堆与堆之间无顺序 。,(2)同(1)可得：共有 种分堆方法,(3)共有 种不同的分堆方法,(4)

17、共有 种不同的分堆方法,(5)共有 种不同的分堆方法,解：(1)A堆得4本书有 种方法，B堆得4本书有 种方法， C堆得4本书有 种方法，由分步计数原理得： 共有 种不同的分堆方法,点评：平均分堆问题与顺序无关,练习： 有12个人，按照下列要求分配，求不同的分法种数 （1）分为两组，一组7人，一组5人； （2）分为甲、乙两组，甲组7人，乙组5人； （3）分为甲、乙两组，一组7人，一组5人； （4）分为甲、乙两组，每组6人； （5）分为两组，每组6人； （6）分为三组，一组5人，一组4人，一组3人； （7）分为甲、乙、丙三组，甲组5人，乙组4人，丙组3人； （8）分为甲、乙、丙三组，一组5人，一

18、组4人，一组3人； （9）分为甲、乙、丙三组，每组4人； （10）分为三组，每组4人,【探索与研究】,如图，某城市有6纵7横共13条马路，汽车从图示A处行驶至B处，行驶方向规定只能是正东向或正北向，则不同的行驶路径有多少条？,分析：从A行驶到B，共需走11“段”路，其中横路5段，纵路6段，而且我们知道，任意一条路径都是5横6纵共11段路组成从而问题转化为在11段路径中无顺序地确定5段横路的位置，这是一个组合问题,解：共有 条不同的路径,点评：对于较复杂的排列组合问题，充分挖掘出问题的简化模型，往往是我们快捷而准确地解决问题的关键,2.(2016课标全国,5,5分)如图,小明从街道的E处出发,先

19、到F处与小红会合,再一起到位于G处的老年公寓参加志愿者活动,则小明到老年公寓可以选择的最短路径条数为()A.24B.18C.12D.9,答案B分两步,第一步,从EF,有6条可以选择的最短路径;第二步,从FG,有3条可以选择的最短路径.由分步乘法计数原理可知有63=18条可以选择的最短路径.故选B.,3、课堂小结,1.正确区分、合理运用两个计数原理；,2.真正理解排列与组合的区别和联系；排列-顺序；组合-无顺序,3.掌握求解排列、组合的典型方法。 间接法、捆绑法、插空法、整体对称法等,补充习题,例6. 用0, l, 2, 3, 4, 5这六个数字， （l）能组成多少个无重复数字的四位偶数？ （2

20、）能组成多少个无重复数字且为5的倍数5位数？ （3）能组成多少个比1325大无重复数字的四位数？ （4）能组成多少个无重复数字的且奇数在奇数位上的六位数字？,解：,（2）符合条件的可分为二类：,第一类：0在个位时有 个；,第二类：5在个位时有 个；,由分类计数原理得，符合条件的五位数,= 216 （个）,解：,（3）符合条件的可分为三类：,第一类：千位数字为 2、3、4、5 时有 个；,第二类：千位百位数字为14、15时有 个；,由分类计数原理得，符合条件的数共有,= 270 （个）,第三类：千位百位十位数字为134、135时有 个；,例5 用0, l, 2, 3, 4, 5这六个数字， （l

21、）能组成多少个无重复数字的四位偶数？ （2）能组成多少个无重复数字且为5的倍数5位数？ （3）能组成多少个比1325大无重复数字的四位数？ （4）能组成多少个无重复数字的且奇数在奇数位上的六位数字？,解：,（4）先将 1，3，5 在奇数位上排列，有 种，,再将其余3个偶数排在剩余3个位置上排列，共有 种，,由分步计数原理得，共有 种排法，,= 24 （个）,而其中0在首位上时不合题意，有 种，,所以符合条件的数共有,例5 用0, l, 2, 3, 4, 5这六个数字， （l）能组成多少个无重复数字的四位偶数？ （2）能组成多少个无重复数字且为5的倍数5位数？ （3）能组成多少个比1325大无重

22、复数字的四位数？ （4）能组成多少个无重复数字的且奇数在奇数位上的六位数字？,谢 谢！,【小试牛刀】,(1)从a,b,c,d 4名学生中选出2名完成一件工作，有 种不同的选法？,(2)从a,b,c,d 4名学生中选出2名完成两件不同的工作，有 种不同 的选法？,(3)a,b,c,d 4个足球队之间进行单循环比赛，共需踢 场？,(4)a,b,c,d 4个足球队争夺冠亚军，有 种不同的结果？,【典型例题】,求方程 的正整数解的个数,+,+,+,= 7,分析,1 2 2 2,1 1 2 3,1 1 1 4,法1,组合：无顺序,1 + 1 + 1 + 1 + 1 + 1 + 1=7,1 + 1 + 1

23、 + 1 + 1 + 1 + 1=7,1 + 1 + 1 + 1 + 1 + 1 + 1=7,法2,解： 法一 共有 种 法二 共有 种,点评：此题新颖，解题过程中用到的都是基本知识和基本方法，但要通过分析、构想、调动基本知识和基本方法解题解法一应有较强的分类讨论处理问题的意识；解法二通过转化， 化归为熟悉的插空问题由此还可以求解本类问题更一般的情形,1 有六本不同的书分给甲、乙、丙三名同学，按下条件，各有多少种不同的分法？（1）每人各得两本；（2）甲得一本，乙得两本，丙得三本；（3）一人一本，一人两本，一人三本；（4）甲得四本，乙得一本，丙得一本；（5）一人四本，另两人各一本.,(3),(4),(5),(2),(1),分组问题,