例谈几类常见的排列组合问题的解法

王慧娟

排列组合问题和实际生活息息相关，主要考查事件中可能出现的情况数.解答排列组合问题，要灵活运用分类、分步计数原理.排列组合问题的命题形式有很多种，如求数字排列顺序的种数、求排队顺序的种数、求线路的条数、求染色的可能情况数等.本文重点阐述下面三类排列组合问题的解法.

一、路线问题

路线问题是一类综合性较强的排列组合问题，一般要求最短路线的组合方案数.解答这类排列组合问题，需首先明确从起点到终点要分多少步走，然后找出几种可能的路线，根据分步计数原理分别求出每条线路中可能出现的情况数，最后运用分类计数原理求得结果.

例1.某人设计一项单人游戏，规则如下：先将一枚棋子放在如图1所示正方形ABCD（边长为3个单位）的顶点A处，然后通过掷骰子的点数来确定棋子沿正方形的边按逆时针方向行走的单位长度，如果掷出的点数为i（ i=1，2，-6），则棋子就按逆时针方向行走i个单位，如此一直循环下去.则某人抛掷3次骰子后棋子恰好又回到点4处的不同走法共有（ ）种.

A.21种

B.24种

C.25种

D.27种

解：根据题意可知，长方形ABCD（边长为3个单位）的周长为12个单位，当投掷3个骰子之后，棋子恰好又回到点A处，表示掷3次骰子的点数之和为12，有1，5，6;2，4，6;3，4，5;3，3，6;5，5，2;4，4，4共6种组合.前3个组合可列出A3 =6条线路.中间2种组合可列出6条线路，最后一种组合可列出一条线路.根据分类计数原理，可得一共有12+6+6+1=25种不同的走法，所以本题选C.

在解答线路问题时，我们需做到不重不漏，根据题目要求对每一种情况进行讨论，分析每一条线路，可采用列举法、树状图法等求得总线路的条数.

例2.如图2，从A点出发每次只能向上或者向右走一步，则到达B点的路径的条数为____.

解：如图3所示，从点A到C，D，E，F，G的路线都有1条;从点A到点H的路线有2条，即A→C→H，A→F→H：从点A到点D的路线有3条，即从A经过H到点O的2条以及A→F→G→O;从点A到点M的路线有3条，即从点A经过点H到点M的2条和A→C→D→M;从点A到点P的路线有6条，分别是从点A经过点O到点P的3条和从点4经过点M到点P的3条;从点A到点N的路线有4条，分别是从点A经过点M到点Ⅳ的3条和从点4经过点E到点N的1条;从点A到点Q的路线有10条，就分别是从点4经过点P到点Q的6条，和从点4经过点Ⅳ到点Q的4条;从点A到点R的路线有6条，即从点A经过点P到点R的6条;所以从点A到点B的路线有16条，即分别从点A经过点R到点B的6条，和从点A经过点Q到点B的10条;所以到B点的路线的总条数是16条.故答案为16.

本题中的路线较多，需分类进行讨论.可见，分类讨论思想是解答排列组合问题中的线路问题的重要思想方法.

例3.如图4，甲从A到B，乙从C到D，2人每次都只能向上或者向右走一格，如果2个人的线路不相交，则称这2个人的路径为一对孤立路，那么不同的孤立路一共有____对.（用数字作答）.

解：甲从A到B，需要向右走4步，向上走4步，共需8步，所以甲从A到B共有c;种走法.乙从C到D，需要向右走4步，向上走4步，共需8步，所以乙从c到D有c：种走法，根据分步乘法计数原理可知，共C;.c;种不同的路径.甲从A到D，需要向右走6步，向上走4步，共需10步，所以从A到D共有有C/O种走法.乙从c到B，需要向右走2步，向上走4步，共需6步，所以从c到B共有Ci种走法，所.

解答线路问题，需要明确线路的方向和行走的步骤，合理运用分步计数原理和分类计数原理来分析每条路线中可能出现的情况.

二、染色问题

染色问题是指将几个不同的区域染上不同颜色的问题.解答染色问题应从颜色的种类以及问题的特殊要求两方面进行考虑.首先应考虑选取的颜色种数，然后根据题目的要求將不同的区域分情况进行填色，最后根据分类计数原理得到染色方案的总数.

