排列、组合问题奇思妙解

傅雪慧

中学数学中的排列组合是一类思考方式较为独特的问题。它对分析能力要求较高，解法也非常灵活，是高考的难点之一。因此，恰当地选择思考方法，对于解决排列组合问题至关重要。分类计数，分步计数两个原理是解决排列、组合问题的基本方法，利用该两个原理及课堂中学习的常规解法如：特殊元素、特殊位置、插空法、捆绑法等解决某些问题总感觉较难或者解答较繁。针对该现象，本文列举几例介绍解排列组合问题的非常规解题思路。

一、列举法

把符合条件的安排不重复、不遗漏的一一列举出来，是最简单、最原始但也是最基本的计数方法。教材中多次应用到，高考中也常用枚举法解决问题。

例1，某电脑用户计划使用不超过500元的资金购买单价分别为60元、70元的单片软件和盒装磁盘，根据需要，软件至少买3片，磁盘至少买2盒，则不同的选购方法有（ ）。

A、5种 B、6种 C、7种 D、8种

解析：根据所给选项数字较小，不难用枚举法解决。

单片买3张，磁盘买2盒，花费320元；单片买3张，磁盘买3盒，花费390元；单片买3张，磁盘买4盒，花费460元；单片买4张，磁盘买2盒，花费380元；单片买4张，磁盘买3盒，花费450元；单片买5张，磁盘买2盒，花费440元；单片买6张，磁盘买2盒，花费500元。故选购方式有7种，选A。

例2，从1到100的一百个自然数中，每次取出兩个数，使其和大于100，这样的取法共有多少种？

解：从1到100的一百个自然数中，每次取出两个数，其中必有一个是较小的。我们先按较小的一数枚举，而当较小的数取定以后，使和超过100的另一个相应较大的数不难一一例举，所有情况如下表：

所以共有：1+2+3+…+49+50+49+…+1=2500种不同的取法。

利用枚举法解题，直观性强，是处理排列组合问题的好方法。

二、“正难则反”

解决问题，当正面难以解决时，不妨从反面、侧面思考，顺繁则逆、正难则反。

例3，有五张卡片，他们的正反面分别写有0与1，2与3，4与5，6与7，8与9，將其中任意三张排放在一起组成三位数，共可组成多少个不同的三位数？

解析：①0不能做百位，但可以作十位或个位。②0与1在同张卡片上，因此直接分类既要考虑0又要考虑1分类较复杂。于是先不考虑任何情况算出总数，然后减去0在左边第一位的号码即为所求。由于任取三张可以组成不同的三个数的号码有：C³₅·2³·A³₃，其中0在左边第一位的号码有：c；-2。-Ai，故所求的不同三位数共有：C³₅·2³·A³₃-C²₄·2²·A²₂=432个。

例4，从1，2，3，……，1995，这1995个自然数中，取出9个互不相邻的自然数，有多少种方法？

解析：由于符合题意的条件错综复杂，正面进攻思维受阻，此时采用反面去考虑问题。

问题相当于“9个女生不相邻地插入站成一列横队的1986个男生之间（包括首尾外侧），有多少种方法？”

任意相邻2个男生之间最多站1个女生，队伍中的男学生首尾两侧最多也可各站1个女学生，于是，这就是1987个位置中任选9个位置的组合问题，共有C⁹₁₉₈₇种方法。

三、利用映射关系解题

就是运用集合的概念、逻辑语言、运算、图形来解决数学问题或非纯数学问题的思想方法。

例5，圆上有10个点，每两点连成一条线段，这些线段在圆内最多有多少个交点？以这些交点为顶点的三角形最多有多少个？

解析：该题如果用枚举法显然很困难；同样用基本极数原理先算出弦的总数，然后算出交点，在减去圆外和圆上的交点个数亦很困难，利用映射关系，化难为易。

一个交点s是由两条线段p，q相交而得，反之，依题意，两条在圆内相交的线段p，q确定一个交点s，即s与（p，q）可建立一一对应关系，两条线段p，q分别是由圆上的两对点A，B与C，D连接而成。故又可在（p，q）与（A，B，C，D）之间建立一一对应关系。因此，若令M={S|题中线段的交点}，N={（A，B，C，D}110个点中，任意四个不同的点组}，则M与N中的元素构成一一对应关系，从而有|M|=|N|但N中元素个数显然为C⁴₁₀=210，所以题中交点为210个。同样的考虑，圆内一个三角形与圆上6个点之间构成一一对应关系，因此，题中所求三角形的个数为C⁶₁₀=210个。

四、利用递推关系解题

例6，有一楼梯共10级，每步只能跨上1级或2级，问要登上最后一级共有多少种走法？

