排列、组合复习课.ppt

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

1、1、两个原理：、两个原理： 分类计数加法原理（加法原理）：完分类计数加法原理（加法原理）：完成一件事，有成一件事，有n类办法，在第类办法，在第1类办法中类办法中有有m1种不同的方法，在第种不同的方法，在第2类办法中有类办法中有m2种不同的方法种不同的方法在第在第n类办法中有类办法中有mn种不同的方法种不同的方法,那么完成这件事共有那么完成这件事共有N= m1+ m2 +.+ mn种不同的方法种不同的方法. 分步计数乘法原理（乘法原理）：完成一件事分步计数乘法原理（乘法原理）：完成一件事需要需要 n个步骤，做第个步骤，做第1步有步有m1种不同的方法，做第种不同的方法，做第2 步有步有m2种不同的

2、方法，种不同的方法， 做第做第n步有步有mn种不种不 同的方法，那么完成这件事共有同的方法，那么完成这件事共有N= m1 m2 . mn种不同的方法种不同的方法.两个原理的区别：前者各种方法相互独立，两个原理的区别：前者各种方法相互独立，用其中的任何一种方法都可以完成这件事；后者用其中的任何一种方法都可以完成这件事；后者每个步骤相互依存，只有每个步骤都完成了，这每个步骤相互依存，只有每个步骤都完成了，这件事才算完成。对前者的应用，如何分类是关键，件事才算完成。对前者的应用，如何分类是关键，如排数时有如排数时有0没有没有0，排位时的特殊位置等；后者，排位时的特殊位置等；后者一般体现在先选后排。一

3、般体现在先选后排。 定义：一般地，从定义：一般地，从n个不同元素中取出个不同元素中取出m个元素，按照一定的顺序排成一列，叫个元素，按照一定的顺序排成一列，叫做从做从n个不同元素中取出个不同元素中取出m个元素的一个个元素的一个排列，所有排列的个数，叫做从排列，所有排列的个数，叫做从n个不同个不同元素中取出元素中取出m个元素的排列数，用个元素的排列数，用 表示表示.mnA(1)(2)(1)(,),!()!mnnnmnAn nnnmnmNmnAnnAnm、，特别地（常用于证明等式）定义：一般地，从定义：一般地，从n个不同元素中取出个不同元素中取出m个元素，并成一组，叫做从个元素，并成一组，叫做从n个

4、不同元素个不同元素中取出中取出m个元素的一个组合。所有组合个元素的一个组合。所有组合的个数，叫做从的个数，叫做从n个不同元素中取出个不同元素中取出m个个元素的组合数，用元素的组合数，用 表示。表示。mnC011(1)(2)(1)!(,)!()!,1,mmnnmmmnmn mmmmnnnnnnAn nnnmCAmnCnmNmnm nmCCCCCC、排列与组合的区别：前者先选出元素，排列与组合的区别：前者先选出元素，再按一定的顺序排成一列，后者只要选再按一定的顺序排成一列，后者只要选出元素并成一组即可；两个排列相同当出元素并成一组即可；两个排列相同当且仅当两个排列的元素完全相同，且元且仅当两个排列

5、的元素完全相同，且元素的顺序也相同，如素的顺序也相同，如abc与与acb是不同的是不同的排列；两个组合相同，只要元素完全相排列；两个组合相同，只要元素完全相同，可从集合的观点来看，如同，可从集合的观点来看，如a,b,ca,c,b是同一集合。是同一集合。直接法：特殊元素法、特殊位置法（两者直接法：特殊元素法、特殊位置法（两者适用某一个或几个元素在指定的位置或不在适用某一个或几个元素在指定的位置或不在指定的位置）、捆绑法（两个或两个以上的指定的位置）、捆绑法（两个或两个以上的元素必须相邻）、插空法元素必须相邻）、插空法 （两个或两个以上（两个或两个以上的元素必须不相邻）、挡板法（相同的元素的元素必

6、须不相邻）、挡板法（相同的元素分成若干部分，每部分至少一个）分成若干部分，每部分至少一个） 间接法（排除法间接法（排除法,正难则反的思想正难则反的思想）例例1 1 学校组织老师学生一起看电影，同一排电影票学校组织老师学生一起看电影，同一排电影票1212张。张。8 8个学生，个学生，4 4个老师，要求老师在学生中间，且老师互不个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的坐法？相邻，共有多少种不同的坐法？解解 先排学生共有先排学生共有A A8 88 8 种排法种排法, ,然后把老师插入学生然后把老师插入学生之间的空档，共有之间的空档，共有7 7个空档可插个空档可插, ,选其中的选其

