計數原理在四色問題中簡單應用的探討

計數原理和染色問題均是高考中常考內容，且與染色問題有關的試題內容新穎有趣，數學思想豐富，解題技巧靈活多變，故這類問題有利于培養學生的創新思維能力，有利于培養分析和解決問題的能力。常見的解題原則有（1）.根據分步計數原理，對各個區域分步涂色，這是處理染色問題的基本方法；（2）.特殊位置或特殊元素優先考慮原則；（3）.分步處理過程中出現矛盾或問題則分類討論原則；

以下針對染色問題的特征分幾類情形進行探討和歸納。

（一）平面直線型染色問題

【例1】如圖，用4種不同的顏色給圖中所給出的四個區域涂色，每個區域涂一種顏色，若要求相鄰（有公共邊）的區域不同色，那么共有多少種不同的涂色方法？

ABCD

解：根據分步計數原理，按的順序染色，故N=4X3X3X3=108（種）

說明：本題也可以對C與A同色與否，B與D同色與否進行討論解決，但計算過程復雜，解題不簡潔，利用分別計數原理簡潔。

（二）平面環形染色問題

【例2】將例1中四個區域的位置做出如下調整，如下圖，相鄰區域不同色，問共有多少種不同的染色方法？

解：根據分步計數原理，按的順序進行染色，由于C區域是特殊位置，應進行討論：（1）當C與A同色時，則=4x3x1x3=36；

（2）當C與A不同色時，則=4x3x2x2=48；

所以N==36+48=84（種）.

【變式1】如下圖，將一個圓分成4個扇形，每個扇形用4中不同顏色染色，要求相鄰區域不同色，問共有多少種不同的染色方法？

解：本變式題本質與例2完全相同，故N=84（種）。

【變式2】如下圖，將一個圓形分成n個扇形（），每個扇形用4種不同顏色之一染色，要求相鄰區域不同色，問共有多少種不同的染色方法？

解：圓被分成n個扇形時：

（1）當n=2時，有種，即

（2）當時，如圖知，與不同色，與不同色，，

與不同色，先將n個區域看作直線型染色問題，則共有種染色方法，但由于與鄰，所以應排除與同色的情形；而與同色時，可把、合并看成一個扇形，與前個扇形加在一起為個扇形，此時有種染色法，故有如下遞推關系：

說明：有了以上通項公式，可以解決所有扇形染色問題。

（三）棱錐型頂點染色問題

【例3】如圖，將一個四棱錐的每一個頂點染一種顏色，并使同一條棱上的兩端點異色，如果只有4種顏色可供使用，求不同的染色方法總數。

解法一：根據分步計數原理，按的順序染色，先對S、A、B染色，有4x3x2種，由于C點的顏色可能與A相同或不同，這影響到D點的染色方法，故分兩類情況討論：

（1）C與A同色，則C方法唯一，D有2種染色法，所以=4x3x2x1x2=48種；

（2）C與A不同色，則C只有一種顏色可選，D有一種選法，所以=4x3x2x1x1=24種；

綜上：種。

解法二：按顏色的種數分類討論解題

（1）若用三種顏色，則A與C同色，B與D同色，所以種；

（2）若用四種顏色，則先染P，有種，再染A，B有種，再染C有種，再染D有1種，

所以=48種；

所以（種）

解法三：將立體問題轉化為平面相鄰區域染色問題

如下圖，原問題可以轉化為將圖中五個區域用4種不同顏色染色，要求相鄰區域不同色，求不同的染色方法？其中區域P對應棱錐頂點P。

根據分步計數原理，按順序染色，由于C位置特殊，故分C與A同色和C與A不同色兩類討論：

（1）C與A同色時，則=4x3x2x1x2=48種；

（2）C與A不同色時，則=4x3x2x1x1=24種；

所以種。

【變式3】如圖四棱錐，用4種不同的顏色涂在四棱錐的各個面上，要求相鄰不同色，有多少種涂法？

解：將立體圖形問題轉化為平面區域染色問題，如左圖，

圖中5號區域相當于四棱錐中底面ABCD，其他 4個區域相當于四棱錐四個側面，問題又回到例3的解法三，所以

總結：變式題的解題方法體現了數學思想中的化歸思想，對培養學生能力有很好的意義。

【推廣探究】

1.將例3中的四棱錐改為五棱錐，其染色方法共有多少？

方法1：將五棱錐轉化為平面相鄰區域染色問題，如圖，按的 順序問題，討論C與A同色或C與A不同色，再討論D與B或D與B不同色，可得

方法2.由題意，平面共有6個區域，用4種顏色，則必有兩對區域分別同色，故用枚舉法討論解題即可。例如A與C同色，B與D同色，此時有共有5種情形；

所以。

2.推廣到n棱錐

對n棱錐的頂點用4種不同顏色進行染色，要求相鄰頂點不同色，求不同的染色方法數。

如圖，先根據分布計數原理，由共有N=種，但其中包含了“同色”和“不同色”兩大類。

當同色時，染色總數就是，當不同色時，染色總數就是。

故有：

可解得：（種）。

（四）線段染色問題

【例4】：如圖，用4種不同顏色給五邊形ABCDE每條邊染色，要求一條邊只染一色，且相鄰邊不同色，問共有多少種不同染色方法？

解：本題的本質就是環形染色問題，

由通項公式

知：N

【變式4】如圖，用四種不同的顏色給正四面體A-BCD的每條棱染色，要求每條棱只染一色，且相鄰邊不同色，問共有多少種不同染色方法？

解：四面體A-BCD中共有三組對棱，AB與CD，AD與BC，BD與AC，

共四種顏色，故必有兩組對棱組內同色，但組與組之間不同色，

所以

小結：計數原理是排列組合的基礎，也是染色問題研究的基礎，通過對四色染色問題的簡單探討，我們發現染色問題中分類討論思想，轉化與化歸思想等數學思想得到充分應用，所以染色問題是培養學生邏輯思維能力，創新思維能力，空間想象能力和轉化能力的很好的平臺。