質問＜３８６１＞２０１３／９／１４
from=guiter
「確率」

先頭車両から順に１からｎまでの番号ついたｎ両編成の列車がある。
ただしｎ≧２とする
各列車を赤色、黄色、青色のいずれか一色で塗るとき、となりあった車両の少なくとも
一方が赤色となるような塗り方は何通りか？
どうやってもわかりません

★希望★完全解答★

お便り２０１３／９／１６
from=wakky

質問2738にも解答がありますが
さらに詳しく解答してみます

n両編成において、隣り合う車両の少なくとも1方が赤色となるような塗り方を
p(n)通り　とする
そうすると
2両のときは
赤赤、赤青、青赤、赤黄、黄赤　の5通りだから
p(2)=5
3両のときは
赤赤赤、赤赤青、青赤赤、赤青赤、赤赤黄、黄赤赤、赤黄赤、青赤青、黄赤青、青赤黄、黄赤黄
の11通りだから
p(3)=11
n≧4のとき
（あ）1両目が赤ならば
　　　　残りn-1両の塗り方はp(n-1)
（い）1両目が青ならば
　　　　2両目は必ず赤でなければならない
　　　　3両目以降の残りn-2両の塗り方はp(n-2)通り
　　　これは1両目が黄のときも同じ
（あ）（い）より
漸化式
p(n)=p(n-1)+2p(n-2)・・・①　（n≧4)　を得る
p(n)-ap(n-1)=b{p(n-1)-ap(n-2)}・・・②
とおくと
p(n)=(a+b)p(n)-abp(n-1)
これと①を比較すると
a+b=1,ab=-2
二次方程式の解と係数の関係から
a,bはtに関する二次方程式
t^2-t-2=0（いわゆる特性方程式）の2解
(t+1)(t-2)=0より
t=-1,2
a=-1,b=2のとき
②より
p(n)+p(n-1)=2{p(n-1)+p(n-2)}
=2^(n-3){P(3)+p(2)}
=2^(n-3)・16
=2^(n+1)・・・③
a=2,b=-1のとき
p(n)-2p(n-1)=-{p(n-1)-2p(n-2)}
=(-1)^(n-3){P(3)-2p(2)}
=(-1)^(n-3)(11-10)
=(-1)^(n-3)・・・④
③-④より
3p(n-1)=2^(n+1)-(-1)^(n-3)
p(n-1)=(1/3){2^(n+1)-(-1)^(n-3)}
したがって
p(n)=(1/3){2^(n+2)-(-1)^(n-2)}
これは
n=2,3の場合も成り立つ
以上から
求める色の塗り方は
(1/3){2^(n+2)-(-1)^(n-2)}通り・・・（答）