解决复杂排列组合问题的五种方法

■深圳技术大学附属中学 邱崇洋

对于复杂的排列组合问题,必须讲究解题方法。常言道:兵来将挡,水来土掩。那么,破解复杂的排列组合问题有哪些方法呢?

一、构造模型法

例1马路上有编号为1,2,3…,9这9盏路灯,现要关掉其中的3盏,但不能关掉相邻的2盏或3盏,也不能关掉两端的2盏,则满足条件的关灯方案有多少种?

解析:把此问题当作一个排队模型,在6盏亮灯的5个空隙中插入3盏不亮的灯,有种方法,所以满足条件的关灯方案有10种。

点评:一些不易理解的排列组合题,如果能转化为熟悉的模型(如占位填空模型、排队模型、装盒模型等),可使问题容易解决。

二、分解与合成法

例2(1)30 030能被多少个不同偶数整除?

(2)正方体8 个顶点可连成多少对异面直线?

解析:(1)先把30 030 分解成质因数的形式:30 030=2×3×5×7×11×13。

依题意知偶因数2必取,再从3,5,7,11,13这5个因数中任取若干个相乘。

由此可见，会计内容在与时俱进，变革速度很快，有可能给学生讲授的财务会计内容，还没等学生毕业，所学内容可能就已经改变了，比如现在的经融工具和收入的修改等。

(2)因为四面体中仅有3对异面直线,所以可将问题分解成正方体的8个顶点可构成多少个不同的四面体。

所以8个顶点可连成的异面直线有3×58=174(对)。

点评:分解与合成策略是排列组合问题的一种最基本的解题策略。把一个复杂问题分解成几个小问题逐一解决,然后依据问题分解后的结构,用分类计数原理和分步计数原理将问题合成,从而得到问题的答案,每个比较复杂的问题都要用到这种解题策略。

三、间接法

例38张卡片分别标数字1,2,3,4,5,6,7,8,从中取出6张卡片排成3行2 列,要求3行中仅有中间行的两张卡片上的数字之和为5,则不同的排法共有( )。

A.1 344种 B.1 248种

C.1 056种 D.960种

解析:中间行数字之和为5 只有两种情况,即1,4和2,3。但这两组不能同时占据两行,以1,4占中间行为例,则在安排时既要考虑另一组2,3是否同时被选中,还要考虑同时被选中时不能呆在同一行,情况比较复杂。所以考虑间接法,先求出中间数之和为5 的所有情况,再减去两行和为5的情形。

先考虑中间和为5的所有情况:

再考虑两行和为5的情况:

从而仅有中间行为5的情况有1 440-192=1 248(种),选B。

点评:对于复杂的排列组合问题,当从正面入手解决比较困难时,应转变思维角度,从反面考虑,这种方法体现了“正难则反”的解题思路。

四、转化法

例4(1)平面上给定10个点,任意三点不共线,将10个点中的任意两个点连成线段,求这些线段的交点个数(假设这些交点都不重合)。

(2)某火车站共设有4个安检入口,每个入口每次只能进入1位乘客,求一个4 人小组进站的不同方案种数。

解析:(1)本题如果采用直接法,觉得无从下手,但注意到一个平面四边形的对角线只有一个交点,那原问题可转化为平面上10个无三点共线的点可以构成多少个四边形。所以这些线段的交点个数为=210。

(2)设4 名乘客中分别有z1,z2,z3,z4个人在第1个、第2个、第3 个、第4 个安检口通过,则z1+z2+z3+z4=4,即问题转化为求方程z1+z2+z3+z4=4的非负整数解的组数,共有种情况,每一种进站情况的4个位置由4个人去站,有种方法。

所以一个4人小组进站的不同方案数为840。

点评:处理复杂的排列组合问题时可以把这个问题转化成一个简单的问题,通过解决这个简单的问题从而解决原来的问题。

五、定序问题——除法倍缩法

例5甲、乙、丙、丁、戊这5 个人排成一排照相,且甲、乙不在丙的同侧,则不同的排法共有( )种。

A.48 B.40 C.60 D.64

解析:先对5人进行全排列,则不同的排法有种。由于甲、乙、丙的不同顺序共有种,而甲、乙不在丙的同侧的相对顺序有甲→丙→乙和乙→丙→甲这两种情况,占了总数的,故不同的排法共有(种)。选B。

点评:当n个人排成一列并且其中m人位置固定时,一般可先将n个人全排列,再除以m个人全排列总数,即,这就是所谓的“除法倍缩”策略。