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

1、排列与组合,2010信息学奥赛问题求解专题,例1 从甲地到乙地,可以乘火车,也可以乘汽车,还可以乘轮船。一天中，火车有4班，汽车有2班，轮船有3班。那麽，一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法？,解：因为一天中乘火车有4种走法，乘汽车有2种走法，乘轮船有3种走法，每一种走法都可以从甲地到乙地，因此，一天中乘坐这些交通工具从甲地到乙地共有 4+2+3=9 种不同的走法。,加法原理：,做一件事，完成它可以有 n 类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法， ，在第n类办法中有mn种不同的方法。那么完成这件事共有 N= m1+ m2+ + mn 种不同

2、的方法。,例2 由 A 村去 B 村的道路有3条，由 B 村去 C 村的道路 有2条。从 A 村经 B 村去 C 村，共有多少种不同的走法？,解：从A 村去 B 村有3种不同的走法，按这3种走法中的每一种走法到达B村后，再从 B村到达C 村又有2种不同的走法。因此，从 A 村经 B 村去 C 村共有 3 2 = 6 种不同的走法。,乘法原理：,做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法， ，做第n步有mn种不同的方法。那么完成这件事共有 N= m1 m2 mn 种不同的方法。,分类计数原理(加法原理) ：做一件事情，完成它可以有n类办法，在第一类办

3、法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn。种不同的方法，那么完成这件事共有N=m1+m2+mn种不同的方法。 分步计数原理（乘法原理） ：做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事有N=m1*m2*mn种不同的方法。,分类计数原理与“分类”有关，各种方法相互独立，用其中任何一种方法都可以完成这件事； 分步计数原理与“分步”有关，各个步骤相互依存，只有各个步骤都完成了，这件事才算完成,解: 从书架上任取数学书与语文书各一本,可以分成两个步骤完成： 第一步取一本数学书，

4、有6种方法； 第二步取一本语文书，有5种方法。 根据乘法原理，得到不同的取法的种数是： N= m1 m2 = 65 = 30,例1 书架上层放有 6 本不同的数学书，下层放有 5 本不同的语文书。 从中任取一本，共有多少种不同的取法？ 从中任取数学书与语文书各一本，共有多少种不同的取法？,例2 有数字 1，2，3，4，5 可以组成多少个三位数（各位上的数字许重复）？,解：要组成一个三位数可以分成三个步骤完成： 第一步确定百位上的数字，从5个数字中任选一个数字，共有5种选法； 第二步确定十位上的数字，由于数字允许重复，这仍有5种选法； 第二步确定十位上的数字，同理，它也有5种选法。 根据乘法原理

5、，得到组成的三位数的个数是： N = 5 5 5 = 53 = 125,例3 有不同的语文书9本，不同的数学书7本，不同的物理书5本，从中任取两种不同类的书，共有多少种不同的取法？,解：每次取出的两本书中： 含 1 本语文书和 1 本数学书的共有 9 7 = 63 种取法； 含 1 本数学书和 1 本物理书的共有 7 5 = 35 种取法； 含 1 本语文书和 1 本物理书的共有 9 5 = 45 种取法。,由加法原理得 63 + 35 + 45 = 143,排列,排列的概念：从n个不同元素中，任取m(mn)个元素(这里的被取元素各不相同)，按照一定的顺序排成一列，叫做从n个不同元素中取出m个

6、元素的一个排列。 排列数的定义：从n个不同元素中，任取m(mn)个元素的所有排列的个数叫做从n个元素中取出m个元素的排列数，用符号 表示。,排列数公式：,全排列数：,规定：0！1,计算用,证明用,组合,组合的概念：一般地，从n个不同元素中取出m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合 组合数的概念：从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数用符号 表示,组合,组合数公式： 或 (n，mN，且mn) 组合数的性质1： 规定： ：=1； 性质2：,常用解题方法及适用题目类型,直接法：特殊元素法、特殊位置法（两者适用某一个

7、或几个元素在指定的位置或不在指定的位置）捆绑法（两个或两个以上的元素必须相邻）插空法 （两个或两个以上的元素必须不相邻）挡板法（相同的元素分成若干部分，每部分至少一个） 间接法（排除法）,一、相邻问题捆绑法,把题中规定相邻的几个元素并为一组（当作一个元素）参与排列 例1：A、B、C、D、E五人并排成一排，如果A、B必须相邻且B在A的右边，那么不同的排法有（） A60 B48 C36 D24 分析：把A、B视为1人，且B固定在A的右边，则本题相当于4人全排列，即 24 引申：如没有说B要在A的右边则A44A22,二、相离问题插空法,元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把

