1排列组合问题的基本类型及解题方法解决排列组合问题要讲究策略,首先要认真审题,弄清楚是排列(有序)还是组合(无序),还是排列与组合混合问题。其次,要抓住问题的本质特征,准确合理地利用两个基本原则进行“分类与分步”。加法原理的特征是分类解决问题,分类必须满足两个条件:①类与类必须互斥(不相容),②总类必须完备(不遗漏);乘法原理的特征是分步解决问题,分步必须做到步与步互相独立,互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略,在实际操作中往往是“步”与“类”交叉,有机结合,可以是类中有步,也可以是步中有类。以上解题思路分析,可以用顺口溜概括为:审明题意,排(组)分清;合理分类,用准加乘;周密思考,防漏防重;直接间接,思路可循;元素位置,特殊先行;一题多解,检验真伪。(一)特殊元素的“优先安排法”对于特殊元素的排列组合问题,一般先考虑特殊元素,再考虑其他元素的安排。在操作时,针对实际问题,有时“元素优先”,有时“位置优先”。例1:0,2,3,4,5这五个数字,组成没有重复数字的三位数,其中偶数共有几个?解法一:(元素优先)分两类:第一类,含0,0在个位有24A种,0在十位有1123AA种;第二类,不含0,有1223AA种。故共有2111242323(AAA)+AA30种。注:在考虑每一类时,又要优先考虑个位。解法二:(位置优先)分两类:第一类,0在个位有24A种;第二类,0不在个位,先从两个偶数中选一个放个位,再选一个放百位,最后考虑十位,有111233AAA种。故共有21114233A+AAA=30(二)总体淘汰法对于含有否定词语的问题,还可以从总体中把不符合要求的除去,此时应注意既不能多减也不能少减,例如在例1中也可以用此法解答:5个数字组成三位数的全排列为35A,排好后发现0不能在首位,而且3和5不能排在末尾,这两种不合题意的排法要除去,故有30个偶数.(三)合理分类与准确分步解含有约束条件的排列组合问题,应按元素的性质进行分类,事情的发生的连续过程分步,做到分类标准明确,分布层次清楚,不重不漏.例2:5个人从左到右站成一排,甲不站排头,乙不站第二个位置,不同的站法有解:由题意,可先安排甲,并按其进行分类讨论:(1)若甲在第二个位置上,则剩下的四人可自由安排,有44A种方法;(2)若甲在第三个或第四个位置上,则根据分布计数原理不同的站法有113333AAA种站法;再根据分类计数原理,不同的站法共有:21134333AAAA78种.(四)相邻问题:捆绑法对于某些元素要求相邻排列的问题,可先将相邻元素捆绑成整体并看作一个元素再与其它元素进行排列,同时对相邻元素内部进行自排。例3:5个男生3个女生排成一列,要求女生排一起,共有几种排法?解:先把3个女生捆绑为一个整体再与其他5个男生全排列。同时,3个女生自身也应全排列。由乘法原理共有6363AA种。(五)不相邻问题用“插空法”2对于某几个元素不相邻的排列问题,可先将其他元素排好,再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可(注意有时候两端的空隙的插法是不符合题意的).例4:5个男生3个女生排成一列,要求女生不相邻且不可排两头,共有几种排法?解:先排无限制条件的男生,女生插在5个男生间的4个空隙,由乘法原理共有5354AA种。注意:①分清“谁插入谁”的问题。要先排无限制条件的元素,再插入必须间隔的元素;②数清可插的位置数;③插入时是以组合形式插入还是以排列形式插入要把握准。例5:马路上有编号为1,2,3,9的9盏路灯,现要关掉其中的三盏,但不能同时关掉相邻的两盏或三盏,也不能关两端的路灯,则满足要求的关灯方法有几种?解:由于问题中有6盏亮3盏暗,又两端不可暗,故可在6盏亮的5个间隙中插入3个暗的即可,有35C种。(六)顺序固定问题用“除法”或选位不排或先定后插对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素之间的全排列数。或先在总位置中选出顺序一定元素的位置而不参加排列,然后对其它元素进行排列。也可先放好顺序一定元素,再一一插入其它元素。例6:5人参加百米跑,若无同时到达终点的情况,则甲比乙先到有几种情况?解法一:先5人全排有55A种,由于全排中有甲、乙的全排种数22A,而这里只有1种是符合要求的,故要除以定序元素的全排列22A种,所以有5522A=60A种。解法二:先在5个位置中选2个位置放定序元素(甲、乙)有25C种,再排列其它3人有33A,由乘法原理得共有2353CA=60种。解法三:先固定甲、乙,再插入另三个中的第一人有3种方法,接着插入第二人有4种方法,最后插入第三人有5种方法。由乘法原理得共有345=60种。(七)“小团体”排列,先“团体”后整体对于某些排列问题中的某些元素要求组成“小团体”时,可先按制约条件“组团”并视为一个元素再与其它元素排列。例7:四名男歌手与两名女歌手联合举行一场演唱会,演出的出场顺序要求两名女歌手之间有两名男歌手,则出场方案有几种?解:先从四名男歌手中选2人排入两女歌手之间进行“组团”有2242AA种,把这个“女男男女”小团体视为1人再与其余2男进行排列有33A种,由乘法原理,共有2242AA33A种.(八)分排问题用“直排法”把n个元素排成若干排的问题,若没其他的特殊要求,可用统一排成一排的方法来处理.例8:7个人坐两排座位,第一排坐3人,第二排坐4人,则有种排法.解:7个人,可以在前后两排随意就座,没有其他的限制条件,故两排可以看成一排来处理,所以不同的坐法有77A.(九)逐步试验法如果题中附加条件增多,直接解决困难,用试验法寻找规律有时也是行之有效的方法.例9:将数字1,2,3,4填入标号为1,2,3,4的四个方格内,每个方格填一个,则每个方格的标号与所填的数字均不相同的填法种数有种。解:此题考查排列的定义,由于附加条件较多,解法较为复杂,可用试验法逐步解决.第一方格内可填2或3或4.如填2,则第二方格内可填1或3或4.若第二方格内填1,3则第三方格内只能填4,第四方格内填3.若第二方格填3,则第三方格应填4,第四方格应填1.同理,若第二方格填4,则第三、四方格应分别填3,1。因而第一方格填2共有3种方法。同理,第一格填3或4也各有3种,所以一共有9种方法。(十)探索规律法对于情况复杂,不易发现其规律的问题需要仔细分析,探索出其中规律,再予以解决。例10:从1到100的自然数中,每次取出不同的两个数,使他们的和大于100,则不同的取法种数有种。解:此题的数字较多,情况也不一样,需要分析摸索其规律。为方便,两个加数中较小的为被加数,1100101100,1为被加数的有1种;同理,2为被加数的有2种;3为被加数的有3种;……;49为被加数的有49种;50为被加数的有50种;但51为被加数的只有49种;52为被加数的只有48种;……;99为被加数的只有1种,故不同的区法有:(12350)(49481)2500种。(十一)“住店”问题解决“允许重复排列”的问题要注意区分两类元素:一类元素可重复,另一类元素不能重复。把不能重复的元素看着“客”,能重复的元素看着“店”,再利用分步计数原理直接求解的方法称为“住店法”。例11:7名学生争夺五项冠军,获得冠军的可能种数是种。解:应同一学生可同时夺得n项冠军,故学生可重复排列,将7名学生看着7家“店”,五项冠军看着5名“客”,每个客有7种住宿方法,由分步计数原理得5N=7种。(十二)特征分析法有约束条件的排数问题,必须紧扣题中所提供的数字和结构特征,进行推理,分析求解。例12:由1,2,3,4,5,6六个数可组成多少个无重复且是6的倍数的五位数?解:分析数字的特征:6的倍数的数既是2的倍数,又是3的倍数。其中3的倍数又满足“各个数位上的数字之和是3的倍数”的特征。而且12621是3的倍数,从6个数字中取5个,使之和还是3的倍数,则所去掉的数字只能是3或6。因而可以分两类讨论:第一类,所排的五位数不含3,即由1,2,3,4,5,6作数码;首先从2,4,6三个中任选一个作个位数字有13A种,然后其余4个数字在其他数位上的全排列有44A,所以11134NAA;第二类,所排的五位数不含6,即由1,2,3,4,5作数码,依上法有14224NAA,故12N=NN120种。(十三)相同元素进盒,用档板分隔例13:10张参观公园的门票分给5个班,每班至少1张,有几种选法?解:这里只是票数而已,与顺序无关,故可把10张票看成10个相同的小球放入5个不同的盒内,每盒至少1球,可先把10球排成一列,再在其中9个间隔中选4个位置插入4块“档板”分成5格(构成5个盒子)有49C种方法。注:档板分隔模型专门用来解答同种元素的分配问题。(十四)个数不少于盒子编号数,先填满再分隔例14:15个相同的球放入编号为1,2,3的盒子内,盒内球数不少于编号数,有几种不同的放法?解:先用6个球按编号数“填满”各盒(符合起码要求),再把9个球放入3个盒内即可,可用2块档板与9个球一起排列(即为两类元素的排列问题),有211C种。(十五)不同元素进盒,先分堆再排列4对于不同的元素放入几个不同的盒内,当有的盒内有不小于2个元素时,不可分批进入,必须先分堆再排入。例15:5个老师分配到3个班搞活动,每班至少一个,有几种不同的分法?解:先把5位老师分3堆,有两类:3,1,1分布有35C种和1,2,2分布有12254222CCCA种,再排列到3个班里有33A种,故共有122335425322()CCCCAA种。注意:不同的老师不可分批进入同一个班,须一次到位(否则有重复计数)。即“同一盒内的元素必须一次进入”。(十六)两类元素的排列,用组合选位法例16:10级楼梯,要求7步走完,每步可跨一级,也可跨两级,问有几种不同的跨法?解:由题意知,有4步跨单级,3步跨两级,所以只要在7步中任意选3步跨两级即可。故有37C种跨法。注意:两类元素的排列问题涉及面很广,应予重视。例17:沿图中的网格线从顶点A到顶点B,最短的路线有几条?解:每一种最短走法,都要走三段“|”线和四段“—”线,这是两类元素不分顺序的排列问题。故有37C或47C种走法。例18:从5个班中选10人组成校篮球队(无任何要求),有几种选法?解:这个问题与例12有区别,虽仍可看成4块“档板”将10个球分成5格(构成5个盒子),是球与档板两类元素不分顺序的排列问题。但某些盒子中可能没有球,故4块“档板”与10个球一样也要参与排成一列而占位置,故有414C种选法。注意:怎样把问题等价转化为“两类元素的排列”问题是解题的关键。(十七)元素交叉问题集合法所谓集合思想,就是运用集合的概念、逻辑语言、运算、图形等来解决数学问题或非纯数学问题的思想方法。利用集合思想解决排列组合问题,可以使抽象的数学问题具体化,也可以防止在分类或分步的过程中出现重复和遗漏问题。在利用集合思想求解时,要借助于下列一组公式,它们容易用文氏图来验证。1.德·摩根定律:2.容斥原理:若用表示有限集合A中的元素的个数,则对于任意集合A、B,有=。特殊的,。下面举例说明:5例1.从6名运动员中选出4名参加接力赛,如果甲不跑第一棒,乙不跑第四棒,共有多少种不同的参赛方法?解:设全集,根据容斥原理得参赛方法共有:答:共有252种不同的参赛方法。例2.高一(3)班的学生中,参加课外语文小组的有20人,参加数学小组的有22人,既参加语文又参加数学小组的有10人,既未参加语文又未参加数学小组的有15人,问高一(3)班共有多少学生?解:设由容斥原理及德·摩根定律:答:高一(3)班共有学生47人。例3.由数字1、2、3、4、5可以组成多少个无重复数字且2、3都与4不相邻的五位数。解:设则原题即求,由容斥原理及德·摩根定律:6注:表示2与4相邻且3与4相邻的五位数的个数,那么4一定排在2与3之间,且2、3、4相邻,故有种排法。从以上三例可以看出,用集合思想处理排列组合问题,既可使问题正确归类,又可避免重复、遗漏现