1670

将一个 ${\displaystyle n}$ 边形的每个顶点随机染成红、黄、蓝三种颜色之一, 且要求相邻顶点的颜色不同, 则可能的染色方式有_____种.

记 ${\displaystyle n}$ 边形中对应的染色方式种数为 ${\displaystyle a_n}$, ${\displaystyle n\ge 3}$, 顶点记为 ${\displaystyle A_1,\cdots ,A_n}$. 下面来找 ${\displaystyle a_n}$ 的递推关系.

• 如果 ${\displaystyle A_1,A_{n-1}}$ 同色, 则 ${\displaystyle A_1,A_{n-2}}$ 不同色, 所以 ${\displaystyle A_1,\cdots ,A_{n-2}}$ 组成的 ${\displaystyle n-2}$ 边形有 ${\displaystyle a_{n-2}}$ 种涂法. 此时加上 ${\displaystyle A_n}$ 的 ${\displaystyle 2}$ 种涂法, 所以共有 ${\displaystyle 2a_{n-2}}$ 种涂法.
• 如果 ${\displaystyle A_1,A_{n-1}}$ 不同色, 则 ${\displaystyle A_1,\cdots ,A_{n-1}}$ 组成的 ${\displaystyle n-1}$ 边形有 ${\displaystyle a_{n-1}}$ 种涂法, 而 ${\displaystyle A_n}$ 夹在两点之间只有 ${\displaystyle 1}$ 种涂法, 所以共有 ${\displaystyle a_{n-1}}$ 种涂法.

由上 $$a_n=a_{n-1}+2a_{n-2},$$ 解特征方程 ${\displaystyle x^2-x-2=0}$ 得到 ${\displaystyle x=2}$ 或 ${\displaystyle -1}$, 所以 $$a_n=c_1\cdot 2^n+c_2\cdot (-1{)}^n.$$ 另外可以枚举出 ${\displaystyle a_3=6}$, ${\displaystyle a_4=18}$, 所以解得 $$a_n=2^n+2\cdot (-1{)}^n.$$