OMC103(F) - 題意の場合の数について文字列の長さに関する漸化式を立てる

長さ$n$の文字列で「ココア」を部分文字列として含まないものについて, 末尾2文字が「ココ」であるものの個数をを $a_n$, 末尾2文字が「アコ」であるものの個数をを $b_n$, 末尾1文字が「ア」であるものの個数をを $c_n$とする. ただし, $n=0, 1$ については以下の通りとする. $$a_0=b_0=0, \quad c_0=1, \quad a_1=0, \quad b_1=c_1=1$$ 末尾2文字が「ココ」であるとき, 末尾に「コ」を付け加えると末尾2文字が「ココ」となり, 末尾に「ア」を付け加えると末尾が「ココア」となる. 末尾2文字が「アコ」であるとき, 末尾に「コ」を付け加えると末尾2文字が「ココ」となり, 末尾に「ア」を付け加えると末尾1文字が「ア」となる. 末尾1文字が「ア」であるとき, 末尾に「コ」を付け加えると末尾2文字が「アコ」となり, 末尾に「ア」を付け加えると末尾1文字が「ア」となる.

以上から, 次の漸化式が成り立つ. $$a_{n+1}=a_n + b_n$$ $$b_{n+1}=c_{n}$$ $$c_{n+1}=b_{n}+c_{n}$$ フィボナッチ数列 $c_{n+2}=c_{n+1}+c_{n}$より, $c_{12}=233$. また, $a_{12}=c_{12}-1=232, b_{12}=c_{11}=144$. 長さ12の文字列で「ココア」を部分文字列として含まないものの個数は, $a_{12}+b_{12}+c_{12}=609$. よって, 長さ12の文字列で「ココア」を部分文字列として含むものの個数は, $2^{12}-609={\bf 3487}$.