Question

设正整数，对格点链中的个结点用红（）、黄（）、蓝（）三种颜色染色，左右端点中的三个结点已经染好色，如图。若对剩余的个结点，要求每个结点恰染一种颜色，相邻结点异色，求不同的染色方法数。

Answer

见解析

【解析】

设右端点染色为、，如图2.

图2

记为（或）、为时的染色数为；记为、为（或）时的染色数为；记为、为或为、为时的染色数为.

（1）若右端没有约束时，每增加一个格均有三种不同的染色方法，则.

（2）由对称性，即将图形上下翻转，且颜色与互换，知.

（3）考虑相互的递推特征，如图3，则.

图3

从而，.故，即为问题所求的不同的染色方法数.