排列組合中的染色問(wèn)題

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

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

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

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

圖1

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

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

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

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

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

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

證明： 第O小塊可以從四種顏色中任意選一種有種，設(shè)n個(gè)小塊區(qū)域D1、D2、Dn…的涂法總數(shù)為an，整個(gè)圖形的涂法總數(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只有一種涂色方法。

由分類(lèi)計(jì)數(shù)原理知：

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

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

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

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

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

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

圖4

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

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