19767：a,b,cを並べるとき,cが並ばない確率...

問題19767・・・http://officeklu.s502.xrea.com/2014mondai/ より引用 Orz～

解答

・わたしの...

(1)

3文字を並べたとき、どの文字も連続するような並びを含む確率は1/3

どの文字も連続しない並び...3*2^(n-1)

so...

P(n)

={3*2^(n-1)+(3^n-3*2^(n-1))/3}/3^n

=(3^(n-1)+2^n)/3^n

=1/3+(2/3)^n

(2)

8番目...(a,b)

9番目...((a,b,c),(a,b,c))

so...10番目...4通り

so...

10番目がcにならない場合...4*3+2*2=16

so...

4/16=1/4

でいいのかな ^^

↑

ダメでした ^^; Orz...

↓

・鍵コメT様からのもの Orz～

書かれている結論は明らかに誤りだと思います．
例えば，P(10000)とは，
「a,b,cから重複を許して10000個並べる並べ方3^10000通りのうち，
文字cが連続しないものの割合」であり，
10000個も文字を並べれば，ほぼ確実に「cc」という文字列を含むことから，
P(10000)は0に近い値であるはずで，
1/3+(2/3)^10000になるはずはありません．・・・確かに ^^;

(1)「a,b,cを重複を許してn文字並べた文字列でcが連続しないもの」
のうち，「…a」または「…b」の個数をx[n]，「…c」の個数をy[n]とする．

まず，x[1]=2 (「a」と「b」)，y[1]=1 (「c」)．

「…c」は，「…a」や「…b」の末尾にcを付けたときだけ得られるので，
y[n+1]=x[n].
「…a」や「…b」は，「…a」,「…b」,「…c」の末尾にaかbを付けて
得られるので，x[n+1]=2x[n]+2y[n].

以上より，y[2]=x[1]=2であり，
y[n+2]=x[n+1]=2x[n]+2y[n]=2y[n+1]+2y[n]…[*]．

α=1-√3,β=1+√3として，[*]は・・・特性方程式...y^2-2y=2...y=1±√3 から求めるのですね ^^;
y[n+2]-αy[n+1]=β(y[n+1]-αy[n]),y[n+2]-βy[n+1]=α(y[n+1]-βy[n])
と変形できて，
y[n+1]-αy[n]=(y[2]-αy[1])β^(n-1)=(2-α)β^(n-1)=β^n,
y[n+1]-βy[n]=(y[2]-βy[1])α^(n-1)=(2-β)α^(n-1)=α^n.
辺々引いて，(β-α)y[n]=β^n-α^nとなり，y[n]=(β^n-α^n)/(2√3).
x[n]=y[n+1]であり，
P(n)=(x[n]+y[n])/(3^n)
=(β^(n+1)-α^(n+1)+β^n-α^n)/(2√3*3^n)
=(2+√3)(1+√3)^n-(2-√3)(1-√3)^n)/(2√3*3^n).

(2) 7番目がcである文字列の個数は，
・6番目までの文字列がx[6]通り
・8番目からの文字列は，逆順にしたときに最後がaかbとなるからx[n-7]通り
で，x[6]*x[n-7]通りある．

そのうち，10番目もcである文字列は，
・6番目までの文字列がx[6]通り
・8,9番目は「aa」「ab」「ba」「bb」のいずれかで4通り
・11番目からの文字列はx[n-10]通り
で，x[6]*4*x[n-10]通りだから，
Q(n)=(x[6]*4*x[n-10])/(x[6]*x[n-7])
=4x[n-10]/x[n-7].
n→∞のとき，((1-√3)^n)/((1+√3)^n)は0に収束するから，
求める極限は，4/(1+√3)^3=4/(6√3+10)=3√3-5.

*熟読玩味ぃ～^^;v