環(huán)形染色問題的公式解法

李學(xué)民　聶二軍

定理 如圖把一個(gè)圓分成n(n≥2)個(gè)扇形區(qū)域An,現(xiàn)用m(m≥2)種不同顏色為這n個(gè)區(qū)域染色，要求相鄰兩個(gè)區(qū)域Ai與Ai+1顏色不同，則不同的染色方法共有(m-1)n+(m-1)(-1)n種

證明 記用m種不同顏色為n個(gè)區(qū)域進(jìn)行染色的方法種數(shù)為an.

對(duì)于區(qū)域A1，有m種染法；由于相鄰區(qū)域顏色不能相同，區(qū)域A2有m-1種染法；同理A3，A4，…，An-1分別有m-1種染法；區(qū)域An有m-1種染法（不論區(qū)域An是否與A1同色），共有m(m-1)n-1種染法但m(m-1)n-1種染法中要分為兩類，一是An與A1不同色，二是An與A1同色，同色時(shí)可把An與A1看作為同一區(qū)域，此時(shí)染法總數(shù)為an-1,因此有an+an-1=m(m-1)n-1

利用由數(shù)列遞推公式求通項(xiàng)公式的方法

可設(shè)an+α·(m-1)n=-［an-1+α·(m-1)n-1］,

整理有an+an-1=-m(m-1)n-1·α

與an+an-1=m(m-1)n-1比較得α＝-1.

則有an-(m-1)n=-［an-1-(m-1)n-1］,令bn=an-(m-1)n,則｛bn｝是公比為-1的等比數(shù)列因?yàn)閚≥2,則其首項(xiàng)b2=a2-(m-1)2=m(m-1)-(m-1)2=m-1.

得bn=an-(m-1)n=(-1)n-2·(m-1)=(-1)n(m-1)(n≥2).

即an=(m-1)n+(-1)n(m-1)(n≥2).

(由a2=m(m-1),將an+an-1=m(m-1)n-1式兩邊同乘以（-1)n,得（-1)nan-(-1)n-1an-1=(-1)nm(m-1)n-1,對(duì)n分別取3,4,5,…,然后疊加化簡(jiǎn)得an)

用此公式法求近幾年高考題中出現(xiàn)的染色問題則非常簡(jiǎn)便

例1 （2008年全國(guó)卷·理）如圖一個(gè)環(huán)形花壇分成A、B、C、D四塊，現(xiàn)有4種不同的花供選種，要求每塊里種1種花，且相鄰的2塊種不同的花，則不同的種法總數(shù)為（）

A96B84C60D48

解 由公式n=4,m=4,a4=(4-1)4+(-1)4·(4-1)=84.選B

例2 （2003年全國(guó)卷·文）如圖，一個(gè)地區(qū)分為5個(gè)行政區(qū)域，現(xiàn)給地圖著色，要求相鄰地區(qū)不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同的著色方法共有種

解 先對(duì)區(qū)域1染色有C14種染法（因在中心），然后把問題轉(zhuǎn)化為用3種顏色對(duì)4個(gè)扇形區(qū)域進(jìn)行染色的環(huán)形染色問題，此時(shí)n=4,m=3,a4=(3-1)4+(-1)4·(3-1)=18.

所以不同的染色方法共有4×18=72種

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文