例談三類排列組合問題及其解法

蔡振樹

排列組合問題一般和實際生活息息相關.排列組合問題主要考查事件中可能出現的情況的種數.要順利解答此類問題，我們需靈活運用兩個計數原理：分類計數原理和分步計數原理.排列組合問題的命題形式有很多種，如求數字的排列順序的種數、求排隊的順序種數、求線路的條數、求染色的可能情況數等.本文重點探討以下三類排列組合問題及其解法.

一、路線問題

路線問題是一類綜合性較強的排列組合問題，一般求最短路線的組合方案數.解答這類排列組合問題，需首先明確從起點到終點要分多少步走，然后找出幾種可能的路線，根據分步計數原理分別求出每條線路中可能出現的情況數，最后運用分類計數原理求得結果.

例 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種排法.

對于有特殊要求的問題，我們一般優先處理特殊元素或者位置.對于本題，需優先考慮排隊伍的兩端，然后再排剩余的位置.

路線問題、染色問題以及排隊問題都是常見的排列組合問題，都需靈活運用分類、分步計數原理來求解.因此在解題時，我們需明確事件的類型，完成做每一件事所要求的步驟，然后逐類、逐步進行操作，根據兩個計數原理找出可能出現的情況，求得問題的答案.

（作者單位：福建省石獅市華僑中學）