设正整数n≥2，对2×n格点链中的2n个结点用红（R）、黄（Y）、蓝（B）三种颜色染色，左右端点中的三个结点己经染好色，如图所示．若对剩余的2n-3个结点，要求每个结点恰染-种颜色，相邻

Question

设正整数n≥2，对2×n格点链中的2n个结点用红（R）、黄（Y）、蓝（B）三种颜色染色，左右端点中的三个结点己经染好色，如图所示．若对剩余的2n-3个结点，要求每个结点恰染-种颜色，相邻结点异色，求不同的染色方法数

Answer 1

2×n格点链中的2n个结点用红（R）、黄（Y）、蓝（B）三种颜色染色，其中最左端点染成红色与黄色，设右端点染色为P，Q，如图所示：

记P=R（或Y），Q=B时的着色数目为a_n，
记P=B，Q=R（或Y）时的着色数目为b_n，
记P=R，Q=Y或者P=Y，Q=R时的着色数目为c_n，
我们注意到：（1）若右端没有约束时，每增加一个格子都有3种不同的着色方法，则a_n+b_n+c_n=3^n-1，
（2）由对称性，即将图形山下翻转，并且颜色R与Y互换，可知a_n=b_n，
（3）考虑相互的递推特征，如图：则a_n=2b_n-1+c_n-1，

所以，

an+bn+cn=3n-1

an=bn

an=2bn-1+cn-1

，n∈N*
这样a_n=2b_n-1+c_n-1=a_n-1+b_n-1+c_n-1=3^n-2，
即为问题所求的不同的染色方法数．