7、中的4 4个空档个空档, ,共共有有 A A7 74 4种选法种选法. .根据乘法原理根据乘法原理, ,共有的不同坐法为共有的不同坐法为A A8 88 8A A7 74 4 种种. .结论结论1 1 插空法插空法: :对于某两个元素或者几个元素要求对于某两个元素或者几个元素要求不相邻的问题不相邻的问题, ,可以用插入法可以用插入法. .即先排好没有限制条即先排好没有限制条件的元素件的元素, ,然后将有限制条件的元素按要求插入排好然后将有限制条件的元素按要求插入排好元素的空档之中即可元素的空档之中即可. .分析分析 此题涉及到的是不相邻问题此题涉及到的是不相邻问题, ,并且是对老师有特殊并且是对

8、老师有特殊的要求的要求, ,因此老师是特殊元素因此老师是特殊元素, ,在解决时就要特殊对待在解决时就要特殊对待. .所涉及问题是排列问题所涉及问题是排列问题. .例例2 2 5 5个男生个男生3 3个女生排成一排个女生排成一排,3,3个女生要排在一起个女生要排在一起, ,有多少种不同的排法有多少种不同的排法? ? 33P66P3366PP解解 因为女生要排在一起因为女生要排在一起, ,所以可以将所以可以将3 3个女生看成是个女生看成是一个人一个人, ,与与5 5个男生作全排列个男生作全排列, ,有有A A6 66 6 种排法种排法, ,其中女生其中女生内部也有内部也有A A3 33 3 种排法

9、种排法, ,根据乘法原理根据乘法原理, ,共有共有A A6 66 6A A3 33 3种不同种不同的排法的排法. .结论结论2 2 捆绑法捆绑法: :要求某几个元素必须排在一起的问要求某几个元素必须排在一起的问题题, ,可以用捆绑法来解决问题可以用捆绑法来解决问题. .即将需要相邻的元素合即将需要相邻的元素合并为一个元素并为一个元素, ,再与其它元素一起作排列再与其它元素一起作排列, ,同时要注意同时要注意合并元素内部也可以作排列合并元素内部也可以作排列. .分析分析 此题涉及到的是排队问题此题涉及到的是排队问题, ,对于女生有特殊的限对于女生有特殊的限制制, ,因此因此, ,女生是特殊元素女

10、生是特殊元素, ,并且要求她们要相邻并且要求她们要相邻, ,因此因此可以将她们看成是一个元素来解决问题可以将她们看成是一个元素来解决问题. .例例3 3 高二年级高二年级8 8个班个班, ,组织一个组织一个1212个人的年级学生分会个人的年级学生分会, ,每班要求至少每班要求至少1 1人人, ,名额分配方案有多少种名额分配方案有多少种? ?解解 此题可以转化为此题可以转化为: :将将1212个相同的白球分成个相同的白球分成8 8份份, ,有多有多少种不同的分法问题少种不同的分法问题, ,因此须把这因此须把这1212个白球排成一排个白球排成一排, ,在在1111个空档中放上个空档中放上7 7个隔

11、板个隔板, ,每个空档最多放一个每个空档最多放一个, ,即即可将白球分成可将白球分成8 8份份, ,显然有显然有 种不同的放法种不同的放法, ,所以名额所以名额分配方案有分配方案有 种种. .711C711C结论3 隔板法隔板法: :解决指标分配问题解决指标分配问题分析分析 此题若直接去考虑的话此题若直接去考虑的话, ,就会比较复杂就会比较复杂. .但如果但如果我们将其转换为等价的其他问题我们将其转换为等价的其他问题, ,就会显得比较清楚就会显得比较清楚, ,方法简单方法简单, ,结果容易理解结果容易理解. .例例4 4 袋中有袋中有5 5分不同硬币分不同硬币2323个个,1,1角不同硬币角不

12、同硬币1010个个, ,如果从袋中取出如果从袋中取出2 2元钱元钱, ,有多少种取法有多少种取法? ?解解 把所有的硬币全部取出来把所有的硬币全部取出来, ,将得到将得到 0.050.0523+0.1023+0.1010=2.1510=2.15元元, ,所以比所以比2 2元多元多0.150.15元元, ,所所以剩下以剩下0.150.15元即剩下元即剩下3 3个个5 5分或分或1 1个个5 5分与分与1 1个个1 1角角, ,所以所以共有共有 种取法种取法. .110123323CCC结论结论4 4： 剩余法剩余法: :在组合问题中在组合问题中, ,有多少取法有多少取法, ,就有多就有多少种剩法

