[例題] 316 場合の数と漸化式
2辺の長さが1と2の長方形と1辺の長さが2の正方形の2種類のタイル
がある。 nを自然数とし, 縦2, 横nの長方形の部屋をこれらのタイルで
過不足なく敷き詰めるときの並べ方の総数を Am で表す。
(1) n ≧3のとき, An を An-1, An-2 を用いて表せ。
(2) Ann を用いて表せ。
思考プロセス
具体的に考える
例題
307
Am
を敷き詰める
最初にをおくと
最初に
最初に
をおくと2
をおくと
An+An-1=2 (An-1+An-2)
--2-
-2--
An-2A-1=-(An-1-2An-2)
3
②より, 数列{An+1 + An} は初項 A2 + A1 = 4,
公比2の等比数列であるから
n
Action» n を含んだ場合の数は,最初の試行で場合に分けよ
解 (1) 左端に長辺を縦にした長方形を並べるとき
残り縦2, 横 (n-1)の部分の並べ方は A-1 通り
(イ) 左端に長辺を横にした長方形を並べるとき
残り縦2, 横 (n-2)の部分の並べ方は A-2 通り
(ウ) 左端に正方形を並べるとき
残り縦2, 横 (n-2)の部分の並べ方は A-2 通り
(ア)~ (ウ)より
An=An-1+2An-2
①
(2) ① を変形すると
A-1
An+1+An=4.2-1 = 2+1
③より, 数列{An+1-2Am} は初項 A2-2A1 = 1,
公比1の等比数列であるから
An+1-2An=1,(-1)"^'=(−1)"-'
④ ⑤ より 3An=2+1-(-1)^-'
よって An = 1/1/12 (2711-(-1)^-1)
n-2
An-2
n-2
An-2
(東京大)
← 斜線部分
も
特性方程式
x2-x-2=0 より
x=-1,2
より A = 1
①日
より Ag = 3
[練習 316 先頭車両から順に1からnまでの番号の付いた両編成の列車がある。 ただ
し≧2 とする。 各車両を赤色, 青色, 黄色のいずれか1色で塗るとき, 隣
り合った車両の少なくとも一方が赤色となるような色の塗り方は何通りか。
(京都大)
p.570 問題316
6
章
18
化式と数学的帰納法
547
