Question

ゆうなぎ

漸化式と場合の数の問題です。
（1）なのですが解説を見ても理解できなかったので教えてくださると嬉しいです。

75
場合の数と漸化式 (1)
3つの文字a,b,cを繰り返しを許して,左から順にn個並べる.ただ
し, αの次は必ずcであり,bの次も必ずcである. このような規則を満た
す列の総数をπn とする.例えば, x1 =3, π2=5 である.
(1)x+2 +1 と In で表せ.
(2)yn=In+1+mm とおく. yn を求めよ.
(3) x を求めよ.
(一橋大)

② 最初がc のとき, その後は a,
まり,同じルールでn+1個並ぶので In+1 通
り
これらを加えたものが, In+2 となるので,
In+2=Xn+1 +2.3Cn
が成り立ちます. このように樹形図をかいていくと,
a,b,c から始まる個数だけが異なる入れ子
が見えてきます.この入れ子の部分を In とおいて樹 入れ子はかっこ良くいうと
形図を省略して表したものが漸化式です.
場合の数で漸化式を利用する場合は
最初の一手で場合分け!
するとよいことが多いです. いわば、 「未来の樹形図
の省略」です.
ちょっと
一言
ロシアの木製の人形マトリョーシカは知
っていますか.胴体の部分で上下に分割
でき、中には少し小さい人形が入ってお
り,これが何回か繰り返され,人形の中からまた人形
が出てくる入れ子構造になっています. こんなイメー
ジがあると上の構造がわかりやすいかもしれませんね.
解答
(1) 題意を満たす n+2個の文字列において,
1番左がα 6のときは,次がc, その後は a, b,
cから始まるn個の列となるから,それぞれxn 通
り1番左がcのときは, その後は a b c から
始まる n+1個の列となるから, In+1 通りある. し
たがって, 求める漸化式は
In+2=xn+1+23C (n≧1)
(2)yn=In+1+x (n≧1) とおくと
In+2=xn+1+2x より
①
In+2+In+1=2(In+1+xn) ∴.yn+1=2yn
=3, x2=5より, y=x+x2=8
..yn=y1・2"-1=8・2"-1=2+2
「自己同形」.
◆yn は公比2の等比数列.

場合の数 漸化式

Answer 1

✨ ベストアンサー ✨

希

(n+2)個a,b,cを規則に従って並べます。次の2通りで場合分けをします。
(i)最初がaまたはbのとき
(ii)最初がcのとき

(i)最初がaまたはbのとき、次に来る文字はcで確定します。よって(n+2)個の文字列は
a c ○ ○ ･･･ ○
または
b c ○ ○ ･･･ ○
という形をしています。それぞれ2個並べれているので、残りはn個です。3文字目はa,b,cのどれが来てもいいので、残りのn個は規則に従っていればどんな並べ方でもいいです。よって、残りのn個の並べ方の総数はx_nに等しいです。最初がaかbかの2通りあるのでこの場合の総数は2x_nとなります。

(ii)最初がcのとき、次に来る文字はa,b,cのどれでもよいです。よって、残りの(n+1)個の文字は規則に従っていればどんな並べ方でもいいです。なので、残りの(n+1)個の並べ方の総数はx_{n+2}となります。

(i),(ii)より(n+2)個並べる総数x_{n+2}は
x_{n+2} = x_{n+1} + 2x_n
となります。

ゆうなぎ

腑に落ちました！ありがとうございます