ｸｲｽﾞ大陸

<tt>イニト
ロホチ
ハヘリ</tt>
B(n)について
最後がロということはその前はハ、その前はヘです。
2列目の領域に注目すると、ニで始まりヘで終わりますので、
B(n)=C(n-1)です。

C(n)について
最初がイ、最後はハです。
イの次がロの場合、続けてホ、ニ、トの順になります。
3列目からn列目の領域では最初がト、最後がリとなりますので、総数はC(n-2)
イの次がニの場合、ハの前はロ、その前はホです。
2列目からn列目の領域では最初がニ、最後がホとなりますので、総数はB(n-1)
よって、C(n)=C(n-2)+B(n-1)です。
B(n)=C(n-1)でしたので、C(n)=C(n-2)+C(n-2)=2C(n-2)
B(n)=B(n-2)もいえます。
各数列の偶数項のみの部分列、奇数項のみの部分列は公比2の等比数列です。
B(1)=0,C(1)=1より、B(3)=0,C(3)=2
B(2)=C(1)=1,C(2)=B(3)=0
mを2以上の自然数とすると、
B(2m-1)=0,C(2m-1)=2^(m-1)
B(2m)=2^(m-1),C(2m)=0

A(2m-1)=2A(2m-2)+B(2m-2)+B(2m-3)+C(2m-3)=2A(2m-2)+2^(m-2)+2^(m-2)=2A(2m-2)+2^(m-1)
A(2m)=2A(2m-1)+B(2m-1)+B(2m-2)+C(2m-2)=2A(2m-1)+2^(m-2)

従って置き方の総数A(n)は、
A(1)=1
A(2)=3
A(2m-1)=2A(2m-2)+2^(m-1)
A(2m)=2A(2m-1)+2^(m-2)
と計算できます。
A(2m-1)=2A(2m-2)+2^(m-1)=2(2A(2m-3)+2*2^(m-2))+2^(m-1)
代入を繰り返すと、A(2m-1)は2^(m-3)*A(2)と2の冪の和になります。
2の冪については、奇数の項目、偶数の項目はそれぞれ等比数列になっています。
A(3)からA(2m-1)までの奇数の項目の個数は
(2m-1-3)/2+1=m-1
奇数の項の2の冪の合計は
初項2^(m-1)、公比2、項目数(m-1)の等比数列の合計
2^(m-1)*(2^(m-1)-1)=2^(2m-2)-2^(m-1)
A(4)からA(2m-2)までの奇数の項目の個数は
(2m-2-4)/2+1=m-2
偶数の項の2の冪の合計は
初項2^(m-2)、公比2、項目数(m-2)の等比数列の合計
2^(m-2)*(2^(m-2)-1)=2^(2m-4)-2^(m-2)

以上より
A(2m-1)=2^(2m-2)-2^(m-1)+3*2^(2m-3)+2^(2m-4)-2^(m-2)=11*2^(2m-4)-3*2^(m-2)
A(2m)=2(11*2^(2m-4)-3*2^(m-2))+2^(m-2)=11*2^(2m-3)-5*2^(m-2)

答えは、
nが奇数の場合は、11*2^(n-3)-3*2^((n-3)/2)
nが偶数の場合は、11*2^(n-3)-5*2^((n-4)/2)
です。
これをまとめて一つの式にすることも可能ではあります。

11*2^(n-3)-3(1-(-1)^n)*2^((n-5)/2)-5(1+(-1)^n)*2^((n-6)/2)
等とすればよいです。