2群馬大学 2012年 数学 第2問解答・解説

(1) $3\times2$ の盤では、すべて横置きにする場合と、左端に縦置きのタイルを1枚置き残りの1段を横置きにする場合が上下2通りある。よって $a_1=3$。 $3\times4$ の盤では、左端に3枚が接する場合は、最初の2列を3枚の横置きタイルで埋め、その残りの $3\times2$ 盤を敷きつめるので3通り。左端が2枚の場合、縦置きタイルの位置により2通りに分かれる。各場合について、次列の残る2マスを縦置きにすれば残りの $3\times2$ 盤の敷きつめ方が3通り、横置きに張り出す形なら残りが強制されて1通り、合計4通り。したがって $a_2=3+2\cdot4=11$。 (2) 左端に3枚のタイルが接するなら、左端の3マスはすべて横置きタイルで埋まる。これを置いた後は $3\times2n$ の盤が残るから $$a_n=x_n+y_n,\qquad x_{n+1}=a_n=x_n+y_n.$$ 次に、左端が2枚の配置を一つ固定し、その配置後に残る部分の敷きつめ方を $p_n$ とする（もう一つの配置は上下対称で同数）。残り部分で次列の2マスを縦置きにすれば $3\times2n$ の盤が残って $a_n$ 通り。2マスを横置きで次列へ出す場合は他の段も強制的に次列を越えて進み、残りは $p_{n-1}$ と同じ形になる。よって $$p_n=a_n+p_{n-1},\qquad p_0=1.$$ 左端が2枚である配置は上下対称な2種類なので $$y_{n+1}=2p_n=2a_n+2p_{n-1}=2a_n+y_n =2x_n+3y_n.$$ (3) (2)より $a_{n+1}=x_{n+1}+y_{n+1}=3a_n+y_n$ かつ $y_{n+1}=a_{n+1}-a_n$。したがって $$a_{n+2}=3a_{n+1}+y_{n+1}=4a_{n+1}-a_n.$$ $a_1=3,\ a_2=11$ から $a_3=41,\ a_4=4\cdot41-11=153$。

左端に接するタイル数で場合分けして漸化式を作り、総数の二項間漸化式へまとめる。