探究計數原理在染色問題中的應用

秦雪梅

摘 要：中學數學課程中引進的關于排列、組合的計算公式都是以兩個計數原理為基礎的，而一些較復雜的排列、組合應用題的求解，更是離不開兩個基本原理，所以正確理解兩個基本原理并能解決實際問題是學習分類計數原理與分步計數原理的重點內容

關鍵詞：計數原理；探討和歸納；培養學生邏輯思維能力；創新思維能力。

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

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

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

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

A B C D

解：根據分步計數原理，按 的順序染色，故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種；

綜上： 種。

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

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

（4）若用四種顏色，則先染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的解法三，所以

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

（四）線段染色問題

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

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

由通項公式

知：N

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

解：四面體A-BCD中共有三組對棱，AB與CD，AD與BC，BD與AC，共四種顏色，故必有兩組對棱組內同色，但組與組之間不同色，所以

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

正確使用兩個基本原理的前提是要學生清楚兩個基本原理使用的條件.而原理中提到的分步和分類，學生不是一下子就能理解深刻的，面對復雜的事物和現象學生對分類和分步的選擇容易產生錯誤的認識，所以分類計數原理和分步計數原理的準確應用是本節課的教學難點。必需使學生認清兩個基本原理的實質就是完成一件事需要分類還是分步，才能使學生接受概念并對如何運用這兩個基本原理有正確清楚的認識。教學中兩個基本問題的引用及引伸，就是為突破難點做準備。

（作者單位：重慶市萬州高級中學）