解析：因为每步只能跨上1级或2级，所以最后一步可能从第9级也可能从第8级跨上第10级，向前递推关系不变。设登上第k级有a_k种走法，显然a₁=1，a₂=2，当k>2时，登上第k级台阶的走法可以分两种情况得到：从第k-1级台阶跨一级登上第k级，或从第k-2级台阶，一步跨两级登上第k级。故当k≥3时，有a_k=a_k-1+2_k-2。

∴a₁₀=a₉+a₈=2a₈+a₇=……=34a₂+21a₁=89

例7，把圆分成10个不相等的扇形，并且用红、黄、蓝三种颜色给扇形染色，但不允许相邻的扇形有相同的颜色，问共有多少种染色法？

解析：前9个扇形依次染色并不难，但第10个扇形既与第九个相邻也与第1个相邻，这两个扇形颜色可能相同也可能不相同，所以直接用记数原理有困难，但建立递推关系并不难。

设将圆分成n个不相等的扇形时，满足题设的染法有a_n种。依次记n个扇形为s₁，……s_n。显然a₁=3，当n=2时，先对s₁染色，有3种方法；s₁染色后再对s₂染色，有2种方法，故a₂=6，当n≥3时，我们依次对s₁，s₂，……s_n染色。对s₁染色，有3种方法，对s₁染色后再对s₂染色有2种方法，同样的对s₃，s₄……，s_n分别有2种方法，由乘法原理共有3·2^n-1种染色方法。但这样做s_n与s₁有可能同色。即在3·2^n-种染色方法中包含了s_n与s₁同色的染色方法。对于s_n与s₁同色的情形，拆去s_n与s₁的边界使s_n与s₁合并，便得到将圆分为n-1个扇形时，同色不相邻的染色方法，这样的情况有a_n-1种。故a_n=3·2^n-1-a_n-1（n≥3）。所以a₁₀=3·2⁹-a₉=3·2⁹-3·2⁸+a₈=3·2⁹-3·2⁸+3·2⁷-a₇=……=3.2⁹-3.2⁸+3.2⁷-3.2⁶+3.2⁵-3·2⁴+3·2³-3·2²+3.2¹=2¹⁰+2=1026。

五、利用对称性解题

对称是美的一种形式，对称思想在数学中有广泛的应用，挖掘数学问题中隐含的对称性，运用对称思想解题，往往得到出人意料的简捷解法。

例8，A，B，C，D，E五人站成一排，若B必须站在A的右边（A，B可以不相邻）的不同站法有（ ）。

A、24種 B、60种 C、90种 D、120种

解：∵B站在A的右边与B站在A的左边一样多，由对称分析得1/2A⁵₅=60種，选B。

应用对称性简捷明快，给人以美的享受。

六、利用不等式（方程）组解题

在解决某些数学问题时，先设定一些未知数。然后把它们当作已知数，根据题设本身各量间的制约，列出等式，解方程即可。

例9，一个口袋内有4个不同的红球，6个不同的白球，若取一个红球记2分，取一个白球记1分，从中任取5个球，使总分不少于7分的取法有多少种？

例10，将10个完全相同的小球放人编号为1，2，3的三个盒子内，要求放入盒子的球数不小于它的编号数，则不同的放法有（ ）。

A、20种 B、15种 C、14种 D、12种

解：设编号为1，2，3的三个盒子中分别放入x，y，z个小球，于是题中不同的放法即为方程：x+y+z=10，且x≥1，y≥2，z≥3的非负整数解的个数。令u=x-1，v=y-2，w=z-3，得u+v+w=4，所以该方程的非负整数解的个数即为所求的放法数目C⁴₄₊₃₊₁=15，故选B。

七、等价转换、构造模型解题

例11，马路上有编号为1，2，3，4，5，6，7，8，9的九只路灯，现要关掉其中的3盏，但不能关掉相邻的2盏或3盏，也不能关掉两端的2盏，求满足条件的关灯方法有多少种？

解：把此问题当作一个排队模型：在6盏亮灯的5个空隙中插入3盏熄灯有C³₅种。

例12，某排共有10个座位，若4人就坐，每人左右两边都有空位，那么不同的坐法有多少种？

解：等价于4人插5空模型：A⁴₅。

一些不易理解的排列组合题，如果能转化为非常熟悉的模型，如占位填空模型、排队模型、装盒模型等，可使问题直观解决！

八、多排问题改为直排解题

一般地，元素分成多排的排列问题，可归结为一排考虑，再分段研究。

例13，8人排成前后两排，每排4人，其中甲乙在前排，丁在后排，共有多少排法？

解：8人排前后两排，相当于8人坐8把椅子，可以把椅子排成一排。先在前4个位置排甲乙两个特殊元素有A²₄种，再排后4个位置上的特殊元素有A¹₄种，其余的5人在5个位置上任意排列有A⁵_5q种，则共有A²₄A¹₄A⁵₃种。

学习数学的过程是知识建构的过程，是思维训练的过程。本文列举了几种特殊的解题方法，归纳规律，构造数学模型，掌握分类的数学思想和化归的方法。