>>857
n個の文字を並べるとき
条件を満たすような並べ方の場合の数をa[n]通りとする
また、どの文字も連続しないような並べ方は4*3^(n-1)通り
ここでどの文字も連続しないように並べられたn個の文字の前後に同じ文字をつけることを考える
・もとのn個の文字列の最初と最後が同じ種類ならそれとは違う文字(3通り)をつければいい
・もとのn個の文字列の最初と最後が異なるならそのいずれとも違う文字(2通り)をつける

従って
a[n+2]=3a[n]+2｛4*3(n-1)-a[n]｝つまり
a[n+2]=a[n]+8*3^(n-1)がなりたつ

また明らかにa[2]=0
故に
a[10]=8*(3+3^3+3^5+3^7)=19860