例谈三类排列组合问题及其解法

蔡振树

排列组合问题一般和实际生活息息相关.排列组合问题主要考查事件中可能出现的情况的种数.要顺利解答此类问题，我们需灵活运用两个计数原理：分类计数原理和分步计数原理.排列组合问题的命题形式有很多种，如求数字的排列顺序的种数、求排队的顺序种数、求线路的条数、求染色的可能情况数等.本文重点探讨以下三类排列组合问题及其解法.

一、路线问题

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

例 1.图1为某城市的道路规划图，共有7条纵向道路，有5条横向道路.若公交车队从 A处出发到 B处且经过 C处的最短路线有______条.

解析：从 A处到 C处有2条纵向道路、3条横向道路，所以从 A处到 C处有 种走法;从 C处到 B处有2条纵向道路、3条横向道路，所以从 C处到 B处有 种走法，根据分步计数原理可得共有 种走法.即从 A处出发到 B处且经过 C处的最短路线有100条.

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

二、染色问题

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

例2.某一地区可分为5个区域，如图2所示.现在要给这块地图涂色，要求每相邻的区域不能使用相同的颜色，现在有4种颜色可供选择，则不同的涂色方法共有____种.

解析：①若使用4种颜色，可先涂第1区域，将剩下的3种颜色涂满剩下的4个区域，那么相对的2个区域就要使用同1种颜色，则有 种涂法;

②若使用3种颜色，就要从4种颜色选出3种，且2、4区域，3、5区域都要涂同一种颜色，则有 种涂法;

综上所述，一共有48+ 24= 72种涂法.

染色问题较为复杂，一般需分几种情况进行讨论，然后逐步对每一种情况进行分析，从而完成涂色任务.

三、排队问题

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

例3.现有3名男生和5名女生排成一排合照，如果两端都不排女生，则有____种排法.

解析：首先从3名男生中任选2名放在队伍的两端，有 种排法;然后将剩余的6人随意排列，有 种排法;

根据分步计数原理可得共有6×720= 4320种排法.

对于有特殊要求的问题，我们一般优先处理特殊元素或者位置.对于本题，需优先考虑排队伍的两端，然后再排剩余的位置.

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

（作者单位：福建省石狮市华侨中学）