４項間漸化式

質問

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

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

ｎ＝１のとき　２通り

ｎ＝２のとき　４通り

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

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

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

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

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

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

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

回答No.1

motsuan

Q1について、一般的漸化式を示します。
n個並べたときに、1回あたりの出現確率が ｐ の「あるもの」が
k個以上連続している確率 P(n,k)をもとめます。
n-1個並べたときに「あるもの」が k 個以上連続している場合と、
そうでない場合いに n 個目に「あるもの」を１つ付け加えて初めて
k 個連続したものができる場合の和で表されると思います。
前者は
（０）　n 個目につけ加えるものはなんでもいいので P(n-k,k-1)、
後者は
（１）　最初の n-k-1 個には n 個以上連続したものがなく（1-P(n-k-1,k)）、かつ
（２）　n-k個目は「あるもの」ではなく（1-p）、かつ
（３）　残りの k 個はすべて「あるもの」（p^k）
となるので、
　P(n,k)=P(n-1,k)-(1-P(n-k-1,k))*(1-p)*p^k (但し、n>k+1)。
結局、求めるk個以上続かない確率Q(n,k)はQ(n,k)=1-P(n,k)として
　Q(n,k)=Q(n-1,k)-Q(n-k-1,k)*(1-p)*p^k (但し、n>k+1)
となるのではないでしょうか？
したがって、これに全体の場合の数をかければ
求める場合の数が得られるはずです。（いまの場合、p=1/2, k=3）

> これを踏まえたうえでｎ＝５を考えると、
> １枚目が×のときは残りの樹形図はｎ＝４のときと同じはず。
> ○×となったときは残りの樹形図はｎ＝３のときと同じはず。
>　　　　　　　　 ：
ですが、○×だけではなく、××も加えないといけないですよね。
そして、どんどんｎが大きくなったとき、たとえばｎ＝６
○○○？？？
のような場合ははずさないといけないですよね。
というわけで、ちょっとややこしい漸化式になってしまうと思います。

お礼

ご丁寧な回答、ありがとうございます。

Q(n,k)=Q(n-1,k)-Q(n-k-1,k)*(1-p)*p^k

これも考えました！でも、結局k=3で具体的に解くとなると、
A(n)=A(n-1)-A(n-3)*(1-p)*p^3 となるのですよね。
ｎをずらすと、
A(n+3)=A(n+2)-A(n)*(1-p)*p^3
結局４項間漸化式のような気がします・・・
この形を強引に解くでも良いのですが。。。。

あと、一番最後のことですが、きっと私の表現が悪かったのだと思います。
「○×となったとき」というのは、「○×で始まる場合」
「○○×となったとき」というのは、「○○×で始まる場合」
という意味でした。表現に誤解を招く部分があり申し訳ありません。
樹形図を実際に書いてみると、私の意図は伝わると思います。
この方法なら○○○で始まる場合はもちろん条件を満たさないので数えていません。

なお、私の方法では、3枚ではなくｋ枚のときは、
a(n)=2^n (1≦n≦k-1)
a(k)=2^k-1　という初期条件で、n≧1+kのときは
a(n)=S(n-1)-S(n-k-1) ただし、S(n)は初項から第ｎ項までの和で、S(0)=0
という漸化式に従いそうなんです。
ここまでは分かっているのですが、字数上限に阻まれてしまいました（笑）

そもそも、この問題,漸化式を解くことには意味がないのでしょうか・・・
Ｑ１は分からないけどＱ２は知っているという方のご意見もお待ちしています。
（このままやると変な３次方程式が出てきて、計算が爆発します）