排列组合问题的基本类型及解题方法

1、排列组合问题的基本类型及解题方法解决排列组合问题要讲究策略，首先要认真审题，弄清楚是排列（有序 ）还是组合（无序 ） ，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两 个基本原则进行“分类与分步”。加法原理的特征是分类解决问题，分类必须满足两个 条件：类与类必须互斥 （不相容） ，总类必须完备 （不遗漏 ） ；乘法原理的特征是分步 解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。分类与分步是解决 排列组合问题的最基本的思想策略，在实际操作中往往是“步”与“类”交叉，有机结 合，可以是类中有步，也可以是步中有类。以上解题思路分析，可以用顺口溜概括为：审明题意，排

2、（组）分清；合理分类， 用准加乘；周密思考，防漏防重；直接间接，思路可循；元素位置，特殊先行；一题 多解，检验真伪。（一）特殊元素的“优先安排法”对于特殊元素的排列组合问题，一般先考虑特殊元素，再考虑其他元素的安排。在操作时，针对实际问题，有时“元素优先”，有时“位置优先”。例 1： 0,2,3,4,5 这五个数字，组成没有重复数字的三位数，其中偶数共有几个？ 解法一： （元素优先 ）分两类：第一类，含 0 ， 0在个位有 A42种， 0在十位有 A12A13种； 第二类，不含 0 ，有 A12A23 种。 故共有 （A42 A12A13）+A12A32 30种。注： 在考虑每一类时，又要优先

3、考虑个位。解法二： （ 位置优先 ） 分两类：第一类， 0 在个位有 A 24 种；第二类， 0 不在个位，先从两 个偶数中选一个放个位，再选一个放百位，最后考虑十位，有A12A13A13 种。故共有 A24 +A12A13A13=30（二）总体淘汰法对于含有否定词语的问题，还可以从总体中把不符合要求的除去，此时应注意既不能多减也不能少减， 例如在例 1中也可以用此法解答： 5 个数字组成三位数的全排列3为 A 35，排好后发现 0 不能在首位，而且 3和 5不能排在末尾，这两种不合题意的排法 要除去，故有 30 个偶数（三）合理分类与准确分步解含有约束条件的排列组合问题，应按元素的性质进行分

4、类，事情的发生的连续过程分步，做到分类标准明确，分布层次清楚，不重不漏例 2： 5 个人从左到右站成一排，甲不站排头，乙不站第二个位置，不同的站法有 解：由题意，可先安排甲，并按其进行分类讨论：（1）若甲在第二个位置上，则剩下的四人可自由安排，有A44 种方法；（2）若甲在第三个或第四个位置上， 则根据分布计数原理不同的站法有 A13A31A 33种站法； 再根据分类计数原理，不同的站法共有：A 24 A13A13A33 78种（四）相邻问题：捆绑法对于某些元素要求相邻排列的问题， 可先将相邻元素捆绑成整体并看作一个元素再与其它元素进行排列，同时对相邻元素内部进行自排。例 3： 5 个男生 3

5、 个女生排成一列，要求女生排一起，共有几种排法？ 解：先把 3个女生捆绑为一个整体再与其他 5个男生全排列。同时， 3个女生自身也应 全排列。由乘法原理共有 A66A33 种。（五）不相邻问题用“插空法”对于某几个元素不相邻的排列问题， 可先将其他元素排好， 再将不相邻的元素在已排好 的元素之间及两端的空隙之间插入即可（注意有时候两端的空隙的插法是不符合题意的） 例 4： 5 个男生 3 个女生排成一列，要求女生不相邻且不可排两头，共有几种排法？ 解：先排无限制条件的男生， 女生插在 5个男生间的 4个空隙，由乘法原理共有 A55A34 种。 注意： 分清“谁插入谁”的问题。要先排无限制条件的

6、元素，再插入必须间隔的元素； 数清可插的位置数；插入时是以组合形式插入还是以排列形式插入要把握准。例 5：马路上有编号为 1,2,3 ,9的 9盏路灯，现要关掉其中的三盏，但不能同时关掉相邻的两盏或三盏，也不能关两端的路灯，则满足要求的关灯方法有几种？解：由于问题中有 6盏亮 3盏暗，又两端不可暗，故可在 6盏亮的 5个间隙中插入 3个暗 的即可，有 C35 种。（六）顺序固定问题用“除法”或选位不排或先定后插对于某几个元素顺序一定的排列问题，可先把这几个元素与其他元素一起进行排列，然后用总排列数除以这几个元素之间的全排列数。或先在总位置中选出顺序一定元素的位置而不参加排列，然后对其它元素进行

