ｸｲｽﾞ大陸

それでは答えを発表します。

次のように左3列のマスに名前をつけます。
<tt>イニト
ロホチ
ハヘリ</tt>
置き方の総数をA(n)とします。
最後に置くタイルがロの位置になる置き方の総数をB(n)とします。
最後に置くタイルがハの位置になる置き方の総数をC(n)とします。
・最初の3枚をイ、ロ、ハに置く場合、
　残りの領域は3行(n-1)列で、4枚目はヘの位置に置くことになるので、
　置き方の総数はA(n-1)に等しくなります。
・最初の3枚をイ、ロ、ホに置く場合
　最後に置く場所はハ、その前はヘ、その前はリの位置になります。
　4枚目、5枚目の場所はニ、トとなります。
　3列目からn列目の領域はトで始まり、リで終わることになります。
　よって置き方の総数はC(n-2)です。
・最初の2枚をイ、ニに置く場合
　ロ、ハまたはハ、ロと続けて置くことになります。
・・ロが最後のマスの場合
　　その前はハ、その前はヘです。
　　2列目からn列目の領域は最初がニ、最後がヘとなりますので
　　置き方の総数はC(n-1)です。
・・ハが最後のマスの場合
　　その前はロ、その前はホです。
　　2列目からn列目の領域は最初がニ、最後がホとなりますので
　　置き方の総数はB(n-1)です。
・・ホが最後のマスの場合
　　その前はロ、その前はハ、その前はヘです。
　　2列目からn列目の領域に注目すると、
　　最初がニ、最後がホ、その前がヘの置き方と一対一に対応します。
　　これは最初がニ、最後がホの置き方と同数ですので、
　　置き方の総数はB(n-1)です。
・・ヘが最後のマスの場合
　　その前はハ、その前はロ、その前はホです。
　　2列目からn列目の領域に注目すると、
　　最初がニ、最後がヘ、その前がホの置き方と一対一に対応します。
　　3列目からn列目の領域において、最初がト、最後がチの置き方になります。
　　置き方の総数はB(n-2)です。
・・ロ、ハ、ホ、ヘがいずれも最後のマスでない場合
　　途中でホ、ロ、ハ、ヘまたはヘ、ハ、ロ、ホの順に置くことになります。
　　2列目からn列目の領域に注目すると、最初がニで、
　　途中でホ、ヘまたはヘ、ホの順に置く置き方と一対一に対応します。
　　これはニで始まる置き方からヘまたはホで終わるものを除いたものです。
　　よって置き方の総数はA(n-1)-B(n-1)-C(n-1)

A(n)=2A(n-1)+B(n-1)+B(n-2)+C(n-2)です。