恰用m種顏色著色的一類計數問題的算法

摘 要：用m種不同的顏色對圓內n個扇形染色（相鄰扇形不同色）的方法數可用公式表示，其中包含恰用2種、恰用3種、…、恰用m種顏色染色的方法.如果要計算恰用m種不同的顏色對圓內n個扇形染色（相鄰扇形不同色）的方法數難度更大.本文用猜想證明和算法程序解決了該問題.

關鍵詞：恰用m種顏色；計數問題算法

兩道高考題“牽”出的計數問題

2003年高考數學全國卷理科15題如下：如圖1，一個地區分為5個行政區域，現給地圖著色，要求相鄰地區不得使用同一顏色，現有4種顏色可供選擇，則不同的著色方法共有多少種？

無獨有偶，2008年高考數學全國卷理科12題如下：如圖2，一環形花壇分成A，B，C，D四塊，現有4種不同的花供選種，要求在每塊里種1種花，且相鄰的2塊種不同的花，則不同的種法有多少種？

上述兩道考題源于同一問題背景.因為前一題中，先選擇一種顏色涂1號區域后，再用余下3種顏色涂2、3、4、5號四塊區域（相鄰區域不同色），此時，與后一題的問題情景完全一致. 一般地，有下述問題：如圖3，把圓分成S1，S2，…，Sn共n個扇形（n≥2）. 現對這n個扇形著色，若有m種不同的顏色可供選擇，每個扇形一種顏色，相鄰扇形不同色，那么共有多少種不同的著色方法？利用遞推關系，可求得著色方法共有f（n，m）=（m-1）n+（-1）n·（m-1）種，因此，兩道高考題的答案分別為4f（4，3）=72和f（4，4）=84.

不同分類視角提出一類新的計數問題

在一次數學興趣小組輔導課上，筆者以上述問題背景給出一道練習題：

在圖4所示的六邊形區域內栽種植物， 要求相鄰兩塊種不同的植物， 如果有4種植物可供選擇， 那么有多少種栽種方法？

依據公式，很容易得到答案為f（6，4）=36+3=732. 而多數學生是用分類討論解決的.

分類視角1：情況①，A，E相同， C與A，E也相同時有4×3×3×3=108種；情況②，A，E相同， C與A，E不同時有4×3×3×2×2=144種；情況③，A，E不同，C與A或E相同時有4×3×2×2×3×2=288種；情況④，A，E不同，C與A，E都不同時有4×3×2×2×2×2=192種. 綜上，相加得共有732種栽種方法.

分類視角2：情況①，恰用其中的2種植物種植的種法有C×2=12種；情況②，恰用其中的3種植物種植的種法有C×（A+3×6+3×3×2×2）=240種（小括號內分“A，C，E互不同”“A，C，E都相同”“A，C，E恰有兩塊相同”討論）；情況③，恰用其中的4種植物種植的種法有480種.

學生普遍感到上述分類視角2的情況③比較困難， 無法完成討論. 筆者將該問題歸納成一類新的計數問題敘述如下：“如圖3，把圓分成S1，S2，…，Sn共n個扇形（n≥2）. 現對這n個扇形著色，若有m（2≤m≤n）種不同的顏色可供選擇，每個扇形一種顏色，每種顏色至少涂一塊區域，相鄰扇形不同色，那么共有多少種不同的著色方法？”（即恰用m種顏色的著色方法有幾種？）

新計數問題的算法

1. 尋求遞推關系

對上述扇形著色問題，當n給定時，設am=f（n，m）（2≤m≤n）表示有m種不同的顏色可供選擇的涂法種數，設bm表示恰用m種不同的顏色的涂法種數，那么

am=bm+C·bm-1+C·bm-2+…+C·bm-k+…+C·b2. ①

2. bm表達式的猜想與證明

若n足夠大， 在式子①中取m為一些特殊值可得如下結果：

當m=2時，a2=b2，即b2=a2；

當m=3時，a3=b3+Cb2，可得b3=a3-Cb2=a3-Ca2；

當m=4時，a4=b4+Cb3+Cb2，可得b4=a4-C（a3-Ca2）-Ca2=a4-Ca3+Ca2；

當m=5時，a5=b5+Cb4+Cb3+Cb2，可得b5=a5-C（a4-Ca3+Ca2）-C（a3-Ca2）-Ca2=a5-Ca4+（CC-C）a3-（CC-CC+C）a2=a5-Ca4+Ca3-Ca2.

所以猜想：bm=am-Cam-1+Cam-2+…+（-1）kCam-k+…+（-1）m-2Ca2. ②

下面用數學歸納法證明等式②.

當m=2，3，4，5時，結論已成立. 假設當m≤p（p=2，3，4，…）時，②式成立，則當m=p+1時，可知ap+1=bp+1+Cbp+Cbp-1+…+Cbp+1-k+…+Cb2，可得bp+1=ap+1-Cbp-Cbp-1-…-Cbp+1-k-…-Cb2，所以

bp+1=ap+1-C[ap-Cap-1+Cap-2+…+（-1）kCap-k+…+（-1）p-2·Ca2]

-C[ap-1-Cap-2+Cap-3+…+（-1）k-1Cap-k+…+（-1）p-3Ca2]

-C[ap-2-Cap-3+Cap-4+…+（-1）k-2Cap-k+…+（-1）p-4Ca2]

…

-C[ap-k-Cap-k-1+Cap-k-2+…+（-1）p-k-2Ca2]

…

-Ca2.③

則③式中ap-k的系數為

（-1）k+1CC+（-1）kCC+（-1）k-1CC+…+（-1）1CC

=（-1）k+1[CC-CC+CC+…+（-1）kCC]

=（-1）k+1[CC-CC+CC+…+（-1）iCC+…+（-1）kCC]. ④

而CC=CC（兩邊展開即得），所以④式可化為

（-1）k+1[CC-CC+CC+…+（-1）iCC+…+（-1）kCC]

=（-1）k+1C[C-C+C+…+（-1）iC+…+（-1）kC]

=（-1）k+1C[C-（1-1）k+1]=（-1）k+1C=（-1）k+1C.

所以bp+1=ap+1-Cap+Cap-1+…+（-1）k+1Cap-k+…+（-1）p-1·Ca2. 所以，當m=p+1時，猜想也成立.

綜上所述，對任意正整數m（2≤m≤n），②式都成立.

3. 編制算法程序來進行計算

至此， 我們已獲得如下結論：用m（2≤m≤n）種不同的顏色給圖3所示的n塊扇形著色，每個扇形一種顏色、每種顏色至少涂一塊區域，相鄰扇形不同色，那么不同的著色方法種數為：bm=am-Cam-1+Cam-2+…+（-1）kCam-k+…+（-1）m-2Ca2，其中am=（m-1）n+（-1）n（m-1）.

在具體運算中，上述公式比較繁瑣，因此，筆者根據上式進一步編制了算法程序如下，供讀者參考.

感悟

新課改提倡探究性學習， 對于一些經典問題， 教師不能簡單地將“最佳解法”直接告訴學生，而應該放手讓學生去探究知識生成和問題解決的“本真”過程. 這樣，才能讓學生在對比不同解題途徑中領悟方法、在突破細節難點處創新思路、在綜合運用知識時提升數學素養. 也只有這樣，才有可能挖掘經典問題所蘊含的探究素材，充分發揮其教育教學價值.