例4.将四棱锥S-ABCD的每一个顶点染上一种颜色，并使同一条棱上的两端异色，如果有恰有5种颜色可供使用，则不同的染色方法有（ ）.

A.480种

B.360种

C.420种

D.320种

解：（1）如果只用3种颜色染色，需先从5种颜色中选取一种将顶点M染色，然后从剩下的4种颜色中选出2种涂在A、B、C和D.且需使4和C、B和D同色，所以一共有C1A4 =60种染色方法.

（2）如果用4色颜色染色，可先从这5种颜色中任选一种将顶点M染色，然后从剩余的4色颜色中任选2种颜色将A和B染色，因为4、B的颜色可互换，所以有A2种染色方法;接着从余下的2种颜色中任选一种将D或C染色，最后用剩下的一种颜色将其他2个顶点染色，故有CIA4C1CI =240种染色方法.

（3）如果用5类颜色染色，则有A 5 =120种染色方法.

所以一共有60+240+120=420种染色方法.

本题主要考查了排列组合中的两个基本原理，需先分类，再分步进行讨论.解答涂色问题可从两个角度人手：（1）颜色的种类;（2）需涂色的区域.

例5.如图5所示，用4种不同的颜色涂人图中的矩形A，B，C，D中，要求相邻的矩形涂不同的颜色，则有____种不同的涂法.

解：按要求涂色至少需要3种颜色，故分2类进行讨论：

一是4种颜色都用，这时A有4种涂法，B有3种涂法，C有2种涂法，D有1种涂法，共有4x3x2x1=24种涂法;

二是用3种颜色，这时A，B，C的涂法有4x3x2-24种，D只要不与C同色即可，故D有2种涂法，

所以不同的涂法共有24+24x2=72（种）.

排列组合问题中的染色问题一般难度较大，通常需用两个计数原理来求解.求解的思路是：先分为若干类，再将每类分成若干个“完整的步骤”，求出完成每个步骤的方法数，最后根据分步计数原理和分类计数原理得出总数.

三、排队问题

排队问题也是排列组合问题中的常见问题之一，此类问题常常会对排队的顺序和队员有特殊的要求.解答这类问题应从问题中的特殊要求人手，若要求n个队员中有m个队员不相邻，可以采用插空法求解;若要求n个队员中有m个队员相邻，则考虑用捆绑法求解;若要求将部分队员均匀分组，就需要对分组的情况进行讨论.

例6.10位同学在进行队列训练，前排站3人，后排站7人，现体育老师要求从后排的7人中调2人至前排，如果其他人的相对顺序不变，那么有（ ）种不同的调整方案.

分析：根據题意可知本题是分步计数问题，需分两步完成，第一步从后排的7人中选出2人;第二步，在前排安排好2人的座位，最后根据分步计数原理即可解题.

解：先从后排的7人中选择2人，有C;种方案，然后让2个人从5个座位中选2个，有A;种方案，所以不同的调整方案有C7A5，本题选B.

例7.3位老师和5位同学排成一排.

（1）如果老师必须全排在一起，有多少种不同的排法？

（2）如果老师不相邻，有多少种不同的排法？

（3）如果老师不在两端，有多少种不同的排法？

解：（1）由于3位老师都必须排在一起，所以可将他们视为一个整体，与5位同学一起，共有6种元素，有A：种排法.3位老师排在一起，有A：种排法，所以总共A：A3 =4320种排法.

（2）要确保3位老师不相邻，可先将5位同学排好，有A：种不同的排法;每2位相邻的同学中间有一个空位，则总共有4个空位，加上两端，总共6个空位，然后让3位老师插入这6个空位中，就可以确保任意2位老师都不相邻，有A;种排法，所以总共A6 A; A3=14400种不同的排法.

（3）由于老师不在两端，所以需从5位同学中选出2位排在两端，有A;种排法，其他人6种随意排列，有A：种排法，所以总共A5 A：=14400种排法.

第一个问题为相邻问题，通常采用捆绑法求解;第二个问题为不相邻问题，一般需用插空法求解;第三个问题中的元素有特殊要求，需采用优先法求解.

路线问题、染色问题以及排队问题都是常见的排列组合问题，均须灵活运用分类、分步进行的计算原理来求解.因此在解题时，我们需明确事件的类型、完成这件事所需的步骤，然后逐类、逐步进行操作，根据计数原理找出可能出现的情况，求得问题的答案.