解排列组合题的若干技巧

王承超　向清耀

排列组合问题的解题方法既有一般的规律，又有很多特别的技巧. 它要求我们认真地审题，对题目中的信息进行科学地加工处理，下面通过一些例题来说明几种常见的解法.

运用两个基本原理

加法原理和乘法原理是解排列组合应用题最基本的出发点，可以说对每道应用题我们都要考虑在计数的时候进行分类或分步处理.

例1 如右图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同着色方法共有 种.（以数字作答）.

分析 本题只要用两个基本原理即可解决.

解 根据题意，可分类求解：第一类，用三种颜色着色，由乘法原理[C14C41C12=24]种方法；第二类，用四种颜色着色，由乘法原理有[2C14C41C12C11=48]种方法. 再由加法原理得，24+48=72种方法.

答案 72

特殊元素（位置）优先

特殊元素优先考虑，特殊位置优先考虑.

例2 从[a，b，c，d，e]这5个元素中，取出4个放在四个不同的格子中，且元素[b]不能放在第二个格子中，问共有多少种不同的放法？

分析 若从特殊元素考虑可以先排[b]，若从特殊位置考虑先排第二格.

解 法一：（元素分析法，[b]为特殊元素）先排[b]，但考虑到取出的4个元素可以有[b]，也可以没有[b]，所以分两类. 第一类，取出的4个元素中有[b]，则排[b]有[A13]种方法；再从[a，c，d，e]中取出3个排另外三个格子有[A34]种，所以此类共有[A13?A34]种. 第二类，取出的4个元素中没有[b]，则有[A44]种方法. 所以共有[A13?A34+A44=96]种放法.

法二：（位置分析法，第二格为特殊位置）先排第二格，有[A14]种（从[a，c，d，e]中取一个）；再排另外三格有[A34]种，所以共有[A14?A34=96]种放法.

捆绑法

对于相同类别不可分开的，要先进行捆绑.

例3 计划在一画廊展出10幅不同的画，其中1幅水彩画，4幅油画，5幅国画，排成一行陈列. 要求同一品种的画必须排一起，并且水彩画不放在两端，那么不同的陈列方式有（ ）

A. [A44?A55] B. [A33?A44?A55]

C. [C13?A44?A55] D. [A22?A44?A55]

分析 先捆绑，然后再看其他限制条件.

解 油画整体、国画整体、水彩画按“元素”先排，考虑到水彩画不能排两端，所以有[A22]种方法. 又4幅油画的不同陈列方式有[A44]种，5幅国画陈列方式有[A55]种. 因而，画展的不同陈列方式有[A22?A44?A55]种.

答案 D

插空法

解决某几个元素要求不相邻的问题时，先将其他元素排好，再将指定的不相邻的元素插入已排好元素的间隙和两端位置，从而将问题解决.

例4 道路边上有编号为1，2，3，4，5，6，7，8，9，10的10盏路灯，现要关掉其中的3盏，但不能关掉相邻的2盏或3盏，也不能关两端的路灯，则满足要求的关灯方法有几种？

分析 在[n]个元素间的[n-1]个空中插入若干个板，共有[Cbn-1]种方法.

解 由于问题中有7盏亮3盏暗，又两端不能暗，问题等价于：在7盏开着的路灯的6个间隔中，选出3个间隔各插入3只关掉的路灯，所以关灯的方法共有[C36=20]种.

排除法

在直接法考虑比较难或分类不清或多种时，可考虑用排除法.

例5 从正方体的6个面中选取3个面，其中有2个面不相邻的选法共有（ ）

A. 8种 B. 12种 C. 16种 D. 20种

分析 解决几何问题必须注意几何图形本身对其构成元素的限制.

解 六个面中任取三个共有[C36=20]种，排除掉3个面都相邻的种数，即8个角上3个平面相邻的特殊情形共8种，故符合条件的共有[C36-8=12]种.

答案 B

多元分类法

对于元素多、选取情况多的，可按要求进行分类讨论，最后总计.

例6 有甲、乙、丙三项任务，甲需2人承担，乙、丙各需1人承担，从10人中选派4人承担这三项任务，不同的选法共有（ ）

A. 1260种 B. 2025种

C. 2520种 D. 5040种

分析 先依次选出甲、乙、丙承担的人数，再根据根据乘法原理计算总人数.

解 先从10人中选出2人承担甲项任务，有[C210]种选法，再从余下的8人中选1人承担乙项任务，有8种；最后从7人中选1人承担丙项任务，有7种. 所以根据乘法原理知共有[C210×8×7=2520]种.

答案 C

先取后排法

从几类元素中取出符合题意的几个元素，再安排到一定位置上，可用先取后排法.

例7 有5个男生和3个女生，从中选5个担任5门学科代表，求符合下列条件的选法数. （1）有女生但人数少于男生. （2）某女生一定要担任语文科代表. （3）某男生必须在内，但不担任数学科代表. （4）某女生一定要担任语文科代表，某男生必须担任科代表，但不是数学科代表.

分析 比较复杂的排列组合混合问题，一般要遵循先取后排的原则.

解 （1）可分为1女4男和2女3男，共计不同的选法种数为[C13?C45+C23?C35=45]，任科代表种数为[（C13?C45][+C23?C35）A55]=5400.

（2）某女生一定要担任语文科代表，余4门科代表从余下的7人中任选有[A47=840]种.

（3）某男生从除数学外四科中任选一科代表有[C14]，余4科从余下的7人中任选有[A47，]共有不同种数为[C14?A47=3360].

（4）某女生任语文科代表，某男生从余下3种（数学除外）中任选一科有[C13]种，余3科代表由余下6人中选任，共计不同安排总数为[C13?A36=360]种.

隔板法

排列组合中对于不可分辨的球装入到可以分辨的盒子中而求装入的方法数的问题，通常用隔板法.

例8 将20个相同的球分放在三个盒中，不允许有盒不放球，有多少种分法？

分析 由两个隔板将20个球分成三个部分.

解 将20个球排成一排，一共有19个空隙，将两个隔板插入这些空隙中，规定由隔板分成的左、中、右三部分球分别放在三个盒中，则每一种隔法对应了一种分法，于是分法的总数为[C219=171]种方法.

转化法

将陌生、复杂的问题转化为熟悉、简单的问题也是解决排列组合较难问题的重要策略.

例9 将组成篮球队的12个名额分给7所学校，每校至少1个名额，问名额分配的方法共有多少种？

分析 名额分配问题通常转化为平时熟悉的隔板法.

解 问题等价于将排成一行的12个相同元素分成7份的方法数，相当于用6块隔板插在11个间隔中，共有[C611=462]种不同的方法.

例10 10级楼梯，要求7步跨完，且每步最多跨2级，问有几种不同跨法？

分析 问题转化为先捆后排.

解 由题意知要有4步单级、3步双级，因此，这是两类不同元素的排列，问题等价于只要在7步中任意选3步双级即可. 故[C37=35]种.