7、排列。也可先放好顺序一定元素，再一一插入其它元素。例 6： 5 人参加百米跑，若无同时到达终点的情况，则甲比乙先到有几种情况？解法一： 先5人全排有 A55种，由于全排中有甲、乙的全排种数A22 ，而这里只有 1种是符合要求的，故要除以定序元素的全排列A22 种，所以有A55A22=60 种。解法二：先在 5个位置中选 2个位置放定序元素 （甲、乙）有 C52种，再排列其它 3人有 A33，由乘法原理得共有 C25A 33=60 种。解法三： 先固定甲、乙，再插入另三个中的第一人有 3种方法，接着插入第二人有 4 种 方法，最后插入第三人有 5种方法。由乘法原理得共有 3 4 5=60 种。七

8、）“小团体”排列，先“团体”后整体对于某些排列问题中的某些元素要求组成“小团体”时，可先按制约条件“组团”并视为一个元素再与其它元素排列。例 7: 四名男歌手与两名女歌手联合举行一场演唱会，演出的出场顺序要求两名女歌手之 间有两名男歌手，则出场方案有几种？解：先从四名男歌手中选 2 人排入两女歌手之间进行“组团”有A24A22种，把这个“女男男女”小团体视为 1人再与其余 2 男进行排列有 A 33种，由乘法原理，共有 A42A22 A33种八）分排问题用“直排法”把 n 个元素排成若干排的问题， 若没其他的特殊要求， 可用统一排成一排的方法来处理例 8： 7 个人坐两排座位，第一排坐 3人，

9、第二排坐 4 人，则有 种排法 解：7 个人，可以在前后两排随意就座， 没有其他的限制条件， 故两排可以看成一排来处理， 所以不同的坐法有 A77 （九）逐步试验法如果题中附加条件增多 ,直接解决困难 ,用试验法寻找规律有时也是行之有效的方法例 9：将数字 1,2,3,4 填入标号为 1,2,3,4 的四个方格内，每个方格填一个，则每个方格的标号与所填的数字均不相同的填法种数有 种。解： 此题考查排列的定义，由于附加条件较多，解法较为复杂，可用试验法逐步解决 第一方格内可填 2或3或4如填 2 ，则第二方格内可填 1或3或 4 若第二方格内填 1, 则第三方格内只能填 4 ，第四方格内填 3

10、若第二方格填 3 ，则第三方格应填 4 ， 第四方格应填 1同理，若第二方格填 4 ，则第三、四方格应分别填 3， 1。因而第一 方格填 2共有 3种方法。同理，第一格填 3或 4也各有 3种，所以一共有 9种方法。（十）探索规律法对于情况复杂，不易发现其规律的问题需要仔细分析，探索出其中规律，再予以解决。例 10 ：从 1 到 100 的自然数中，每次取出不同的两个数，使他们的和大于100 ，则不同的取法种数有 种。解：此题的数字较多，情况也不一样，需要分析摸索其规律。为方便，两个加数中较小的为 被加数， 1 100 101 100 ， 1为被加数的有 1种；同理， 2为被加数的有 2种；

11、3为被加 数的有 3种； 49为被加数的有 49种； 50为被加数的有 50种；但 51为被加数的只 有 49种； 52为被加数的只有 48 种； 99为被加数的只有 1种，故不同的区法有： （1 2 3 50） （49 48 1） 2500 种。（十一）“住店”问题解决“允许重复排列”的问题要注意区分两类元素：一类元素可重复，另一类元素不能重 复。把不能重复的元素看着“客”，能重复的元素看着“店”，再利用分步计数原理直接求解的方 法称为“住店法”。例 11： 7 名学生争夺五项冠军，获得冠军的可能种数是种。解： 应同一学生可同时夺得 n 项冠军，故学生可重复排列，将7名学生看着 7家“店”，

12、五项冠军看着 5名“客”，每个客有 7 种住宿方法，由分步计数原理得N=7 5种。（十二）特征分析法有约束条件的排数问题， 必须紧扣题中所提供的数字和结构特征， 进行推理， 分析求解。 例 12：由 1,2,3,4,5,6 六个数可组成多少个无重复且是6 的倍数的五位数？解：分析数字的特征： 6的倍数的数既是 2的倍数，又是3的倍数。其中 3的倍数又满足“各 个数位上的数字之和是 3的倍数”的特征。而且 1 2 6 21是 3的倍数，从 6个数字 中取 5个，使之和还是 3的倍数，则所去掉的数字只能是 3或 6 。因而可以分两类讨论：第 一类，所排的五位数不含 3 ，即由 1,2,3,4,5,

