排列組合中的染色問題

林維祥

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

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

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

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

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

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

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

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

種方法。

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

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

現尋找 的遞推關系：當 、 、… 區域涂色完畢后，區域 的涂色有兩種情況：

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

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

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

證明： 設n個小塊區域 、 、… 的涂法總數為 ，整個圖形的涂法總數為 。

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

則有

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

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

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