环形染色问题的公式解法

李学民　聂二军

定理 如图把一个圆分成n(n≥2)个扇形区域An,现用m(m≥2)种不同颜色为这n个区域染色，要求相邻两个区域Ai与Ai+1颜色不同，则不同的染色方法共有(m-1)n+(m-1)(-1)n种

证明 记用m种不同颜色为n个区域进行染色的方法种数为an.

对于区域A1，有m种染法；由于相邻区域颜色不能相同，区域A2有m-1种染法；同理A3，A4，…，An-1分别有m-1种染法；区域An有m-1种染法（不论区域An是否与A1同色），共有m(m-1)n-1种染法但m(m-1)n-1种染法中要分为两类，一是An与A1不同色，二是An与A1同色，同色时可把An与A1看作为同一区域，此时染法总数为an-1,因此有an+an-1=m(m-1)n-1

利用由数列递推公式求通项公式的方法

可设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的等比数列因为n≥2,则其首项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,对n分别取3,4,5,…,然后叠加化简得an)

用此公式法求近几年高考题中出现的染色问题则非常简便

例1 （2008年全国卷·理）如图一个环形花坛分成A、B、C、D四块，现有4种不同的花供选种，要求每块里种1种花，且相邻的2块种不同的花，则不同的种法总数为（）

A96B84C60D48

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

例2 （2003年全国卷·文）如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有种

解 先对区域1染色有C14种染法（因在中心），然后把问题转化为用3种颜色对4个扇形区域进行染色的环形染色问题，此时n=4,m=3,a4=(3-1)4+(-1)4·(3-1)=18.

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

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文