問題5230(某サイト問のプレリュード ^^;)
a,bの2種類のものを10個並べるとき、bが2個以上連続している場合の数を求めよ。
解答
・わたしの
1個以下しか連続していない場合を考える...
0-(0,1)-((0,1),0)-((0,1),0),(0,1))-
と...フィボナッチ数列になってる ^^
1-2-3-5-8-13-21-34-55-89
つまり...F(11)
1-0-(0,1)-...と一つずれたフィボナッチ...
1-1-2-3-5-8-13-21-34-55
つまり...F(10)
けっきょく...
k個までに1個以下しか連続しない場合は...F(k+1)+F(k)=F(k+2)
ここから思考停止...^^;
再考...
11で始まる場合の数:f(k)
0で始まる場合の数:g(k)
g(k)=f(k-1)+f(k-2)+...+f(2)
f(10)+g(10)=f(10)+f(9)+...+f(2)
f(2)=1, f(3)={111,110}=2, f(4)={1111,1110,1100}=3
f(5)={11111,11110,11100,11000,11011}=5
f(6)={111111,111110,111100,111000,110000,110011, 111011, 110111}=8
になってる...^^;
おそらく...←いい加減ある...^^;...ここの上手い証明がわからない...
f(7)=13, f(8)=21, f(9)=34, f(10)=55
けっきょく...
f(10)+g(10)=2*55=110 通り
でいいのかなぁ...?
↑
間違ってましたぁ...^^;...Orz〜
以下は、ご指摘いただきました鍵コメさまの見事な解法です☆
グラッチェです〜m(_ _)m〜
↓
問題がちょっとあいまいな気がします.
1(問題文ではb,表題と解答では1)が連続するところが1箇所でもあればよいのか,
登場する1はすべて,2つ以上続いていないとだめなのか.
後者のつもりでしたぁ...^^;...Orz〜
後者だとして,解答ですが,f(6) のところで,110110が漏れています.←ほんに...^^;;
f(6)=9であり,「fがフィボナッチ」は不成立です.
11ではじまるものf(n)通りを,
111ではじまるもの(先頭の1を除いて考え,f(n-1)通り)と
110ではじまるもの(先頭の11を除いて考え,g(n-2)+1通り)
に分類し,
0ではじまるものg(n)通りを,先頭の0を除いて考えることで,
f(n)=f(n-1)+g(n-2)+1,g(n)=f(n-1)+g(n-1)
を得ます.
これを用いて,
f(2)=1,g(2)=0,f(3)=2,g(3)=1から順次,
f(4)=3,g(4)=3,
f(5)=5,g(5)=6,
f(6)=9,g(6)=11,
f(7)=16,g(7)=20,
f(8)=28,g(8)=36,
f(9)=49,g(9)=64,
f(10)=86,g(10)=113
となり,求める個数は,
f(10)+g(10)=199
となると思います.