例題 307
漸化式と場合の数
先頭車両から順に1からnまでの番号のついた両編成の列車がある。
ただし n ≧2 とする. 各車両を赤色、青色,黄色のいずれか1色で塗ると
き、隣り合った車両の少なくとも一方が赤色となるような色の塗り方は何
通りか.
(京都大)
考え方
まずは具体例で考える.
n=2のとき, (2両の塗り方)
2両目が赤のとき, 1両目は赤, 青, 黄のいずれでもよい。
2両目が青, 黄のとき, 1両目は赤でなければならない.
一般には, n両目を考え,それが赤か, 赤以外かで場合分けして考える.
解答 条件を満たす両の車両の塗り方の数をan, そのうち最後
尾の車両が赤である塗り方の数を6n, 最後尾の車両が赤以外
である塗り方の数を cm とする.
n=2 の場合, a2=5, b2=3,C2=2
また,
an=bn+cn ......①
ここで,(n+1) 両目について考える.
(n+1) 両目が赤のとき、両目は赤, 青, 黄のいずれでも
bn+1=bn+Cn
「よいので,
一方,(n+1) 両目が青, 黄いずれかのとき, n両目は赤で
なければならないので,
Cn+1=26n
ここで, b=1,C1 = 2 とすると, ②, ③ は n=1のときも
成り立つので, n ≧1 として考える.
②③より
bn+2=bn+1+2bn
bn+2-2bn+1=-(bn+1-2bn)
これより
・④
bn+2+bn+1=2(bn+1+bn) I\ ･⑤
④より、数列{bn+1-26m} は初項 62-261=3-2=1,
公比 -1の等比数列だから,
****
bn+1-26=1・(-1)^-1=(-1)^-1
⑥6⑥
⑤より, 数列{bn+1+bn} は初項b2+b=3+1=4,
公比2の等比数列だから,
bn+1+b=4・2-1=2n+1
⑥⑦ より, -36=(-1)-1-2n+1,6n= 1 -{2n+1+(-1)"}
3
③より, n≧2のとき
Flo
FM
Cn=267-1=2.1/13(2"+(-1)^-1=1/12 (21" +1-2 (-1)^}
よって, ①より, an=1/12 (2+2(-1)^) (通り)(n≧2)
最後尾の車両の色に
注目して考える.
1両目
2両目
青
青
黄
赤
赤
n両目 (n+1) 両目
赤}6 赤
7 bn+1-2bn
C2
赤+1
Cn
赤}6 青
赤}6 黄
x2=x+2より
(x-2)(x+1)=0
x=2, -1
n≧2で考えると,
b3-262 に対して、
=(3+2)-2・3=-1
Cn+1
=-1(-1)-2
=(-1)^-1
|--(-1)^-1=(-1)"
