2文字A,\ Bを用いて,\ Bが連続しないように文字列を作成する.
(1)\ \ 文字が2個,\ 3個,\ 4個の列はそれぞれ何通りあるか.
(2)\ \ 文字$n$個の列の総数を$a_n$とするとき,\ $a_{n+2}$を$a_{n+1}$と$a_n$を用いて表せ.
(3)\ \ 左端の文字がBである文字$n$個の列の総数を$b_n$とするとき,
$b_{n+2}$を$b_{n+1}$と$b_n$を用いて表せ. \\場合の数の漸化式
4個程度の列までならばすべて書き出すことが可能である.
計算で求めたければ,\ AとBを何個ずつ使うかで場合分け}することになる(別解).
隣り合わない並べ方は,\ それ以外のものを並べた後に両端または間に入れる}のであった.
A\,3個,\ B\,1個}ならば,\ ○A○A○A○}の4つの○から1つ選んで Bを1個入れればよい.
(2)\ \ 文字$n+2$個の列には,\ 左端がAの列と左端がBの列がある.
[1]\ \ \.{左}端がA}の$n+2$個の列の数は,\ 残りの$n+1$個の列の数に等しく} $a_{n+1$通り
[2]\ \ \.{左}端がB}の$n+2$個の列の数は,\ BAの後の$n$個の列の数に等しく} $a_n}$通り
[1],\ [2]\,は互いに排反であるから $a_{n+2}=a_{n+1}+a_n}$}
文字$n+2$個の列には,\ 右端がAの列と右端がBの列がある.
[1]\ \ \.{右}端がA}の$n+2$個の列の数は,\ 残りの$n+1$個の列の数に等しく} $a_{n+1$通り
[2]\ \ \.{右}端がB}の$n+2$個の列の数は,\ ABの前の$n$個の列の数に等しく} $a_n}$通り
[1],\ [2]\,は互いに排反であるから $a_{n+2}=a_{n+1}+a_n}$}
(1)ですべて書き出すときに本質的構造に気付けたならば,\ n個の場合にまで一般化できる.
文字2個の列の総数3通りと文字3個の5通りが既知であるとし,\ 文字4個の列の総数を考える.
文字4個の列を書き出すとき,\ まずは左端が Aの場合を書き出すだろう.
後は残りの文字3個の列が何通りあるかを考えればよいわけだが,\ すべて書き出す必要はない.
文字3個の列が5通りあることは既知だからである.
次に左端が Bの場合,\ 2番目は必ず Aなので,\ 残りの文字2個の列が何通りあるかに帰着する.
文字2個の列が3通りあることは既知なので,\ 結局文字4個の列の総数は5+3=8通りとなる.
同様に考えると,\ 文字n+2個の列は\
A}\,[\,文字n+1個の列\,] & a_{n+1}\,通り
BA}\,[\,文字n個の列\,] & a_n\,通り
よって,\ a_{n+2}=a_{n+1}+a_n\,が成り立つわけである.
このように,\ n,\ n+1,\ n+2番目の項の関係を表した式を漸化式}(数 B:数列)という.
重要なのは,\ a_{n+1},\ a_n\,の値が不明でもa_{n+2}\,との間に成り立つ関係ならば立式できる}ことである.
そして,\ この漸化式を解けば,\ 一般項a_n\,を求めることができる(要数 B:数列).
不明のものを一旦xとおいて方程式を作成し,\ それを解いてxの値を求めるようなものである.
漸化式の作成は,\ 直接的にa_n\,を求めることが困難な問題に対して強力な武器となる.
特に,\ 単純な規則に従ってn個まで段階的に増やしていく問題では漸化式の作成が有効である.}
漸化式を利用する問題は,\ 場合の数と数列の理解度を同時に問えるため,\ 難関大学でよく出題される.
ただし,\ 実際の入試では漸化式の問題であることがわかるように出題されるとは限らない.
単に「\,n個の文字列は何通りあるか」と出題された場合,\ 自分で漸化式の作成を思いつく必要がある.
漸化式を作成するとき,\ 最初の1つまたは最後の1つで場合分けする}とうまくいくことが多い.
最後の1個で場合分けすると別解のようになるが,\ 本問では本解と変わらない.
文字n+2個の列は\
[\,文字n+1個の列\,]\,bf A & a_{n+1}\,通り
[\,文字n個の列\,]\,AB} & a_n\,通り
一応,\ 隣接3項間型漸化式a_{n+2}=a_{n+1}+a_n\,の一般項a_n\,の求め方を簡単に示しておく.
等比数列型)
この2式からa_{n+1}\,を消去するとa_n\,が求まる.
本問の場合,\ a_1=2,\ a_2=3である.
ゴツイ式だが,\ 正体は整数である.\ \ 実際,\ n=4を代入して計算してみるとちゃんとa_4=8になる.
(3)\ \ 文字$n+2$個の列には,\ 右端がAの列と右端がBの列がある.
[1]\ \ \.{右}端がA}の$n+2$個の列の数は,\ 残りの$n+1$個の列の数に等しく} $b_{n+1$通り
[2]\ \ \.{右}端がB}の$n+2$個の列の数は,\ ABの前の$n$個の列の数に等しく} $b_n}$通り
左端に条件が加わったせいで,\ 最初の1つで場合分けして漸化式を作成することが困難になる.
Bの次は必ずAなので,\ 左から3番目がAかB}かで場合分けするとしよう.
左端 Bの文字n+2個の列は\
BA}\,[\,左端がbf Aの文字n個の列\,] & ？\,通り
BA}\,[\,左端がbf Bの文字n個の列\,] & b_n\,通り
このように,\ 左端が Aの文字n個の列の総数をどのように表すかで普通は行き詰まる.
この総数が左端が Bのn+1個の列の総数に等しいことに気付けばb_{n+1}\,と表せるが,\ 中々難しい.
左端が Bのn+1個の列の2番目は必ず Aなので,\ 左端が Aのn個の列の総数に等しいのである.
右端は無条件であるから,\ 最後の1つで場合分けすると(2)と同様にして容易に漸化式を作成できる.
左端 Bの文字n+2個の列は\
[\,左端がbf Bの文字n+1個の列\,]\,A} & b_{n+1}\,通り
[\,左端がbf Bの文字n個の列\,]\,AB} & b_n\,通り
結局,\ (2)と全く同じ漸化式b_{n+2}=b_{n+1}+b_n\,が導かれる.
ただし,\ (2)とは初項と第2項が異なり,\ b_1=1,\ b_2=1である.
もちろん,\ n=3のときちゃんとb_3=2となる.\ 具体的には,\ BAAとBAB}の2通りである. [-.8zh]
なお,\ b_n\,を初項から順に書き出すと1,\ 1,\ 2,\ 3,\ 5,\ 8,\ ･･･\ となる.\ これをフィボナッチ数列}という.
