林維祥

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

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

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

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

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

所以，不同的著色方法共有 + =72（種）。

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

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

種方法。

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

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

現(xiàn)尋找 的遞推關系：當 、 、… 區(qū)域涂色完畢后，區(qū)域 的涂色有兩種情況：

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

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

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

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

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

則有

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

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

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