91考试网_排列组合问题.doc

解排列组合问题的常用方法与技巧在排列组合问题中,由于研究的对象独特,研究问题的方法也有所不同,学习它所需的先行知识跟学生熟知的数学知识联系很少,学生学习起来比较困难.排列组合问题的基础是两个基本原理,因此必须学会正确地运用这两个基本原理.原理中提到分步和分类,分类用加法原理,分步用乘法原理,问题在于怎样合理地进行分类、分步,特别是在分类时如何做到既不重复,又不遗漏.找到分步的方法有时是比较困难的,这要求学生周密思考、细心分析.下面结合实例说明排列组合学习中要注意的问题及常用方法与技巧.一.正确理解加法原理及乘法原理运用两个基本原理时需要注意：进行分类时,要求各类办法彼此之间是相互排斥的,不论哪一类办法中的哪一种方法,都能单独完成这件事.只有满足这个条件,才能直接用加法原理,否则不可以.如果完成一件事需要分成几个步骤,各步骤不可缺少,需要依次完成所有步骤才能完成这件事,而各步要求相互独立,即相对于前一步的每一种方法，下一步都有m种不同的方法,那么计算完成这件事的方法数时,就可以直接应用乘法原理.也就是说,类类互斥,步步独立,即分类时用加法原理,分步时用乘法原理.例1 书架上放有3本不同的数学书, 5本不同的语文书, 6本不同的英语书.(1) 若从这些书中任取一本,有多少种不同的取法?(2) 若从这些书中,取数学书、语文书、英语书各一本,有多少种不同的取法?(3) 若从这些书中取不同的科目的书两本,有多少种不同的取法?解 (1)从书架上任取一本书,可以有3类办法:第一类办法是从3本不同数学书中任取1本,有3种方法;第二类办法是从5本不同的语文书中任取1本,有5种方法;第三类办法是从6本不同的英语书中任取一本,有6种方法.根据加法原理,得到的取法种数是.所以从书架上任取一本书的不同取法有14种.(2) 从书架上任取数学书、语文书、英语书各1本,需要分成三个步骤完成,第一步取1本数学, 有3种方法;第二步取1本语文书,有5种方法;第三步取1本英语书,有6种方法.根据乘法原理,得到不同的取法种数是.所以从书架上取数学书、语文书、英语书各1本,有90种不同的方法.(3)从书架上任取不同科目的书两本,可以有3类办法;第一类办法是数学书、语文书各取1本,需要分两个步骤,有35种方法;第二类办法是数学书、英语书各取1本,需要分两个步骤,有36种方法;第三类办法是语文书、英语书各取1本,有56种方法,一共得到不同的取法种数是.即从书架任取不同科目的书两本的不同取法有63种.二.从特殊元素或特殊位置出发正确地进行分类或分步:例2 一名数学教师和四名获奖学生排成一行留影,若老师不排在两端,则共有多少种不同的排法.解法1 从特殊元素出发,由于数学教师是特殊元素,所以他除了两端外还有3个位置可排共有种排法,然后排学生共有种排法,由乘法原理共有（种）.解法2 从特殊位置出发,由于两端是特殊位置,除数学教师外先从四名学生选2人排在两端共有种排法,然后剩余学生及教师排剩余位置共有种排法,由乘法原理共有(种).三.在既有排列又有组合的问题中先组合凑够元素个数后再排列,以避免元素重复使用.例3 在无重复数字四位数中,有两个奇数数字和两个偶数数字的四位数共有_个.分析 因为各有5个奇数数字和5个偶数数字,先取了2个不同的奇数数字,2个不同的偶数数字共有种取法,然后将这取出来的4个数字全排列,共有种方法;其中0在首位时,有种不能构成4位数,所以符合条件的数共有 (个).例4 将5名同学分配到4个不同的课外小组参加活动,每个课外小组至少有一名同学,共有分配方法( )(A)60种 (B)120种 (C)240种 (D)480种分析 此问题相当于有且仅有一个小组含有2个同学,即先取2个人为一组共有种,剩余的每人为一组,这样把5个人变成四组,然后再作排列共有种,所以共有分配方法(种).四.至多、至少类的问题用分类讨论例5 从5男4女中选4位代表,其中至少有2位男同志,且至少有1位女同志,分别到4个不同的工厂调查,不同的分派方法有( )(A)100种 (B)400种 (C)480种 (D)2400种分析 至少有2位男同志,且至少有1位女同志应分两类:第一类中含有2位男同志有2位女同志,共有种;第二类中含有3位男同志有1位女同志,共有种;所以符合要求的选法共有+=2400(种).五.先确定好研究对象例6 有3封信和4个邮筒,则将信全部投入邮筒的所有不同的投法种数为( )(A) (B) (C) (D)分析 解题首先要确定是把3封信作为研究对象还是把4个邮筒作为研究对象,此题很显然要把3封信作为研究,其中每封信投到邮筒都有4种可能性,由乘法原理知选B.六.构造模型巧解排列、组合题数学解题的一个基本思想就是设法将所要求解的问题转化为我们熟悉的或容易解决的问题,这在解排列组合问题时尤显重要.例7 7名同学站成一排,求出甲、乙、丙三人必须相邻的排法总数.分析 这个问题比较简单,但它是排列组合中的相邻问题,用“捆绑法”.先将必须相邻的甲、乙、丙3个人捆在一起视为一个元素,于是由原来的7人变为现在的“5个人”进行全排,然后再对甲乙丙3个人全排,所以排法总数为.例8 由数字1、2、3、4、5、6、7组成无重复数字的七位数.(1)求有3个偶数相邻的7位数的个数;(2)求3个偶数互不相邻的7位数的个数.分析 (1)因为3个偶数2、4、6必须相邻,所以要得到一人符合条件的7位数可以分为如下3步:第1步将1、3、5、7这4个数字排好,有种不同的排法;第2步将2、4、6这3个数字“捆绑”在一起有种不同的“捆绑”方法;第3步将第2步“捆绑”的这个整体“插入”到第一步所排的4个不同数字的5个“间隙”(包括两端的两个位置)中的其中一个位置上,有种不同的“插入”方法.根据乘法原理共有种不同的排法.所以共有720个符合条件的7位数.也可以这样求解:将2、4、6这3个偶数“捆绑”在一起,当作一个元素与其它4个作全排列,有种不同排法,再将“捆绑”在一起的3个偶数作全排列,又有种排法,所以共有个符合条件的7位数.(2)因为3个偶数2、4、6互不相邻,所以要得到符合条件的7位数可以分为如下两步:第1步将1、3、5、7这4个数字排好,有种不同的排法;第2步将2、4、6分别“插入”到第一步排的4个数字的5个“间隙”(包括两端的两个位置)中的3个位置上,有种“插入”方法.根据乘法原理共有种不同的排法.所以共有1440个符合条件的7位数.在解“必须相邻”的题型中同的是“捆绑法”.那么在解“必须不相邻”的题型时,用的是另一种方法叫“插入法”.例9 某台晚会由3个小品和5个相声组成,小品不能连演,且不能排在头尾,则节目的先后顺序有几种不同的排法?分析 该题的解法是先将5个相声排好,有种排法,然后将3个小品插入由它们构成的4个空格中(首尾除外)有种插法,所以共有种不同的排法.例10 由正方体ABCD-A1B1C1D1的8个顶点可构成多少个不同的四面体?分析 这种题型用正向思维比较烦,而用逆向思维(排除法)则很容易了.相对于课本中介绍的加法原理和乘法原理,现在不妨把这种方法叫做“减法原理”.本题的解题是先从8个顶点中选4个,有种选法,然后减去四点共面的选法,就得到四面体个数为.解决几何计数问题,常采用逆向思考法或分类讨论.应充分发挥空间想象能力和图形分析能力,综合运用相关的几何知识,尤其应注意重复现象的正确判断.例11 用1、2、3、4、5组成没有重复数字的五位数,限定1、3、5这三个数必须从左到右依次递减(不一定相邻),可组成多少个这样的五位数.分析 上一题型的方法叫“减法原理”,那么此题的方法可称之为“除法原理”.首先将1、2、3、4、5全排共有种排法,这些排法中包含了1、3、5的全排,而这种排法中只有一种顺序5、3、1符合题目要求,所以本题的结果为(个).例12 现有10个完全相同的球全部分给7个班级,每班至少1个球,问共有多少种不同的分法?解 题目中球的分法共三类.(1)有3个班每个班分到2个球,其余4个班每班分到1个球.其分法种数.(2)有1个班分到3个球;1个班分到2个球;其余5个班每班分到1个球.其分法种数.(3)有1个班分到4个球;其余的6个班每班分到1个球.其分法种数.所以,10个球的分法种数为:.由上面解题过程可以明显感到对这类问题进行分类计算,比较繁锁,若是上题中球的数目较多处理起来将更加困难,因此我们需要寻求一种新的模式解决问题,我们创设这样一种虚拟的情境插板.将10个相同的球排成一行,10个球之间出现了9个空档,现在我们用“档板”把10个球隔成有序的7份,每个班级依次按班级序号分到对应位置的几个球(可能是1个、2个、3个、4个).这样每个班级分到球的个数不在于它所排的位置,借助于这样的虚拟“档板”分配物品的方法称之为插板法.由上述情境分析知,分球的方法实际上为档板的插法:即是在9个空之中插入6个“档板”,其方法种数为.思考:若上题中的球为15个全分给7个班级,每班至少一个球的分法种数是几?()由上述问题的解决看到,这种插板法解决起来非常简单,但同时也提醒大家,这类问题模型要求满足条件相当严格,必须具备以下3个条件:(1)所要分的物品规格必须完全相同.(2)所要分的物品必须分完,决不允许有剩余.(3)参与分物品的每个成员至少分到1个,决不允许出现分不到物品的成员.插板法是用于解决“相同元素”分组问题，且要求每组均“非空”，即要求每组至少一个元素；若对于 “可空”问题，即每组可以是零个元素，又该如何解题呢？例2有8个相同的球放到三个不同的盒子里，共有（ ）种不同方法.A35 B28 C21 D45【解析】：这道题很多同学错选C，错误的原因是直接套用上面所讲的“插板法”，而忽略了“插板法”的适用条件。例2和例1的最大区别是：例1的每组元素都要求“非空”，而例2则无此要求，即可以出现空盒子。其实此题还是用“插板法”，只是要做一些小变化，详解如下：设想把这8个球一个接一个排起来，即 ，共形成9个空档（此时的空档包括中间7个空档和两端2个空档），然后用2个档板把这8个球分成3组，先插第一个档板，由于可以有空盒，所以有9个空档可以插；再插第二个板，有10个空档可以插，但由于两个板是不可分的（也就是说当两个档板相邻时，虽然是两种插法，但实际上是一种分法），所以共 种。例3（1）已知方程 ，求这个方程的正整数解的个数。（2）已知方程 ，求这个方程的非负整数解的个数。【解析】：(1)将20分成20个1，列出来：1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1在这20个数中间的19个空中插入2个板子，将20分成3部分，每一部分对应“1”的个数，按顺序排成 ； ； ；即是正整数解。故正整数解的个数为 ，解法非常简单。【解析】：（2）此题和例2的解法完全相同，请各位考友自己考虑一下。【提示】：今后我们利用“插板法”解决这种相同元素问题时，一定要注意“空”与“不空”的分析，防止掉入陷阱。例3的两题相比较，可以很明显地看出“空”与“不空”的区别。【总结】： “非空”问题插板法原型为：设有 个相同元素，分成 （ ）组，每组至少一个元素的分组方法共有 ；“可空”问题插板法问题原型为：设有 个相同元素，分成 （ ）组，则分组方法共有 种方法。练习1有10级台阶，分8步走完。每步可以迈1级、2级或3级台阶，有多少中走法？（答案为 ）七.如何计算体育比赛中的排列组合问题体育比赛已成为生活中的一个热门话题,以至为素材的数学试题时有出现且趣味盎然.1.比赛结果计数例13 某赛季足球比赛的计分规则是:胜一场,得3分;平一场,得1分;负一场,得0分.一球队打完15场,积33分.若不考虑顺序,该队胜、负、平的情况共有( )(A)3种 (B)4种 (C)5种 (D)6种解 因为只有胜11场负4场、胜10场平3场负2场以及胜9场平6场时，积33分.所以合题意的比赛结果仅有3种,故选(A).例14 4名短跑运动员参加百米跑决赛,若每人都到达终点,则排名顺序有多少种?解 没有并列名次时排名顺序有种;仅有2人并列时排名顺序有种;各有2人并列时排名顺序有种;有3人或4人并列时各有种或种.综上所得,排名顺序共有75种.2.循环赛计数例15 (1999年全国高中数学联赛题)在某次乒乓球单打比赛中,原计划每两名选手恰好比赛一场,但有3名选手各比赛了2场之后就退出了.这样,全部比赛只进行了50场,那么,在上述3名选手之间比赛的场数是( )(A)0 (B)1 (C)2 (D)3解 设共有n名选手,3名选手间比赛r场.因3名选手间的比赛被重复计算,所以依题意得 即 检验知,故选(B).例16 某校举行象棋比赛,按规则,每两人对局一次,胜者得2分,负者得0分,若弈平则各得1分;经过统计,全部选手得分总数应予公布,但4位统计员却分别得出1979、1980、1984、1985四个不同的结果，若其中肯定有一个统计是正确的，则正确的统计结果应是多少？解 设n个人比赛,则比赛有局,且总积分为,应是一个偶数,因此1979与1985是错的.又1980=4544,而1984=23231, 正确的统计结果应是1980.排列组合问题之比赛计数问题比赛计数问题其实不完全是排列组合问题，之所以仍将其归入排列组合，有将错就错，以毒功毒之意。比赛计数问题主要根据比赛规则，分为四类比赛，每类比赛都有对方的解题方法，下面一一介绍。 需决出冠军（或冠、亚军） 比赛场次 淘汰赛 需决出第1、2、3名（或前四名） 比赛场次比赛类型 单循环赛 比赛场次循环赛 双循环赛 比赛