福建省霞浦縣松港中心小學(xué) 林維祥

引言 組合計數(shù)問題是組合數(shù)學(xué)的重要內(nèi)容，也是競賽數(shù)學(xué)不可或缺的重要組成部分，而染色問題是數(shù)學(xué)競賽中常見的一類問題，也是與實際生活聯(lián)系最為直接的內(nèi)容. 若能順利解決此類問題則其他排列組合問題也就迎刃而解了.

解決組合計數(shù)問題的主要方法有枚舉法、利用計數(shù)原理及基本公式、遞推方法、容斥原理等，其中蘊(yùn)含著分類討論、轉(zhuǎn)化和化歸、函數(shù)與方程等數(shù)學(xué)思想。在平時遇到的某些計數(shù)問題(如染色問題)看似排列組合類應(yīng)用題， 但又復(fù)雜萬分，若從元素遞增的角度考慮，建立遞推數(shù)列就能迎刃而解.

例：如圖1所示，將一個城市劃分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一種顏色，有4種不同顏色可供選擇，不同的著色方法有多少？

圖1

解：（1）先給B、D著相同的顏色，有種方法，再依次給A、C、E著色，有種方法，共有種方法；

（2）先給B、D著不同顏色，有種方法，再依次給A、C、E著色，有種方法，共有種方法。

所以，不同的著色方法共有

例題中的圖形我們可以將其抽象為圖2，即把圖形分成如圖的五塊，則改變圖形至圖3，即將圖形分成n+1塊，有

命題1 如圖3所示的一個圖形被分成n+1塊小塊，現(xiàn)將其染色，要求相鄰的小塊不得使用同一種顏色，有四種顏色可供選擇，則有種方法。

分析：如圖3中第O塊與每個小塊都相鄰，則其所涂的顏色必與剩余的任何一個小塊的顏色不同；因此，當(dāng)O塊涂了四種顏色中的一種后，就只剩下三種顏色可供剩余的小塊涂色，根據(jù)此分析，我們有如下證明：

證明： 第O小塊可以從四種顏色中任意選一種有種，設(shè)n個小塊區(qū)域D1、D2、Dn…的涂法總數(shù)為an，整個圖形的涂法總數(shù)為bn。不難算出

現(xiàn)尋找an的遞推關(guān)系：當(dāng)D1、D2、Dn…區(qū)域涂色完畢后，區(qū)域Dn+1的涂色有兩種情況：

第一種情況：D1與Dn顏色一樣的涂法為an-1，區(qū)域Dn+1有2種涂色方法；

第二種情況：D1與Dn顏色不一樣的涂法為an，區(qū)域Dn+1只有一種涂色方法。

由分類計數(shù)原理知：

經(jīng)檢驗n=2時，也適合上式。

若將命題1中的顏色從4種增加到m種，則有

命題2 如圖3所示的一個圖形被分成n+1塊小塊，現(xiàn)將其染色，要求相鄰的小塊不得使用同一種顏色，有m種顏色可供選擇，則有種方法。

證明： 設(shè)n個小塊區(qū)域D1、D2、Dn…的涂法總數(shù)為an，整個圖形的涂法總數(shù)為bn。

證明與命題2的證明相同。

推論：若將圖3的圖形再復(fù)雜化成如圖4所示的圖形，現(xiàn)對其進(jìn)行染色，要求相鄰的小塊顏色不同，有m種顏色可供選擇，則有種 方法。

圖4

分析：圖4中的圖形相對圖3增加了n個外面的半圓，而外面的半圓的染色數(shù)目只與相鄰的小塊顏色有關(guān)（如B1的顏色只與B有關(guān)，即B1與B顏色不相同）。當(dāng)里面的小塊已經(jīng)染色完畢后，A1還有m-1種顏色可供選擇，同理B1,C1均有m-1種顏色可供選擇。所以根據(jù)乘法原理共有種方法。

從上可知，常規(guī)的方法不僅繁雜而且容易遺漏；但是若能熟練運(yùn)用式（*）或（**），則問題就變得簡單易解，而且在解題過程中不會出現(xiàn)重復(fù)或遺漏的情況。