解决排列组合问题的常用技巧与策略-南昌一中

解决排列组合问题的常用技巧与策略•解决排列组合问题要讲究策略，首先要认真审题，弄清楚是排列(有序)还是组合(无序)，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两个基本原则进行“分类与分步”。•加法原理的特征是分类解决问题，分类必须满足两个条件：①类与类必须互斥(不相容)，②总类必须完备(不遗漏)；乘法原理的特征是分步解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。•分类与分步是解决排列组合问题的最基本的思想策略，在实际操作中往往是“步”与“类”交叉，有机结合，可以是类中有步，也可以是步中有类。•以上解题思路分析，可以用顺口溜概括为：审明题意，排（组）分清；合理分类，用准加乘；周密思考，防漏防重；直接间接，思路可循；元素位置，特殊先行；一题多解，检验真伪。（一）.特殊元素的“优先安排法”•对于特殊元素的排列组合问题，一般先考虑特殊元素，再考虑其他元素的安排。在操作时，针对实际问题，有时“元素优先”，有时“位置优先”。•例1：0、2、3、4、5这五个数字，组成没有重复数字的三位数，其中偶数共有几个？•解法一：(元素优先)分两类：第一类，含0，0在个位有种，0在十位有•种；•第二类，不含0，有种。故共有•＝３０种。•注：在考虑每一类时，又要优先考虑个位。24A1123AA1223AA（24A＋1123AA）＋1223AA（二）．总体淘汰法•对于含有否定词语的问题，还可以从总体中把不符合要求的除去，此时应注意既不能多减也不能少减，•例２：５个人从左到右站成一排，甲不站排头，乙不站第二个位置，•不同的站法有解：由题意，可先安排甲，并按其进行分类讨论：（1）若甲在第二个位置上，则剩下的私四人可自由安排，有44A种方法；（2）若甲在第三个或第四个位置上，则根据分布计数原理不同的站法有113333AAA种站法；再根据分类计数原理，不同的站法共有：44A＋113333AAA＝７８种．•（三）.相邻问题：捆绑法•对于某些元素要求相邻排列的问题，可先将相邻元素捆绑成整体并看作一个元素再与其它元素进行排列，同时对相邻元素内部进行自排。•例3：5个男生3个女生排成一列，•要求女生排一起，共有几种排法？解：先把3个女生捆绑为一个整体再与其他5个男生全排列。同时，3个女生自身也应全排列。由乘法原理共有6365AA种。（四）不相邻问题用“插空法”•对于某几个元素不相邻的排列问题，可先将其他元素排好，再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可（注意有时候两端的空隙的插法是不符合题意的）.•例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种，所以有55A/22A=60种。解法二：先在5个位置中选2个位置放定序元素(甲、乙)有25C种，再排列其它3人有33A，由乘法原理得共有25C33A=60种。•解法三：先固定甲、乙，再插入另三个中的第一人有3种方法，接着插入第二人有4种方法，最后插入第三人有5种方法。由乘法原理得共有种。=60（六）分排问题用“直排法”•把n个元素排成若干排的问题，若没其他的特殊要求，可用统一排成一排的方法来处理．•例7：8个人坐两排座位，每排四人，限定甲必须坐前排，乙、丙必须坐在同一排，则有种排法．•解：乙、丙可以同在前后两排就座，两排可以看成一排来处理，第一类，甲在前排，乙、丙在前排，有，第二类，甲在前排，乙、丙在后排，有•所以不同的坐法有AAA551224AAA551424AAA551224AAA551424+=8640（七）“住店”问题•解决“允许重复排列”的问题要注意区分两类元素：一类元素可重复，另一类元素不能重复。把不能重复的元素看着“客”，能重复的元素看着“店”，再利用分步计数原理直接求解的方法称为“住店法”。•例8：７名学生争夺五项冠军，获得冠军的可能种数是种。解：应同一学生可同时夺得n项冠军，故学生可重复排列，将７名学生看着７家“店”，五项冠军看着５名“客”，每个客有７种住宿方法，由分步计数原理得Ｎ＝57种。（八）相同元素进盒，用档板分隔•例9：10张参观公园的门票分给5个班，每班至少1张，有几种选法？•解：这里只是票数而已，与顺序无关，故可把10张票看成10个相同的小球放入5个不同的盒内，每盒至少1球，可先把10球排成一列，再在其中9个间隔中选4个位置插入4块“档板”分成5格(构成5个盒子)有•种方法。•注：档板分隔模型专门用来解答同种元素的分配问题。•例10：从5个班中选10人组成校篮球队(无任何要求)，有几种选法？•解：这个问题与例12有区别，虽仍可看成4块“档板”将10个球分成5格(构成5个盒子)，是球与档板两类元素不分顺序的排列问题。但某些盒子中可能没有球，故4块“档板”与10个球一样也要参与排成一列而占位置，故有种选法。（九）不同元素进盒，先分堆再排列•对于不同的元素放入几个不同的盒内，当有的盒内有不小于2个元素时，不可分批进入，必须先分堆再排入。•例11：5个老师分配到3个班搞活动，每班至少一个，有几种不同的分法？解：先把5位老师分3堆，有两类：3、1、1分布有种和1、2、2分布有种，再排列到3个班里有种，故共有。•易错题•编号为1、2、3、4的四个小球分给3个小朋友，每人至少一个，有多少种分法？•以上介绍了排列组合应用题的几种常见求解策略，这些策略不是彼此孤立的,而是相互依存的，相互为用的。有时解决某一问题时要综合运用几种求解策略。