“化歸”法在涂色問題中的應用

在高中數學的排列組合問題中，經常會遇到關于涂色的問題，本文主要對用“化歸”的數學思想來處理這類問題做一些研究和探索。

問題1：用3種不同顏色給圖（1）中的三個區域涂色，如果每一個區域涂一種顏色，相鄰兩區域不能涂同一種顏色，共有多少種不同的涂色方法。

■

分析：從A區域開始按A、B、C順序涂色，A區域有3種涂法，B區域因與A區域相鄰，要與A區域不同色，有2種涂法，C區域只要與前面的B區域不同色，有2種涂法，所以根據分步計數原理得涂色的方法總數為3×2×2=12種。

問題2：用3種不同顏色給圖（2）中的三個區域涂色，如果每一個區域涂一種顏色，相鄰兩區域不能涂同一種顏色，共有多少種不同的涂色方法。

分析：可以仿照問題1從A區域開始按A，B，C順序涂色，A區域有3種涂法，B區域因與A區域相鄰，只要與A區域不同色，有2種涂法，C區域因與A區域和B區域均相鄰，故只有1種涂法，所以根據分步計數原理得涂色的方法總數為3×2×1=6種。

問題3：用3種不同顏色給圖（3）中的四個區域涂色，如果每一個區域涂一種顏色，相鄰兩區域不能涂同一種顏色，共有多少種不同的涂色方法。

分析：在這里能否仿照問題2那樣來處理呢？我們發現此時在涂色的過程中，我們需要考慮區域A與區域C是否同色。①若區域A與區域C不同色，則有3×2×1×1=6種涂法；②若區域A與區域C同色，則有3×2×1×2=12，所以根據分類計數原理得涂色的方法總數為6+12=18種。這里從方法上來說已經和問題1、問題2的處理不同了，在這里出現了分類討論的數學思想。我們思考，若平面區域再增多，問題又該怎么解決？

問題4：用3種不同顏色給圖（4）中的五個區域涂色，如果每一個區域涂一種顏色，相鄰兩區域不能涂同一種顏色，共有多少種不同的涂色方法。

分析：在這個問題中，我們不能利用問題2或問題3的解決方法來解決問題4，討論較為復雜，那該怎么辦呢？重新思考，問題1屬于相鄰的直線型問題，問題2、3、4屬于首尾相鄰的環狀問題。我們能否用解決直線型的方法來解決環狀問題呢？它們之間有什么聯系嗎？從問題3來看，若是直線型的問題則總共的涂法有3×2×2×2=24種，但是到了環狀就不能這樣計算，原因主要在于這樣會出現區域A與區域D同色的情況，不合題意。但是，反過來看，這也給了我們一些啟發，我們只要在上面的基礎上去掉區域A與區域D同色的情況不就得到了問題3的解決方案了。而區域A與區域D同色的情況就是問題2了。所以問題3的涂色方法總數為24-6=18種。以上在解決問題3的過程中用到了數學中的“化歸”思想。類似的，我們可以用同樣的方法來處理問題4。首先先將其看做是五個區域的直線型問題，則涂法有3×2×2×2×2=48種，再在此基礎上去掉區域A與區域E同色的環狀問題，即問題3的涂法數18，最終得到問題4的涂法數為48-18=30種。這樣一般的n區域首尾相鄰的問題都可以用這種“化歸”的思想逐個解決了。從上面我們還發現，若將不同環狀區域的涂法數看成關于區域數n的一個數列，則這個數列中的項之間存在著遞推關系，我們是否可以通過這個數列的遞推關系，求出這個數列的通項公式，從而解決這一類問題呢？

為了敘述方便，設分成3個區域時涂色的方法為a3種，分成4個區域時涂色的方法為a4種，一般的，分成n個區域時涂色的方法為an種，則當n≥3時，an+1=3×2n-an=-an+3×2n設an+1-λ·2n+1=-（an-λ·2n），即an+1=-an+（2λ+1）2n，∴2λ+1=3，∴λ=1，∴■=-1，∴an-2n=（a3-23）·（-1）n-3=-2·（-1）n-3=-2·（-1）n-2

∴an-2n+2·（-1）n-2=2n+2·（-1）n（n≥3）

更一般的，若用m種不同顏色給首尾相鄰的n塊環狀區域涂色，相鄰兩區域不能涂同一種顏色，總的涂法數類似可得當n≥3時，an+1=m×（m-1）n-an=-an+m×（m-1）n，設an+1-λ·（m-1）n+1=-［an-λ·（m-1）n］，即an+1=-an+λm（m-1）n，∴λm=m，∴λ=1，∴■=-1，∴an-（m-1）n=［a3-（m-1）3］·（-1）n-3=（m-1）·（-1）n-2

∴an=（m-1）n+（m+1）·（-1）n-2=（m-1）n+（m-1）·（-1）n （n≥3）（*）

問題5：用4種不同顏色給圖（5）中的區域涂色，如果每一個區域涂一種顏色，相鄰兩區域不能涂同一種顏色，共有多少種不同的涂色方法。

分析：區域1與其他4個區域都相鄰，比較特殊，我們先考慮它，有4種涂法，剩下的2、3、4、5區域就是用3中顏色涂4個首尾相鄰的環狀問題，由（*）式得有24+2·（-1）4=18種涂法，由分步計數原理得，總的涂法共有4×18=72種。

問題6：如圖（6）所示，已知四棱錐P-ABCD，從給定的4種不同的顏色中選用若干顏色在四棱錐的各個面上，要求相鄰的面不同色，有多少種涂法？

分析：這種面的涂色問題可轉化為區域涂色的問題來求解。底面相當于問題5中的區域1，四個側面相當于問題5中的區域2、3、4、5，所以涂色的方法有72種。

說明：①若為n棱錐，有m種顏色選用，則其一般性結果為m［（m-2）n+（m-2）（-1）n］；

②如果將題中面涂色改為點涂色問題，只需視“點”為“面”與原題是等價的；

③若研究的問題是n棱柱，只需按兩底同色和兩底不同色兩種情況討論，問題亦不難解決。

本文主要對高中數學中的一些特殊的涂色問題，用“化歸”的數學思想作了一些簡要研究和探索。

（作者單位 江蘇省海門市三廠中學）

編輯 楊兆東