环形染色问题 紫钦 · 2023-12-27 11:53:18 · 个人记录 问题描述：n 个格子排成一圈，有 m 种颜色，要求相邻格子颜色不同，问有几种涂色方案。 设 f_n 表示给环形排列的 n 个格子染色的方案数。 考虑给排成一行的 n 个格子染色，则共有 m(m-1)^{n-1} 种方案。 若把把这一行 n 个格子的首尾相连，则有两种情况： 首尾颜色不同，这样的情况共有 f_n 种。 首尾颜色相同，这样的情况等价于环形排列的 n-1 个格子染色的方案数，为 f_{n-1} 种。注意，这只对于 n\geqslant 3 成立。 则 f_n+f_{n-1}=m(m-1)^{n-1}，n\geqslant3， 方法一： 求交错和： \sum_{i=3}^n(-1)^{n-i}(f_i+f_{i-1})=f_n+(-1)^{n-1}f_2 \sum_{i=3}^n(-1)^{n-i}m(m-1)^{i-1}=m(-1)^{n-1}m(m-1)^2\frac{(1-m)^{n-2}-1}{(1-m)-1}=m(m-1)^{n}-(-1)^{n}m(m-1)^2 又 f_2=m(m-1)， 故 f_n=m(m-1)^{n}-(-1)^{n}m(m-1)(m-2)，