圆环染色问题公式及推导过程

· · 个人记录

圆环染色问题公式及推导过程

图的话大家可以自己上网上搜搜

题意：圆环上有 n 个区域，m 种颜色，要求相邻的两个区域颜色不同，问有多少种染色方法

记用m种不同颜色为 n 个区域进行染色的方法种数为 a_1 ，对于 区域 A_1 ，很显而易见区域 A_1 有 m 种方式

由于相邻区域的颜色不能相同，所以区域 A_2 有 m-1 种方式

同理， A_3 , A_4 ,\cdots , A_n 分别有 m-1 种染色方式（不论 A_n 是否与 A_1 同色），共有 m(m-1)^{n-1} 种方式

但是这些方式中要分为两类：

因为 A_n 不能与 A~1~ 同色，所以此时正确的答案： a_n=m(m-1)^{n-1}-a_{n-1}

两边同时减去 (m-1)^n

\begin{aligned} a_n-(m-1)^n & =m(m-1)^{n-1}-a_{n-1}-(m-1)^n \\ & =(m-1)^{n-1}[m-(m-1)]-a_{n-1} \\ & =-[a_{n-1}-(m-1)^{n-1}] \end{aligned}

因为a_2=m(m-1)，接下来，递推后带入a_2可得：

\begin{aligned} a_n-(m-1)^n&=-[a_{n-1}-(m-1)^{n-1}] \\ &=(-1)^2[a_{n-2}-(m-1)^{n-2}] \\ &=\cdots \\ &=(-1)^{n-2}[a_2-(m-1)^2] \\ &=(-1)^{n-2}(m-1) \\ &=\frac{(-1)^n}{(-1)^2}(m-1) \\ &=(-1)^n(m-1) \end{aligned}

所以 a_n=(-1)^n(m-1)+(m-1)^n (m\ge2)

特殊的：a_1=m