４項間漸化式

質問

ふとした拍子で、次のような漸化式が出てきてしまいました。

ことの発端はこの問題です。
「ｎ枚の硬貨を１列に並べるとき、表が３枚以上続かない場合の数を求めよ。」

ｎ＝１のとき　２通り

ｎ＝２のとき　４通り

ｎ＝３のとき　７通り(○○○を除く)

ｎ＝４のとき
１回目が×だと残りの樹形図はｎ＝３と同じ。
○×××
││└○
│└○×
│　└○
└○××
　　└○　さらにこの樹形図が加わるので、全部で１３通り

これを眺めていると、
○×で始まるときは残りはｎ＝２のときと同じなので４通り
○○×で始まるときは残りはｎ＝１のときと同じなので２通り。
つまり、４番目は、以前の３つの和であることが推測されます。

これを踏まえたうえでｎ＝５を考えると、
１枚目が×のときは残りの樹形図はｎ＝４のときと同じはず。
○×となったときは残りの樹形図はｎ＝３のときと同じはず。
○○×となったときは残りの樹形図はｎ＝２のときと同じはず。
ですよね。

Ｑ１　まず、この推測が正しいかどうかがわかりません。

正しいと仮定して続けさせていただきます。
ｎ枚の硬貨を並べるとき、表が３枚以上続かない場合の数をA(n)とすると、
A(n+3)＝A(n+2)+A(n+1)+A(n) という４項間漸化式が出てきてしまいます。

Ｑ２　３つだったらフィボナッチなのですが、これは何か名前があるのでしょうか？もう、誰かが解いていますか？
一応途中まで頑張っているのですが字数の関係で表現できません。よろしくお願いします。

回答No.2

motsuan

ごめんなさい私が理解していないようでした。
masuo_kunさんがご指摘のように
> ですが、○×だけではなく、××も加えないといけないですよね。
に関して、私の理解がまちがっていたようで、
その１つ前の樹形図に含まれるのですね。

私の計算の漸化式から（両辺に2^nを掛けて）
　a(n)=2*a(n-1)-a(n-4)
つまり、
　a(n)-a(n-1)=a(n-1)-a(n-4)
となり確かにmasuo_kunさんのものと一致しますね
（チェックしていませんでした。ごめんなさい）。
（p=1/2の場合のｋが一般の場合は、
　a(n)=2*a(n-1)-a(n-k-1)
　a(n)-a(n-1) =a(n-1)-a(n-k-1)
　でこれもmasuo_kunさんのものに一致しますね。
)。
これの一般項は求められるかというのが問題意識なのでしょうか？
う～ん。難しいですね。考えてみます。

式の中の符号もひとつ間違っていました。
P(n,k)=P(n-1,k)+(1-P(n-k-1,k))*(1-p)*p^k
でした。

以上、とりあえずお詫びでした。

お礼

こんな難問のためにお時間頂いてしまって恐縮です。
本当にお手数おかけいたします。・・・

Ｑ１については、一致したようで、私の考えに誤りはないことが確認できました。
ありがとうございます。

この漸化式、もしかしたら角の３等分線をコンパスと定規で作るのと同じような、
解けないものの一種ではないかとも思い始めているので、
「解けない」ということならそれでも構わないのです。
これを「４連続」と差し替えると、
A(n+5)=A(n+4)+A(n+3)+A(n+2)+A(n+1)+A(n)
という５項間漸化式になるらしいので、
始まるときりがないんですよ。この話・・・