HAJD 先頭車両から順に1からnまでの番号の付いた n両編成の列車がある。ただし、 練習 ⑨ 17 n ≧2 とする。 各車両を赤色, 青色 黄色のいずれか1色で塗るとき, 隣り合った (4) 2つの車両の少なくとも一方が赤色となるような色の塗り方の数をf(n) とする。 (1) f(2), f(3) を求めよ。 (2) f(n+2)=f(n+1)+2f(n) が成り立つことを示せ。 [類 京都大] Op.322 EX14

1 D E Eの4つの 合うDから | とあるから, を使わないで ことも考える。 領域を2色 ことはでき c, d とす (1) 車両を赤色で塗ることをR, 青色で塗ることをB, 黄色で塗←樹形図をかくときには, ることをで表す。 n=2のとき, 塗り方は ® B ® f(2)=5 よって また, n=3のとき, 塗り方は、 ® ® R (B) [1], [2] から (B) Y B-R R BRB Y ® (B) R -C) このように記述を簡略化 する工夫も有効。 f(2)=32-225 として求めて ←先頭車両が® のとき 2,3両目の塗り方は, 2の場合と同じ。 よって f(3)=11 (2) (+2)両を塗る場合を考える。 [1] 先頭車両を赤色で塗る場合 残りの (n+1) 両の色の塗り方は f(n+1) 通り [2] 先頭車両を青色または黄色で塗る場合 このとき 2両目は赤色で塗る。 残りのn両の塗り方はf(n) 通りあるから、全部ではのう 2f(n) 通り [類 京都大〕 [1] [ [2] B (Y) f(n+2)=f(n+1)+2f(n)=sxa (n+2) 両 00. O f(n+1) 通り ®O ****** f(n)通り