４項間漸化式

Question

ふとした拍子で、次のような漸化式が出てきてしまいました。

ことの発端はこの問題です。
「ｎ枚の硬貨を１列に並べるとき、表が３枚以上続かない場合の数を求めよ。」

ｎ＝１のとき　２通り

ｎ＝２のとき　４通り

ｎ＝３のとき　７通り(○○○を除く)

ｎ＝４のとき
１回目が×だと残りの樹形図はｎ＝３と同じ。
○×××
││└○
│└○×
│　└○
└○××
　　└○　さらにこの樹形図が加わるので、全部で１３通り

これを眺めていると、
○×で始まるときは残りはｎ＝２のときと同じなので４通り
○○×で始まるときは残りはｎ＝１のときと同じなので２通り。
つまり、４番目は、以前の３つの和であることが推測されます。

これを踏まえたうえでｎ＝５を考えると、
１枚目が×のときは残りの樹形図はｎ＝４のときと同じはず。
○×となったときは残りの樹形図はｎ＝３のときと同じはず。
○○×となったときは残りの樹形図はｎ＝２のときと同じはず。
ですよね。

Ｑ１　まず、この推測が正しいかどうかがわかりません。

正しいと仮定して続けさせていただきます。
ｎ枚の硬貨を並べるとき、表が３枚以上続かない場合の数をA(n)とすると、
A(n+3)＝A(n+2)+A(n+1)+A(n) という４項間漸化式が出てきてしまいます。

Ｑ２　３つだったらフィボナッチなのですが、これは何か名前があるのでしょうか？もう、誰かが解いていますか？
一応途中まで頑張っているのですが字数の関係で表現できません。よろしくお願いします。

stomachman · Accepted Answer

綺麗な漸化式ができましたねえ。2連続と考えればフィボナッチ数列の解釈になる。一般にj連続と考えることで一群の漸化式が出てくる。これだけで素敵な成果じゃないですか。
　数列の一般項を求めても、それが難しい関数や総和を含んでいるようでは、漸化式で計算したほうがましだったりしないとも限りません。
　余談ながら比　x=A(N)/A(N-1)がN→∞において収束するとすれば、
   x^3-x^2-x-1=0
という方程式の実数解ですから、
　x=(19/27-√(11/27))^(1/3)+(19/27+√(11/27))^(1/3)-1/3
なんてことになります。

　では、ちょいと観点を変えてみましょう。
A:「裏ばかりの硬貨が一列に並んでいる。その個数（は幾つでも良いがこれ）をMとする。その隙間、あるいは列の先頭や末尾に、適当に表の硬貨を挿入して行く。ただし、各挿入箇所に挿入する表の硬貨の数は０か１か２でなくてはならない。表の硬貨を挿入できる箇所はM+1箇所ある。挿入した表の硬貨の総数をKとすると、N=M+Kが列全体の長さである。Nを固定したとき、場合の数A(N)を求めよ。」これは元もとの問題を別の言い方で表してます。
　Nを固定して考えると、0≦K≦2(M+1)ですから、
(1) 0≦K≦(2N+2)/3
でなくてはなりません。
　さて、NとKが与えられたとします。するとK個の表の硬貨をいかにしてM+1個の挿入箇所に配分するかという問題です。すなわち
B(N,K):「K個の(表の)硬貨をM+1=N-K+1人で分ける。ただし一人最大２個しか貰えない。場合の数を求めよ」
を考えることができる。その解B(N,K)をK=0,1,....,floor[(2N+2)/3] について加えたものがA(N)になります。
A(N) = B(N,0)+ B(N,1) + ...... + B(N,floor[(2N+2)/3] )
 この問題B(N,K)は、さらに次の問題に帰着できます。
C(N,K,h):「N-K+1人の中から、硬貨２つを貰えるヒトh人を選ぶ。残りのN-K+1-h人の中から硬貨１つを貰えるヒト(K-2h)人を選ぶ。場合の数を求めよ。ただし2h≦Kである。」
すなわち
B(N,K) = C(N,K,0)+C(N,K,1)+.....+C(N,K,floor[K/2])
ですね。

ここで、問題c(n,j):「n人のうちからj人を選ぶ場合の数を求めよ」
を考えますと、ご承知の通り、
・j>nの場合にはc(n,j)=0
・0≦j≦nの場合にはc(n,j)= n! / (n-j)!/j!
ということになる。だから
C(N,K,h) = c(N-K+1,h)c(N-K+1-h,(K-2h))
である。
かくて、二重の総和を使って無理矢理ながら元の問題の解が表せることまでは分かりました。それが具体的に綺麗な式に整理できるかどうかがポイントですが.....
これで、おしまい。無責任だなあ。

motsuan · Answer

ごめんなさい私が理解していないようでした。
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 
でした。

以上、とりあえずお詫びでした。

motsuan · Answer

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

４項間漸化式

綺麗な漸化式ができましたねえ。

ごめんなさい私が理解していないようでした。

Q1について、一般的漸化式を示します。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング