問題
，を自然数とする．右の図のような南北m，東西mの長方形の部屋に2辺が2m，3mの長方形の板をすきまなく，また，板が互いに重なりあうことのないように敷き詰めたい．次の各場合に，板の敷き詰め方の総数を求めよ．
(1) ，のとき．
(2) ，のとき．
(3) ，のとき．
出典：九州大学 1995年度 前期日程 第2次学力試験 文系 第4問
方針
板を または の格子長方形として扱う。高さ6の場合は左端が幅2で閉じる配置と幅3で閉じる配置に限られ、 になる。高さ8の場合は幅3ごとの切り口に現れるはみ出し状態を6種類に分け、1ブロック進める遷移表で閉じた状態の数を数える。
解答
(1)
まず南北 m、東西 m の長方形の敷き詰め方の総数を とする。左端に注目する。
左端を含む板の置き方は、次の2種類しかない。 または である。したがって が成り立つ。
初期値は である。よって となる。したがって のときは 通りである。
(2)
同じ漸化式を まで用いる。
したがって のときは 通りである。
(3)
南北 m、東西 m の場合は、高さ6の場合のように左端だけでは閉じない配置がある。そこで幅3mごとの切り口で状態を分ける。
切り口の右側へ板がはみ出していない状態を とする。また、切り口の右側1列または2列に、上から6マス、下から6マス、上下3マスずつがすでにふさがっている状態をそれぞれ区別して、全部で次の6状態を考える。 ここで が閉じた状態である。幅3m分をさらに敷き詰めるときの遷移は、直接並べて調べると
である。表の各行は、左の状態から幅3m分を敷いた後に上の状態へ移る通り数を表す。
最初は閉じた状態 が1通りである。幅3m、6m、9mまで進めたときの各状態の通り数は
である。求めるのは幅9mで閉じた状態 の数なので 通りである。