环染色问题——m种颜色染n块区域

2022-01-22 12:49 作者:匆匆-cc 0人读过 | 我要投稿

一个环形的花坛，分成n块，有m种不同颜色的花可供种植，要求相邻区域颜色不能相同，共有多少种方法？

该问题称为环染色问题。

同样是涉及 $n$ 的问题，不妨采用数列递推法。

易知， $D_2%3Dm(m-1)$ ， $D_3%3Dm(m-1)(m-2)$ 。

考察图中①、②两块花坛。

若①、②同色，则中间一块有（ $m-1$ ）种选择，剩下的部分等价于 $D_%7Bn-2%7D$ （细品，精髓所在），由乘法原理，共 $(m-1)D_%7Bn-2%7D$ 种选择。

若①、②不同色，则中间一块有（ $m-2$ ）种选择，剩下的部分等价于 $D_%7Bn-1%7D$ （细品，仍然是精髓所在），由乘法原理，共 $(m-2)D_%7Bn-1%7D$ 种选择。

于是，有

$D_n%20%3D%20(m-1)D_%7Bn-2%7D%2B(m-2)D_%7Bn-1%7D$

考察特征根方程

$x%5E2-(m-2)x-(m-1)%3D0$

两根分别为

$x_1%3D-1%2Cx_2%3Dm-1$

从而

$D_n%3DC_1%5Ccdot(-1)%5En%2BC_2%5Ccdot(m-1)%5En$

代入初始值，

$%5Cbegin%7Bcases%7D%0AD_2%3DC_1%2B(m-1)%5E2C_2%3Dm(m-1)%0A%5C%5CD_3%3D-C_1%2B(m-1)%5E3C_2%3Dm(m-1)(m-2)%0A%5Cend%7Bcases%7D$

解得

$%5Cbegin%7Bcases%7D%0AC_1%3Dm-1%0A%5C%5CC_2%3D1%0A%5Cend%7Bcases%7D$

故

$D_n%3D(m-1)%5Ccdot(-1)%5En%2B(m-1)%5En$

标签：

环染色问题——m种颜色染n块区域的评论 (共条)