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

蔡振树

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

一、路线问题

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

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

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

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

二、染色问题

染色问题是指将几个不同的区域染上不同颜色的问题.解答染色问题应从颜色的种类以及问题的特殊要求两方……