“無心”和“有心”染色問題

【摘要】 本文對“無心”和“有心”染色問題建立了遞推數列模型，通過對遞推數列模型的運算給出了公式，使得這兩類問題的計算得到了簡化.

【關鍵詞】 “無心”染色 “有心”染色；遞推數列

圖 1 一、“無心”染色問題

如圖1，將圓分成n（n≥2）個扇形S1，S2，…，Sn，

現用m m≥2 種顏色給這些扇形染色，每個扇形染

色，每個扇形染一種顏色且要求相鄰扇形的染色互不

相同，問有多少種染色方法？

解析 設染色方法數為an.

（1）求初始值.n=2時，給S1染色有m種方法，繼而給S2染色只有m-1種方法，（因S1與S2不同色），所以a2=m（m-1）.

（2）求遞推關系.因S1有m種染色方法，S2有m-1種染色方法，S3有m-1種染色方法，…，Sn有m-1種染色方法（只保證Si+1與Si不同色，i=1，2，…，n-1；而不保證Sn與S1不同色），這樣共有m（m-1）n-1種染色方法，這些染色方法可分為兩類：

一類是Sn與S1不同色，這類方法有an種.另一類是Sn與S1同色，則將Sn與S1合并為一個扇形，并注意到此時Sn-1與S1不同色，故這時的染色方法有an-1種.由加法原理得：an+an-1=m（m-1）n-1.

（3）求an.

令bn= an （m-1）n ，則bn+ 1 m-1 bn-1= m m-1 ，

圖 2 即：bn-1=- 1 m-1 （bn-1-1）.

可得：an=bn·（m-1）n=（m-1）n+（-1）n（m-1）.

例1 如圖2，用4種不同的顏色，給一個六棱錐的側面

染色，一種顏色染一個側面，而且相鄰面的顏色不能相同，

問有幾種染色方法？

解析 如圖3所示，可把立體圖形連續壓縮成平面圖形，

該問題轉化為無心染色問題，由m=4，n=6，可得an=（4-1）6+（-1）6（4-1）=36+3=732種.所以有732種染色方法.

圖 3

二、“有心”染色問題

圖 4 如圖4，設用m（m≥4，m∈ N +）種顏色給n（n≥3，n∈ N +）邊形的頂點和中心點（染色點=n+1）染色，每點染一色且相鄰點染不同的色，不同的染色方法為aN.

解析 （1）先染A0，有m種染法；

（2）再染A1A2….

A1與A0不同色，有（m-1）種染法；A2與A0，A1不同色，有（m-2）種染法…

當n=3時，a3=（m-1）（m-2）（m-3）；

當n>3時，已知A1，A2有（m-1）、（m-2）種染法；

A3與A0，A2不同色，有（m-2）種染法；同理，A4，…，An-1均有（m-2）種染法.最后得到An，若考慮An與An-1不同色，仍有（m-2）種，則得：（m-1）（m-2）n-1種染法.

但該計算中有兩種情況：一種是An與A1不同色，這符合要求，有an-1種染法，另一種是An與A1同色，這不符合要求，應排除，這時可以把An與A1合并看作一點，則得排除的染法為an-1種，故得：a3=（m-1）（m-2）（m-3），…，an=（m-1）（m-2）n-1-an-1，

遞推得：an=（m-2）n+（-1）n·（m-2）.

綜上 可得公式：aN=m（m-2）[（m-2）n-1+（-1）n]=m（m-2）n+ （-1）nm（m-2）.

（式中m≥4，m∈N+；n≥3，n∈N+）.

例2 若想給一個三棱錐S-ABC的每個頂點染上一種顏色，并使同一條棱的兩端點異色，如果現有4種顏色可供使用，那么不同的染色方法的總數是多少？

圖 5

解 如圖5所示，可把立體圖形

連續壓縮成平面圖形，該問題轉化為

有心染色問題，由m=4，n=3，

可得aN=4（4-2）3+（-1）3×4×（4-2）=24種.

所以有24種染色方法.

【參考文獻】

[1]劉華巧，李德勝.幾類遞推數列通項公式的推導及應用[J].高師理科學刊，2007，7.

[2]唐臂.遞推數列的通項公式[J].科技創新導報，2010，11.

[3]曹汝成.組合數學[M].華南理工大學出版社，2012，7.