次: マルコフ過程 上: 帰納的定義 前: 帰納的定義

漸化式で解く

いくつか例をやってみよう． 以下の例は直接計算しても，少し工夫すればできる． もちろん可能である． 一度やってみてほしい． しかし以下のような解もあるのである． 漸化式を立てて解く解法と，直接計算する解法を比較研究したい場合， 『別解研究』「個数処理の方法」「確率」にいくつかの例がある． 「個数処理の方法」では，主な解法は直接計算であるが， 漸化式を立ててもできる，という例が紹介されている． 「確率」でもいくつか二通りの方法で解いている．

例題 1.12  

三文字$a,\ b,\ c$の中から重複を許して5個の文字を選び， 横1列に並べてできる文字列をワードという． 文字列$bc$を含まないワードの総数， すなわち$b$の直後に$c$がこないようなワードの総数を求めよ．

考え方     この問題をどのようにするか． 一つの方法は場合に分けて個別に数える方法だ．

しかし$n$個の文字でできた文字列$bc$を含まないワードの総数を$x_n$とおいて， 数列$\{x_n\}$の漸化式を立てるのだ． それをさらにどの文字から始まるかで細分するとよい．

解答      n 個の文字でできた文字列$bc$を含まないワードの総数を$x_n$とおく． さらにそのうち， $a$から始まるものが$a_n$個， $b$から始まるものが$b_n$個， $c$から始まるものが$c_n$個であるとする．

$$x_n=a_n+b_n+c_n$$

である．

$n+1$個の文字でできた文字列において，$a$から始まるものと$c$から始まるものは，後に続く$n$個の文字列が $a$から始まっても，$b$から始まっても， $c$から始まってもよいので$$x_n=a_n+b_n+c_n$$通りある．

ところが$n+1$個の文字でできた文字列のうち$b$から始まるものは， 後に続く$n$個の文字の決め方が， $a$と$b$から始まるものだけで， $c$から始まるものを除かなければならない．

したがって

$$\left\{ \begin{array}{l} a_{n+1}=a_n+b_n+c_n=x_n\\ b_{n+... ...\quad =x_n-c_n\\ c_{n+1}=a_n+b_n+c_n=x_n \end{array}\right.$$

が成り立つ．$c_n=x_{n-1}$なので，辺々加えて

$$x_{n+1}=3x_n-x_{n-1}$$

$x_1=3,\ x_2=8$であるから

$$\begin{eqnarray*} x_3&=&3\cdot 8-3=21\\ x_4&=&3\cdot 21-8=55\\ x_5&=&3\cdot 55-21=144 \end{eqnarray*}$$

と求まるのである．□

もちろんこれから一般項も求まるが， 一般項を求めなくてよいときでも， 樹形図などを書いて個数を求めようとするよりも， 漸化式の方が正確である．

例題 1.13       ［03東大］

さいころを振り,出た目の数で17を割った余りを$X_1$とする．ただし，1で割った余りは0である． さらにさいころを振り，出た目の数で$X_1$を割った余りを$X_2$とする．以下同様にして， $X_n$が決まればさいころを振り，出た目の数で$X_n$を割った余りを$X_{n+1}$とする．

このようにして， $X_n,\ n=1,\ 2,\ \cdots$を定める．

1. $X_3=0$となる確率を求めよ．
2. 各$n$に対し，$X_n=5$となる確率を求めよ．
3. 各$n$に対し，$X_n=1$となる確率を求めよ．

注意：さいころは1から6までの目が等確率で出るものとする．

考え方     (1)は3回目に余りが0となる確率なので， 樹形図を書いて順次求めてもいけそうである． また実際不可能ではない． しかしやってみると結構たいへんである．

ここは個別の例から一般化するのではなく， 先にすべての起こりうる事象の確率を数列において，その相互関係， つまり漸化式を立てよう． $n$回目に，考えられるすべての余りのそれぞれになる確率を数列において， $n+1$のときの余りが$n$回のときの余りからどのように決まるかを考え漸化式を立てるのだ．するとこの試行のすべてがつかめる．

(2)(3)も一気に解ける． もし(1)を個別に考えていれば，(2)(3)段階で改めて必要な漸化式を立てねばならない．

一般項でなくて，決まった番号の場合の数や確率を求めるときにも，漸化式を立てる．

解答    

1. 17を $1,\ 2,\ 3,\ 4,\ 5,\ 6$で割った余りはそれぞれ $0,\ 1,\ 2,\ 1,\ 2,\ 5$である．

   $0$を1から6の数で割った余りはつねに$0$，
   $1$を1で割れば余りは$0$，2から6の数で割った余りは$1$，
   $2$を1か2で割れば余りは$0$，3から6の数で割った余りは$2$，
   $5$を1から6の数で割った余りは順に $0,\ 1,\ 2,\ 1,\ 0,\ 5$である．

   $X_n=0$となる確率を$a_n$， $X_n=1$となる確率を$b_n$， $X_n=2$となる確率を$c_n$， $X_n=5$となる確率を$d_n$と置く．

   上のことから

   $$\begin{eqnarray*} a_{n+1}&=&a_n+\dfrac{1}{6}b_n+\dfrac{2}{6}c_n+\dfrac{2}{6}d_n... ...\quad \quad \quad \quad \quad \quad \quad \quad \dfrac{1}{6}d_n \end{eqnarray*}$$
   
   

   また．
   

   $$a_1=\dfrac{1}{6},\ b_1=\dfrac{2}{6},\ c_1=\dfrac{2}{6},\ d_1=\dfrac{1}{6}$$
   
   
   である．$n=2$のときの確率を上記漸化式によって計算すると
   
   $$a_2=\dfrac{14}{36},\ b_2=\dfrac{12}{36},\ c_2=\dfrac{9}{36},\ d_2=\dfrac{1}{36}$$
   
   

   求める確率は$a_3$である．
   

   $$∴\quad a_3=\dfrac{14}{36} +\dfrac{1}{6}\cdot\dfrac{12}{36... ...\dfrac{9}{36} +\dfrac{2}{6}\cdot\dfrac{1}{36}=\dfrac{29}{54}$$
   
   

2. 求める確率は$d_n$である．
   
   $$d_n=\left(\dfrac{1}{6} \right)^{n-1}d_1=\dfrac{1}{6^n}$$
   
   

3. 求める確率は$b_n$である．(2)から
   
   $$b_{n+1}=\dfrac{5}{6}b_n+\dfrac{2}{6}\cdot\dfrac{1}{6^n}$$
   
   
   つまり
   
   $$6^{n+1}b_{n+1}=5(6^nb_n)+2$$
   
   
   これから
   
   $$6^{n+1}b_{n+1}+\dfrac{1}{2}=5\left\{6^nb_n+\dfrac{1}{2}\right\}$$
   
   
   
   
   $$∴\quad 6^nb_n+\dfrac{1}{2}=5^{n-1}\left\{6\cdot\dfrac{2}{6}+\dfrac{1}{2}\right\} =\dfrac{1}{2}5^n$$
   
   
   
   
   $$∴\quad b_n =\dfrac{1}{2}\left\{\left(\dfrac{5}{6}\right)^n-\left(\dfrac{1}{6}\right)^n \right\}$$
   
   

□

次: マルコフ過程 上: 帰納的定義 前: 帰納的定義