13、少种剩法, ,他们是一一对应的他们是一一对应的, ,因此因此, ,当求取法困难时当求取法困难时, ,可转化为求剩法可转化为求剩法. .分析分析 此题是一个组合问题此题是一个组合问题, ,若是直接考虑取钱的问若是直接考虑取钱的问题的话题的话, ,情况比较多情况比较多, ,也显得比较凌乱也显得比较凌乱, ,难以理出头绪难以理出头绪来来. .但是如果根据组合数性质考虑剩余问题的话但是如果根据组合数性质考虑剩余问题的话, ,就就会很容易解决问题会很容易解决问题. .例例5、9人排成一行，下列情形分别有多少种排法？人排成一行，下列情形分别有多少种排法？ 甲不站排头，乙不站排尾甲不站排头，乙不站排尾点评：

14、利用对称的思想，点评：利用对称的思想，（一）先排甲（特殊元素优先考虑）（一）先排甲（特殊元素优先考虑）（二）先排尾位（二）先排尾位(特殊位置优先考虑）特殊位置优先考虑） (三）间接法三）间接法练习：练习： 用用0，1，2，3，4这五个数，组成没有重复这五个数，组成没有重复数字的三位数，其中数字的三位数，其中1不在个位的数共有不在个位的数共有_种种。 分析分析：五个数组成三位数的全排列有五个数组成三位数的全排列有 个，个，0排在首位的排在首位的有有 个个 ，1排在末尾的有排在末尾的有 ，减掉这两种不合条件的排，减掉这两种不合条件的排法数，再加回百位为法数，再加回百位为0同时个位为同时个位为1的排

15、列数的排列数 （为什么？）（为什么？）故共有故共有 种。种。24A24A35A13A392132435AAA甲乙必须排在一起，丙丁不能排在一起甲乙必须排在一起，丙丁不能排在一起点评：小团体排列问题中，先整体后局点评：小团体排列问题中，先整体后局部，再结合不相邻问题的插空处理。部，再结合不相邻问题的插空处理。练习练习：(2005 辽宁辽宁)用、用、组成没有重复数字的八位数，要求与相邻，组成没有重复数字的八位数，要求与相邻，与相邻，与相邻，而与不相邻，与相邻，与相邻，而与不相邻，这样的八位数共有这样的八位数共有_个（用数字作答）个（用数字作答） 将与，与，与捆绑在一起排成一列将与，与，与捆绑在一起

16、排成一列有有 种，再将、插入种，再将、插入4个空位中的两个个空位中的两个有有 种，故有种，故有 种种 482333A1224A5761248引申引申:用、组成没有重复数字用、组成没有重复数字的六位数，要求与相邻，与相邻，与的六位数，要求与相邻，与相邻，与相邻，现将相邻，现将7、8 插进去，仍要求与相邻，与插进去，仍要求与相邻，与相邻，与相邻，那么八位数共有相邻，与相邻，那么八位数共有_个个（用数字作答）（用数字作答）A3323（A42+A41A22）=960 甲乙丙从左到右排列（固定顺序问题）甲乙丙从左到右排列（固定顺序问题）分析：分析：96993360480ANAA评：对于某几个元素顺序一定

17、的排列问题，评：对于某几个元素顺序一定的排列问题，可先将这几个元素与其它元素一同进行排列，可先将这几个元素与其它元素一同进行排列，然后用总的排列数除以这几个元素的全排列数然后用总的排列数除以这几个元素的全排列数.l引申：有三人从左到右顺序一定引申：有三人从左到右顺序一定 93369999335080320ANCCAA 点评：定序问题除法处理点评：定序问题除法处理分析：分析： 练习：练习： 有有4名男生，名男生，3名女生。名女生。3名女生名女生高矮互不等，高矮互不等，将将7名学生排成一行，要求从左到右，女生从矮到高名学生排成一行，要求从左到右，女生从矮到高排列，有多少种排法？排列，有多少种排法？

18、前排三人，中间三人，后排三人前排三人，中间三人，后排三人 分析：分析：33399639NAAAA引申：前排一人，中间二人，后排六人引申：前排一人，中间二人，后排六人点评：分排问题直排处理点评：分排问题直排处理练习练习： 七人坐两排座位，第一排坐七人坐两排座位，第一排坐3人，第二排坐人，第二排坐4人，则有多少种不同的坐法？人，则有多少种不同的坐法？ 分析分析：7个人，可以在前后排随意就坐，再无个人，可以在前后排随意就坐，再无其他限制条件，故两排可看作一排处理，所以其他限制条件，故两排可看作一排处理，所以不同的坐法有不同的坐法有 种种.77A分成甲、乙、丙三组，甲组分成甲、乙、丙三组，甲组4人，乙

19、组人，乙组3人，丙人，丙组组2人。人。 分析：分析： 4329521260NC C C432395237560NCCCA3339631680NCCC引申：引申：分成甲、乙、丙三组，一组分成甲、乙、丙三组，一组4人，一人，一组组3 人，人， 一组一组2人人分析：分析： 分成甲、乙、丙三组，每组分成甲、乙、丙三组，每组3人。人。分析：分析：分成三组，每组分成三组，每组3人人分析：分析：33396333280CCCNA22542922378CCNCA引申：分成三组，一组引申：分成三组，一组5人，另两组各两人人，另两组各两人分析：分析：点评：局部均分无序问题易出错点评：局部均分无序问题易出错 实验法（

20、穷举法）实验法（穷举法） 题中附加条件增多，直接解决困难时，用实验逐题中附加条件增多，直接解决困难时，用实验逐步寻求规律有时也是行之有效的方法。步寻求规律有时也是行之有效的方法。 例例 将数字将数字1，2，3，4填入标号为填入标号为1，2，3，4的四的四个方格内，每个方格填个方格内，每个方格填1个，则每个方格的标号与个，则每个方格的标号与所填的数字均不相同的填法种数有（所填的数字均不相同的填法种数有（ ）A.6 B.9 C.11 D.23分析：此题考查排列的定义，由于附加条件较多，解法较为困难，分析：此题考查排列的定义，由于附加条件较多，解法较为困难，可用实验法逐步解决。可用实验法逐步解决。第

21、一方格内可填第一方格内可填2或或3或或4。如填。如填2，则第二方格中内可填，则第二方格中内可填1或或3或或4。若第二方格内填若第二方格内填1，则第三方格只能填，则第三方格只能填4，第四方格应填，第四方格应填3。若第二方格内填若第二方格内填3，则第三方格只能填，则第三方格只能填4，第四方格应填，第四方格应填1。同理，若第二方格内填同理，若第二方格内填4，则第三方格只能填，则第三方格只能填1，第四方格应，第四方格应填填3。因而，第一格填。因而，第一格填2有有3种方法。种方法。不难得到，当第一格填不难得到，当第一格填3或或4时也各有时也各有3种，所以共有种，所以共有9种。种。练练 习习 （不对号入座

22、问题）（不对号入座问题）（1）（）（2004湖北）将标号为湖北）将标号为1，2，3，10的的10个球放入标号为个球放入标号为1，2，3，10的的10个盒子中，个盒子中，每个盒内放一个球，恰好有每个盒内放一个球，恰好有3个球的标号与其所在盒子个球的标号与其所在盒子的标号不一致的放入方法有的标号不一致的放入方法有_种种3102C（2）编号为）编号为1、2、3、4、5的五个球放入编号为的五个球放入编号为1、2、3、4、5的五个盒子里，至多有的五个盒子里，至多有2个对号入个对号入座的情形有座的情形有_种种109直接法直接法：3455552944109CCC 间接法间接法：53551 1109AC 住店

23、法住店法解决解决“允许重复排列问题允许重复排列问题”要注意区分两类元素：要注意区分两类元素： 一类元素可以重复，另一类不能重复，把不能重复一类元素可以重复，另一类不能重复，把不能重复的元素看作的元素看作“客客”，能重复的元素看作，能重复的元素看作“店店”，再利，再利用乘法原理直接求解。用乘法原理直接求解。例例6 七名学生争夺五项冠军，每项冠军只能由一七名学生争夺五项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有（人获得，获得冠军的可能的种数有（ ）A. B. C D.分析：因同一学生可以同时夺得分析：因同一学生可以同时夺得n项冠军，故学生可重复排列，项冠军，故学生可重复排列，将七名学生看

24、作将七名学生看作7家家“店店”，五项冠军看作，五项冠军看作5名名“客客”，每个，每个“客客”有有7种住宿法，由乘法原理得种住宿法，由乘法原理得 种。种。注：对此类问题，常有疑惑，为什么不是注：对此类问题，常有疑惑，为什么不是 呢？呢？57577557A57C75用分步计数原理看，用分步计数原理看，5是步骤数，自然是指数。是步骤数，自然是指数。 对应法对应法例例7 在在100名选手之间进行单循环淘汰赛（即一场名选手之间进行单循环淘汰赛（即一场比赛失败要退出比赛），最后产生一名冠军，问要比赛失败要退出比赛），最后产生一名冠军，问要举行几场？举行几场？ 分析：要产生一名冠军，需要淘汰掉冠军以外的分析

25、：要产生一名冠军，需要淘汰掉冠军以外的所有选手，即要淘汰所有选手，即要淘汰99名选手，淘汰一名选手需要名选手，淘汰一名选手需要进行一场比赛，所以淘汰进行一场比赛，所以淘汰99名选手就需要名选手就需要99场比赛。场比赛。例例8、高二（、高二（1）班从）班从7人中选人中选4人组成人组成4100m接力赛接力赛其中甲乙二人不跑中间两棒，有多少种选法？其中甲乙二人不跑中间两棒，有多少种选法？ 点评：排列组合综合题的解法应遵循在分类的基础上，点评：排列组合综合题的解法应遵循在分类的基础上，先组合后排列的原则，分类与分步相结合，分类时做先组合后排列的原则，分类与分步相结合，分类时做到不重复不遗漏到不重复不遗

26、漏.练习练习:（徐州二检）从（徐州二检）从6人中选人中选4人组成人组成4100m接力赛，接力赛，其中甲跑第一棒，乙不跑最后一棒，有多少种选法？其中甲跑第一棒，乙不跑最后一棒，有多少种选法？分析：（一）直接法分析：（一）直接法 （二）间接法（二）间接法48例例9、从正方体的、从正方体的6个面中任选个面中任选3个，其中个，其中2个面不个面不相邻的选法有多少种？相邻的选法有多少种？练习：从正方体的练习：从正方体的8个顶点中选个顶点中选4个作四面体，个作四面体，则不同的四面体的个数为则不同的四面体的个数为 。58练习：练习：（南通一检）一个三位数，其十位上的数（南通一检）一个三位数，其十位上的数字既小

27、于百位上的数字也小于个位上的数字字既小于百位上的数字也小于个位上的数字（如，等），那么这样的三位数（如，等），那么这样的三位数有有 个个285 练习练习1 1 某人射击某人射击8 8枪，命中枪，命中4 4枪，那么命中的枪，那么命中的4 4枪中恰有枪中恰有3 3枪是连中的情形有几种？枪是连中的情形有几种？练习练习2 2 一排一排8 8个座位，个座位，3 3人去坐，每人两边至少有一个空人去坐，每人两边至少有一个空座的坐法有多少种？座的坐法有多少种？练习练习3 3 马路上有编号为马路上有编号为1,2,3,1,2,3,1010的十只路灯的十只路灯, ,为节为节约电而不影响照明约电而不影响照明, ,可以

28、把其中的三只路灯关掉可以把其中的三只路灯关掉, ,但不但不能同时关掉相邻的两只或三只能同时关掉相邻的两只或三只, ,也不能关掉马路两端的也不能关掉马路两端的灯灯, ,问满足条件的关灯方法有多少种？问满足条件的关灯方法有多少种？练习练习4 4 A A、B B、C C、D D、E E五人站成一排，如果五人站成一排，如果B B必须站在必须站在A A的右边，那么不同的站法有多少种？的右边，那么不同的站法有多少种？ 练习练习5 5 某电路有某电路有5 5个串联的电子元件个串联的电子元件, ,求发生故障的不求发生故障的不同情形数目同情形数目? ?（A52）（A43）（C63）（A55/2）（251=31）

29、三、小结小结 本节课，我们对有关排列组合的几种常见的基本本节课，我们对有关排列组合的几种常见的基本解法加以复习巩固。排列组合历来是学习中的难点，解法加以复习巩固。排列组合历来是学习中的难点，通过我们平时做的历届高考题，不难发现其应用题的通过我们平时做的历届高考题，不难发现其应用题的特点是条件隐晦，难以挖掘，题目多变，解法独特，特点是条件隐晦，难以挖掘，题目多变，解法独特，数字庞大，难以验证。同学们只有对基本的几种解法数字庞大，难以验证。同学们只有对基本的几种解法熟练掌握，然后再本着先分类再分步的原则，把复杂熟练掌握，然后再本着先分类再分步的原则，把复杂的问题简单化，才能做到举一反三，触类旁通，进而的问题简单化，才能做到举一反三，触类旁通，进而为下一章概率的学习打下坚实的基础。为下一章概率的学习打下坚实的基础。