蔡振樹

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

一、路線問題

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

例 1.圖1為某城市的道路規(guī)劃圖，共有7條縱向道路，有5條橫向道路.若公交車隊從 A處出發(fā)到 B處且經(jīng)過 C處的最短路線有______條.

解析：從 A處到 C處有2條縱向道路、3條橫向道路，所以從 A處到 C處有 種走法;從 C處到 B處有2條縱向道路、3條橫向道路，所以從 C處到 B處有 種走法，根據(jù)分步計數(shù)原理可得共有 種走法.即從 A處出發(fā)到 B處且經(jīng)過 C處的最短路線有100條.

解答線路問題，需要明確線路的方向和行走的步驟，合理運用分步計數(shù)原理和分類計數(shù)原理來分析每條路線中可能出現(xiàn)的情況.

二、染色問題

染色問題是指將幾個不同的區(qū)域染上不同顏色的問題.解答染色問題應(yīng)從顏色的種類以及問題的特殊要求兩方面考慮.首先應(yīng)考慮選取的顏色種數(shù)，然后根據(jù)題目的要求將不同的區(qū)域分情況進行填色，最后根據(jù)分類計數(shù)原理即可得到染色方案的總數(shù).

例2.某一地區(qū)可分為5個區(qū)域，如圖2所示.現(xiàn)在要給這塊地圖涂色，要求每相鄰的區(qū)域不能使用相同的顏色，現(xiàn)在有4種顏色可供選擇，則不同的涂色方法共有____種.

解析：①若使用4種顏色，可先涂第1區(qū)域，將剩下的3種顏色涂滿剩下的4個區(qū)域，那么相對的2個區(qū)域就要使用同1種顏色，則有 種涂法;

②若使用3種顏色，就要從4種顏色選出3種，且2、4區(qū)域，3、5區(qū)域都要涂同一種顏色，則有 種涂法;

綜上所述，一共有48+ 24= 72種涂法.

染色問題較為復(fù)雜，一般需分幾種情況進行討論，然后逐步對每一種情況進行分析，從而完成涂色任務(wù).

三、排隊問題

排隊問題也是排列組合中常見的問題之一，此類問題常常會對排隊的順序和隊員有特殊的要求.解答這類問題應(yīng)從問題中的特殊要求切入，若要求 n個隊員中有 m 個隊員不相鄰，可以采用插空法求解;若要求 n個隊員中有 m 個隊員相鄰，則考慮用捆綁法求解;若要求將部分隊員均勻分組，就需要對分組的情況進行討論.

例3.現(xiàn)有3名男生和5名女生排成一排合照，如果兩端都不排女生，則有____種排法.

解析：首先從3名男生中任選2名放在隊伍的兩端，有 種排法;然后將剩余的6人隨意排列，有 種排法;

根據(jù)分步計數(shù)原理可得共有6×720= 4320種排法.

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

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

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