《排列与组合自》PPT课件.ppt

风子编辑,我们用枚举法来试试。四个站分别为：慈溪、龙山、镇海、宁波，采用握手法来做枚举。,从慈溪到宁波要新建一条铁路，在铁路沿线会设4个站，你认为铁路公司应该设计多少种车票呢？又有多少种票价？,慈溪,龙山,镇海,宁波,慈溪,龙山,镇海,宁波,同样名称不需要连线，不同名称的车站间需要连线，每条线表示一种车票。所以，左边的慈溪与右边一列有3条连线，即慈溪出发的车票为慈溪龙山、慈溪镇海、慈溪宁波；,同理，左边的龙山、镇海、宁波分别和右边一列车站也有三条连线，即各有三种车票；,所以，车票种类为12种。,而两站名称相同，车票的票价也是相同的，即票价是没有方向性的。,指从给定个数的元素中取出指定个数的元素进行排序。,排列,指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。,组合,【分析】本题有三个条件：1、10个数字组成5个两位数，数字不能重复；2、5个数字的和最大；3、和为奇数。三个条件中，我们可以从和最大着手，再进行调整。数相加，我们可以对不同权位上的数码进行处理，所以可以不考虑是哪5个两位数，而只需要考虑不同权位上的数字。,数字排列问题,使5个数的和最大，则最高权位的数码尽量大，所以选9、8、7、6、5；,剩下的5个数码为个位，而个位数码的和影响5个数的和的奇偶性。而0+1+2+3+4=10，不符合和为奇数的要求。,因此，用十位上最小的奇数与个位上最大的偶数进行交换，可以符合要求。即4放到十位上，5放到个位上。,所以，这五个数的和为：（4+6+7+8+9）10+（0+1+2+3+5）=351,1、用0、1、2、3、4、9这10个数字组成5个两 位数，每个数字只用一次，要求它们的和是奇数，并且尽可能的大，那么这5个两位数的和是多少？,2、用1、2、3、4这四个数字构成一个四位数abcd，要求：1）a、b、c、d互不相同；2）b比a、d都大，c比a、d都大，这样的四位数有几个？,【分析】本题提供了两个条件作限制，所以可以指导b、c应该为3、4，a、d为1、2。则b c和a d各有两种可能。所以这样的四位数有22=4种。,3、用数字2、2、3可以组成多少个不同的三位数？,【分析】这个题目不同之处是有重复的数字，需要进行讨论。当百位位3时，只有1种可能了。而百位为2时，剩下3、2在个位、十位，就有2种可能。合计为3个不同的三位数。,思考：如果1、2、3、3四个数，能组成几个不同的 三位数,3、某城市的电话号码是六位数，但首位不能是0，其余各位可以是09中任何一个数字，而且不同数字位上的数字可以重复，那么这个城市最多可以容纳多少部电话？,【分析】对于这类为问题，我们引入“碟子法”。题目是要用10个数字，组成不同的六位数，也就是在六个碟子中放入相应的数字。,1,2,3,4,5,6,1号碟子中不能放0，只能放19的任何一个数字，所以有9种可能；,数字排列问题,因为数字可以重复，26号碟子中可以放09的任何一个数字，所以有10种可能；,因此，这样的六位数可以有：91010101010=900000,如果数字不允许重复的话，会怎样呢？,4、用2、0、1、9这四个数字可以组成多少个没有重复数字的四位数？,【分析】用“碟子法”，我们需要四个碟子来表示四位数。,1,2,3,4,1号碟子中不能放0，则可以有3种可能,1号碟子已经放了一个数字，因为不能重复，所以只能在剩下的三个数字中选择一个，放在2号碟子中。这样，2号碟子会有3种可能。,同理，3号、4号碟子分别有2和1种可能。,那么，满足题目要求的四位数有：3321=18个,思考：用这四个数字，能组成多少个三位数,5、从120这20个自然数中，每次取出两个不同的数，使它们的和是4的倍数，共有多少不同的取法？,数字排列问题,【分析】先从题目中抽取出限制条件：1）从120中取出两个数字；2）取出的两个数字的和是4的倍数。怎样的两个数字之和会是4的倍数呢？只要两个数除以4的余数的和能被4整除，则这两个数的和就是4的倍数。,先对120这20个自然数根据除以4后的余数进行分类：1）被4整除的数有：4、8、12、16、20；2）被4整除余1的数有：1、5、9、13、17；3）被4整除余2的数有：2、6、10、14、18；4）被4整除余3的数有：3、7、11、15、19。,所以，合计有10+25+10=45种,6、由数字0、1、2、9这四个数字，组成的所有非零自然数，按照从小到大排列，2019排在第几个？,【分析】首先需要注意，题目没有要求是几位数，所以先要按位数进行分类考虑。然后，考虑2019是“2”在千位上的四位数中排在第几位。,可以组成的非零一位数有：3个可以组成的二位数有：33=9个可以组成的三位数有：332=18个,以“1”为千位的四位数有：1 321=6个以“2”为千位的四位数中，2019是第一个。,所以，2019在第3+9+18+6+1=37个上。,6、一个五位数 abcde 从五个数码中任意取出两个数码，构成一个两位数（保持数码在原先五位数中的前后顺序），这样的两位数有10个：37、38、33、37、78、73、77、83、87、37。则abcde=,数字排列问题,方法一：数轴法（在一条线上比较数字的现后位置）,1、10个两位数中，最多的是3和7，且十位3比7多一个，说明 最前面的是3,3,3,7,1、符合条件的字母组合有：ab、ac、ad、ae、bc、bd、be、cd、ce、de,3、78和87、38和83的存在，说明8在五位数的中间,8,4、有三个37，说明个位上的应该是7,7,5、所以这个五位数为37837,方法二：比对法（先找出10个字母组合）,2、33、77的存在，说明这个五位数有两个3和7。,2、对10个数字根据十位上的数码个数从多到少排序：33、37、37、37、38、73、77、78、83、87,3、比对1和2，十位上a最多，有4个；b次之，有3个；c 位两个。所以，a=3，b=7，c=8,4、十位上的3还多一个37，所以，d=3，e=7,比赛安排问题,1、运动会上，甲、乙、丙、丁4名运动员组队参加4100接力赛，甲必须跑第一棒，一共有多少种不同的跑法？,2、羽毛球训练，甲组有5名男队员，乙组有4名女队员，进行男女混合双打配对，一共有多少种不同的配对方法？,3、10支足球队参加一次足球比赛，每两支足球队都比赛一场，每场比赛中，胜队得3分，负队得0分，平局则各得1分，比赛完毕后，第4名和第5名得球队得分最多可以相差多少分？,【分析】男女混合双打配对，说明要从男女队员中，各找出一个人进行配对，这是一个组合问题。而选出的两个人不存在现后顺序，说明不涉及排列。,A,B,5,4,需要挑出2名队员，所以我们设2两个碟子,从甲组中选出1名男队员，放在A碟子，共有5种可能,从乙组中选出1名女队员，放在B碟子，共有4种可能。,比赛安排问题,1、五支足球队比赛，每两个队之间比赛一场。每场比赛胜者得3分，负者得0分，平局则各得1分，比赛完毕后，发现这五个队得分恰好是五个连续的自然数。设第1、2、3、4、5名分别平了A、B、C、D、E场，那么五位数 ABCDE=,1、乒乓球的比赛规则为：胜一局得2分，负一局得0分。在一次乒乓球比赛中，十名选手每两人之间都要比赛一场。当所有比赛结束后，发现十名选手的得分均不相同，那么第三名得了多少分？,队列问题,1、甲、乙、丙、丁、戊5个人排队，一共有多少种排法？如果甲、乙两人必须相邻，则有多少种排法？,1、有8位小朋友排队，先给每个小朋友编号为18。这8位小朋友排成一行，使得8号两边的小朋友的编号之和相等，共有几种不同的排法？,【分析】（通过排队过程的演示，讲解排第的过程。）排队问题涉及前后顺序，所以是排列问题。,A,B,C,D,E,用5个横杠表示位置，在5个人中找出一个人，站在A处，有5种选择。,5,在剩下的4个人中找出一个人，站在B处，有4种选择。,4,同理，在C、D、E中，各有3、2、1种可能存在。所以，总共排法有：54321=120种,3,2,1,甲乙两人必须相邻，可以把他们捆绑起来作为一个人看待。但甲乙也存在前后顺序的排列。所以，甲乙有2种可能。,所以，总共有排法：224=48种,【分析】这是一个条件限制形排列问题。首先需要知道8号小朋友两边的编号个是多少。再对各边小朋友进行排列。,先求8号小朋友两边的编号组合可能：1+2+3+7=28 282=1417中，和为14的组合有（1，6，7）和（2，3，4，5）、（2,5,7）和（1，3，4，6）、（3，4，7）和（1，2，5，6）、（3，5，6）和（1，2，4，7）,同理，另外三种组合也有288种排法。,所以，共有排法：2884=1152种,1、某信号兵有红、黄、蓝、绿四色信号旗各一面。他在旗杆上挂信号旗时每次可以挂一面、两面或者三面，不同颜色、不同顺序代表不同的信号，那么这个信号兵一共可以表示出多少种不同的信号？,1、用3颗红色的珠子，2颗蓝色的珠子，1颗绿色的珠子串成一条手链，一共可以串成多少种不同的手链？拓展：如果手链是圆形的，那么可以有多少种？,【分析】因为可以挂一至三面旗子，所以先要进行分类讨论。,合计有：4+12+24=40种,【分析】这条手链上有6颗珠子，我们可以看成是6个位置，分别把3种颜色的珠子放到这6个位置中。,F,B,C,D,E,5,4,3,2,1,A,6,【分析】如果手链是圆形的，则旋转和翻转相同的只能算一种。因此我们对红色珠子的相邻状况做分类。3颗红色珠子都相邻，则有2种可能；只有2颗红色珠子相邻，则有2种；如果3颗都不相邻，则只有1种串法。所以，总共有5种。,队列问题,1、大刚老师买了7顶不同的帽子发给班上表现好的5个小朋友作为奖品，每人发一顶，请问有多少种不同的发放方法？拓展：如果是5顶不同的帽子，发给7个小朋友，每个小朋友最多一顶帽子，5顶帽子分完，问有多少种不同的方法？,1、书架上有2本不同的英语书，4本不同的语文书，3本不同的数学书，现在要从中取出2本，而且不能是同一科的，一共有多少中不同的取法？,分配与组合问题,A,B,C,D,E,7,6,5,4,3,先让7个小朋友排好队，如上图站好位置。,先让A挑，则有7种可能；接着让B挑，剩下6种可能；最后到E，只剩下三顶帽子可选了。,所以，发放的方法有：76543=2520种,拓展：与上面不同的是小朋友多，帽子少了。我们仍然可以采用上面的方法进行发放。先把5顶不同的帽子排好位置，再让人站到帽子旁边,所以，发放的方法为：21120=2520种,【分析】选出的书，不需要进行排列，所以只是一个组合问题。有三种科目的书，取出的2本书不能是同一科，所以有三种组合。,所以，合计取法有：8+6+12=26种,1、薇儿出门前要选一身衣服，她共有10件不同的上衣，4条不同的裤子，6条不同的裙子（当然，裤子和裙子不能一起穿的）那么薇儿有几种不同的搭配方法？,【分析】这是一个衣服和裤子，或者衣服和裙子的组合问题。每一件衣服可以和不同的裙子或裤子搭配。从上衣中随机选出一件，有10种可能；从裤子中随机选出一条，有4种可能；从裙子中随机选出一条，有6种可能。裙子与裤子中，只能选一条，所以有(6+4=10)种可能,如果把4条裤子变成4双鞋子呢？,分配与组合问题,1、周老师一天要上3个班级的课，每班上1节。如果一天共有9节课，上午5节，下午4节，并且周老师不能连上3节课（第5节和第6节课不算连上），那么，周老师一天上课的所有排课法共有多少种？,【分析】周老师首先必须从9个时段中选出3个，然后把这3个时段分配给3个班级。所以这是一个排列问题。但是，我们还应该考虑“不能连上3节课”的限制条件。,所以，符合条件的排列方式有：504-30=474种,1、用一根34米长的绳子围成一个矩形，且矩形边长都是整数米，共有多少种不同的围法（边长相同的矩形算同一种围法）。,【分析】首先要弄清楚，矩形的长和宽，及周长的关系。其次，根据题目条件，找出长和宽的组合。,周长为34米，则长+宽为：342=17米,因为边长都是整数米，所以长和宽的组合有：（16，1）、（15，2）、（14，3）（13，4）、(12，5)、（11，6）、（10，7）、（9，8），共8种围法。,分配与组合问题,1、有2克、5克、20克的砝码各1个，只用砝码和一架已经调节平衡了的天平，能称出多少种不同的质量？,【分析】首先要搞清楚，砝码放在同一边，则相当于做加法；如果砝码放在天平的两边，则相当于做减法。砝码放一边，可以在3个砝码中取1、2、3个组合；砝码放两边，可以有取1个和2个放另一边的做法。,车站与车票问题,1、连接宁波与上海的高铁中途只停六个车站，那么应该印制多少种车票？,【分析】车票的种类涉及站点和方向，所以是一个排列问题。本题还应该注意，有几个车站（不要把始末站漏下）。,1、在33的网格中（每个格子是个11的正方形）放两枚相同的棋子，每个格子中最多放一枚棋子，共有多少种不同的摆放方法。（如果两种放法能够由旋转而重合，则把它们视为同一种摆放方法）,1、如图，88的方格表中，左边方44部分是黑色小方格，剩下的部分为白色小方格，将整个方格表分为若干块（每块都必须包含整块数小方格，不能把单个的小方格切开），要求每块中白色小方格的数量是黑色小方格数量的3倍，最多可以分成多少块？,排列与图形问题,【分析】对于左图的九宫格，我们没法一下子找到规律，所以可以通过分类来解决。对九宫格按位置进行分类有：中间格、棱格、角格。,1）一枚棋子在中间格，另一棋子可以在角格和棱格2种,2）一枚棋子在角格，另一棋子不在中间格。则2角和2棱共4种组合,3）两枚棋子都在角格，AC和AI两种。,4）两枚棋子都在棱格，只有BF见和BI两种。,所以，总共有10种可能。,【分析】因为每块由白色和黑色小方格按1：3组合，所以要把与白色小方格相邻的黑格尽量单独出来。所以，最多有7种可能。接着需要分析路径是否可行，下面我们可以来试试。,所以，最多可分成7块。,1、A、B两个纸片都被分成了4个区域，用黄、蓝、红三种颜色分别给它们涂色，要求相邻的区域涂色不能相同，A、B两个纸片中哪个涂法较多，有多少种涂法,A,B,1、如图，六边形的六个顶点分别标志为A、B、C、D、E、F，开始的时候“华罗庚金杯赛”六个汉字分别位于A、B、C、D、E、F顶点处，将六个汉字在顶点处任意摆放，最终结果是每个顶点处仍有一个汉字，每个字在开始位置的相邻顶点处，则不同的摆放方法共有多少种？,A,B,C,D,E,F,赛,华,罗,庚,金,杯,排列与图形问题,【分析】判断哪个涂法多，应该很容易。同样都是4块，B不相邻的比A多，所以涂法就多。,【分析】提取题目中的关键信息：每个顶点有一个汉字，每个字在开始位置的相邻顶点处。其次考虑移动方法：相邻字交换位置，或旋转,1）相邻字交换位置分向左或向右2种摆放方法,2）旋转分顺时针和逆时针2种摆放方法,所以，合计不同的摆放方法有4种。,1、如图是某社区的街道示意图，一辆洒水车从A出发不重复地经过所有街道又回到A点，那么洒水车有多少种不同的路线？,排列与图形问题,1）洒水车从A点出发，可以向左或向右，有2种选择,2）不管向左还是向右，在B或C处，可以有3种选择,3）继续到下一个点，剩下2种选择,4）再继续走向下一个点，只有1种选择可以回到A点,所以，洒水车的不同路线有：2321=12种,1、如图所示，两条直线与两个圆交于9个点。从这9个点中选出4个点，要求这4个点中的任意3个点既不在一条直线上，也不在一个圆周上，不同的选法有多少种？,排列与图形问题,【分析】首先我们需要弄清楚，是否可以选择中间那个点。显然是不行的。如果选择的话，不论另外三个点怎样选择，都会有3个点在同一直线上。接着，我们分两种方法来考虑。,方法一：分类讨论法,所以，合计选法有：11+11+44=18种,方法二：提出重复法,3）4个点在一个圆上：不是内圆就是外圆上，所以有两种,所以，合计选法有：36-16-2=18种,1、从下图a的正六边形网格中选出右图的形状，有多少种不同的选法（右图可以旋转）。,排列与图形问题,【分析】观察左右两个图形，都是对称的。平且右边的图形可以有三种不同方向的变换，而每一种方向的选法都是相同的。因此，只要找出一种方向即可。以图b现有方向，与图a一行一行比对，可以有4、5、6、5、4种选法。,图b不旋转的情形，共有选法：4+5+6+5+4=24种,图b可以有3个不同的方向，且每个方向都有相同的选法所以，共有选法：324=72种,