例題
316 場合の数と漸化式 【
2辺の長さが1と2の長方形と1辺の長さが2の正方形の2種類のタイル
がある。 n を自然数とし, 縦2, 横nの長方形の部屋をこれらのタイルで
過不足なく敷き詰めるときの並べ方の総数を An で表す。
(1)n≧3のとき, A を A-1, A-2 を用いて表せ。
(2) Annを用いて表せ。
具体的に考える
(東京大)
思考プロセス
最初に
をおくと
An
最初に
をおくと2
An-1
-n-2-oils.
An-2
◆ 斜線部分
も
を敷き詰める
-2--
n-2-
最初に
をおくと。
2
An-2
Action n を含んだ場合の数は,最初の試行で場合に分けよ
(1) (ア) 左端に長辺を縦にした長方形を並べるとき
残り縦2, 横(n-1) の部分の並べ方は
(イ) 左端に長辺を横にした長方形を並べるとき
残り縦2, 横 (n-2) の部分の並べ方は
A通り
1
2通り
(ウ)左端に正方形を並べるとき
残り縦2,横(-2) の部分の並べ方は2通り
--2-
-n-2-
BU
307
(ア)~(ウ)より An=An-1+2An-2
①
2 ①を変形すると
An+An-1=2(An-1+An-2)
2.
n-2--
特性方程式
An-2An-1=-(An-1-2 An-2)
③
②より、数列{An+1 + An} は初項 A2+ A1 = 4,
公比2の等比数列であるから
An+1+An=4.2"-1 = 2n+1
④
③より、数列{An+1-2An} は初項 A2-2A1=1,
公比-1の等比数列であるから
④ ⑤
An+1-2An=1(−1)"-1=(-1)"-1
An
==
3An=2+1-(-1)"-18
3
{2n+1-(-1)-1}
|x2-x-2=0より
x=-1,2
より A1 = 1
080
よりA2 = 3
⑤