8、规定相离的几个元素插入上述几个元素间的空位和两端。 例2：七个站成一排，如果甲、乙二人必须不相邻，则排法有（） A1440 B3600 C4820 D4800 分析：除甲、乙外，其余5人排列为种，再用甲、乙去插六个空位，有种，不同排法种数为 3600。,三、定序问题对称法,在排列问题中限制某几个元素必须保持一定的顺序，可用对称思想解题，先排后除， 。 例3：A、B、C、D、E五个站一排，B必须站A右边，则不同的排法 （ ） A25 B60 C90 D120 分析：五个全排列，B在A右边和B在A左边排法数相同，即 60。 引例：晚会原定的5个节目已排成节目单，开演前又加了2个节目，若将这2个节目

9、插入原节目单中，则不同的插法有（）种。 分析：原定的5个节目顺序已定，则不同的插法有,四、定位问题优先法,某个（或几个）元素要排在指定位置，可先排这个（或几个）元素再排其他元素。 例4：一个老师和四名学生排成一排，老师不在两端，则不同的排法有（）种。 分析：老师在中间3个位置上选一个位置有 种，四名同学在其余四个位置有 种， 其 72种。,五、多排问题单排法,把元素排成几排的问题，可归纳为一排考虑，再分段处理。 例5：8人站前后2排，每排4人，其中某2人站在前排，某1人站在后排有（）种排法。 分析：看成一排，某2个人在前半段4个位置中选排2个，有 种，某1人在后半段4个人位置中选一个有 种，其

10、余5人在余下5个位上有种，故共有 5760种排法。,六、乱座问题分步法,把元素排列到指定号码位置上，可先把某个元素按规定排入，第2步再排另一个元素，如此继续下去，依次即可完成。 例6：将数了1，2，3，4，填入标号为1，2，3，4的四个方格，每格填一个数，则每个方格的标号与所填数字均不相同的填法有（）种。 分析：先把1填入方格，符合条件有3种，第2步把被填入方格的对应数字填入其他3个方格，又有3种方法，第3步填余下的2个数字，只有1种填法，故共有3319种。 引申：n封装入n个信封时全部装错的装法总数为。 通常称为伯努利一欧拉错装信封问题，又称为乱序排列，即把n个元素的排列a1，a2，L，an

11、重新排列，使每个元素都不在原来的位置上的排列问题。,(NOIP 2002) 在书架上放有编号为1，2，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。 例如：n=3时： 原来位置为：1 2 3 放回去时只能为：3 l 2或2 3 1这两种 问题：求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法),44,七、多元问题分类法,元素多，取出的情况也有多种，可按结果要求，分成不相容几类情况，分别计算，最后总计。 例7：由0，1，2，3，4，5组成没有重复数字的六位数，其中个位数字小于十位数字的共有（）个。 分析：个位数字只能是0，1，2，3，4共有5

12、种情况，分别有 个，合并总计300个。,用排除法也行，6个数全排，去掉首位是零的，然后一半即可 （A66-A55）/2=（6*5*4*3*2*1-5*4*3*2*1）/2=300,八、“至少”问题间接法,例8：从4台甲型和5台乙型电视机中任取3台，其中至少要甲、乙电视各一台，则不同取法共有（）种。 分析：至少各一台反面就是分别只取一种型号，不取另一种型号，故 种。,九、条件问题排除法,在被选总数中，只有一部分符合条件，可从总数中减去不合条件者。 例9：正六边形中心和顶点共7个点，以其中3个点为顶点的三角形共有（）个。 分析：7点取3点有 种，但有3组3点共线，不构成三角形，故 种。,十、选排问

13、题，先取后排法。,从n类元素中取出符合题意的n个元素，再安排到一定位置上，可用先取后排法。 例10：四个不同球放入编号1，2，3，4四个盒子中，则恰有一个空盒的放法共有（）种。 分析：先取4个球中的2个为一组，另2组各1球有 种，然后排列，在4个盒中每次排3组有种，共有 144种。,十一、指标问题用“隔板法”,例11：将10个保送生预选指标分配给某重点中学高三年级六个班，每班至少一名，共有多少种分配方案？ 分析：将10个名额并成一排，名额之间有9个空，用5块隔板插入9个空，就可将10个名额分成6部分，每一种插法就对应一种分配方法，故有 种方案。 注意：隔板法与插空法是不同的，隔板法只适用于相同