有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格排序的公式是怎样的,可以用递推表示

Question

有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格
排序的公式是怎样的,可以用递推表示

Answer 1

当n=2时,很显然有6种
那么当S1涂3种后,那么S2至Sn-1都有2种选择的颜色
当到了Sn时,分2种：第一种Sn和S1不同,我们假定方法数是an,还有一种是Sn和S1相同这样就是Sn与S1合并成了一起,实际上是Sn-1的涂法,我们假定方法数是an-1
那么a2=6；an+an-1=3*2^(n-1)
根据数列可以得到an=2(2^(n-1)+(-1)^(n-2))种