13、6 作数码；首先从 2,4,6 三个中任选一个作个 位数字有 A13种，然后其余 4个数字在其他数位上的全排列有 A44 ，所以 N1 A13A14；第二 类，所排的五位数不含 6，即由1, 2,3,4作,5数码，依上法有 N2 A12A44 ，故 N=N1 N 2 120种。（十三）相同元素进盒，用档板分隔例 13： 10张参观公园的门票分给 5 个班，每班至少 1张，有几种选法？ 解：这里只是票数而已， 与顺序无关， 故可把 10 张票看成 10 个相同的小球放入 5个不同 的盒内， 每盒至少 1球，可先把 10球排成一列， 再在其中 9个间隔中选 4个位置插入 4 块 “档板”分成 5格

14、（构成 5个盒子 ）有C94种方法。注： 档板分隔模型专门用来解答同种元素的分配问题。（十四）个数不少于盒子编号数，先填满再分隔例 14： 15 个相同的球放入编号为 1,2,3 的盒子内，盒内球数不少于编号数，有几种 不同的放法？解：先用 6个球按编号数“填满”各盒 （符合起码要求 ）, 再把 9个球放入 3个盒内即可 , 可用 2块档板与 9个球一起排列 （ 即为两类元素的排列问题 ）, 有C121种。十五）不同元素进盒，先分堆再排列对于不同的元素放入几个不同的盒内，当有的盒内有不小于2 个元素时，不可分解： 先把 5 位老师分 3堆，有两类：3,1,1分布有 C53种和 1,2, 2分布

15、有C51C42C22A22种，再排列到 3 个班里有 A33种，故共有 （C53C51C42C22A22) A33种。批进入，必须先分堆再排入。例 15 ：5个老师分配到 3 个班搞活动，每班至少一个，有几种不同的分法？注意： 不同的老师不可分批进入同一个班，须一次到位（否则有重复计数 ）。即“同一盒内的元素必须一次进入”。（十六）两类元素的排列，用组合选位法例16： 10级楼梯，要求7步走完，每步可跨一级， 也可跨两级， 问有几种不同的跨法？ 解：由题意知，有 4步跨单级， 3步跨两级，所以只要在 7 步中任意选 3步跨两级即 可。故有 C73 种跨法。注意： 两类元素的排列问题涉及面很广，

16、应予重视。例 17 ： 沿图中的网格线从顶点 A 到顶点 B ，最短的路线有几条？ 解： 每一种最短走法，都要走三段“ | ”线和四段“”线， 这是两类元素不分顺序的排列问题。故有C73 或 C74 种走法。例 18： 从 5个班中选 10人组成校篮球队 （ 无任何要求 ） ，有几种选法？解：这个问题与例 12有区别，虽仍可看成 4块“档板”将 10个球分成 5格（构成 5个盒 子） ，是球与档板两类元素不分顺序的排列问题。但某些盒子中可能没有球， 故4 块“档板”与 10 个球一样也要参与排成一列而占位置，故有C144 种选法。注意： 怎样把问题等价转化为“两类元素的排列”问题是解题的关键。

17、以下选看十七）元素交叉问题 集合法所谓集合思想，就是运用集合的概念、逻辑语言、运算、图形等来解决数学 问题或非纯数学问题的思想方法。 利用集合思想解决排列组合问题， 可以使抽象 的数学问题具体化， 也可以防止在分类或分步的过程中出现重复和遗漏问题。 在 利用集合思想求解时，要借助于下列一组公式，它们容易用文氏图来验证。1. 德·摩根定律：2. 容斥原理：若用表示有限集合 A 中的元素的个数，则对于任意集合 A、B，有= 。特殊的， 。下面举例说明：例 1. 从 6 名运动员中选出 4 名参加 接力赛，如果甲不跑第一棒，乙不 跑第四棒，共有多少种不同的参赛方法？解：设全集，根据容斥原理得参赛方法共有：答：共有 252 种不同的参赛方法。例 2. 高一（ 3）班的学生中，参加课外语文小组的有 20 人，参加数学小组的有 22人，既参加语文又参加数学小组的有 10 人，既未参加语文又未参加数学小组 的有 15 人，问高一（ 3）班共有多少学生？解：设由容斥原理及德·摩根定律：答：高一（ 3）班共有学生 47 人。例 3. 由