次: 階段の昇り方［07京大理系］ 上: 直接計算か漸化式か 前: 直接計算か漸化式か

単語の個数［98名古屋市大改題］

問題     

3種類の文字a，b，c のなかから重複を許して5個の文字を選び， 横一列に並べてできる文字列をワードと呼ぶ．文字列$bc$を含まないワードの総数を求めよ．

方針

1. 文字列$bc$を含む個数を計算し，総数から減じることで求める．
2. $n$文字のワードの個数の漸化式を立て，$n=5$のときの値を求める．

解1

各位置の文字の決め方が3通りあるので，5文字の場合総数は$3^5=243$個ある．

そのうち$bc$を含むものを

$$\begin{array}{ll} 1)&bc○○○\\ 2)&○bc○○\\ 3)&○○bc○\\ 4)&○○○bc \end{array}$$

の型に分け考える．○の所はいずれの文字でもよい． 各型は$3^3=27$個ある． 1)と3)には$bc○bc$型のものが3個共通にある．1)と4)，2)と4)に もそれぞれ3個共通なものがある．

従って$bc$を含む相異なるワードは

$$4\times 27-3\times 3=99\ (個)$$

ある．その結果，文字列$bc$を含まないワードの総数は $243-99=144\ (個)$である．

解2

$n$文字からなる文字列$bc$を含まないワードのうち， $a$から始まるものが$a_n$個， $b$から始まるものが$b_n$個， $c$から始まるものが$c_n$個とする．

$n$文字からなるワードの左側に次の文字をおくと考えると，

$$\begin{eqnarray*} &&a_{n+1}=a_n+b_n+c_n\\ &&b_{n+1}=a_n+b_n\\ &&c_{n+1}=a_n+b_n+c_n \end{eqnarray*}$$

$a_1=b_1=c_1=1$なので，

$$\begin{eqnarray*} &&(a_2,\ b_2,\ c_2)=(3,\ 2,\ 3)\\ &&(a_3,\ b_3,\ c_3)=(8,\ 5,... ... b_4,\ c_4)=(21,\ 13,\ 21)\\ &&(a_5,\ b_5,\ c_5)=(55,\ 34,\ 55) \end{eqnarray*}$$

よって 文字列$bc$を含まないワードの総数は $55+34+55=144\ (個)$である．