OMC103(F)

　ここでは, 「ココア」を部分文字列として含まないものの個数を数えてみます.
　まず, $12$ 文字が全て「コ」のときで $1$ 通りです.
　上のパターンを除けば, 少なくとも$1$ 文字は「ア」が含まれるので, 以下はそのうち最も右にある「ア」が左から $i$ 文字目 $(1\leq{i}\leq12)$ にある場合について, 「ココア」を部分文字列として含まないものの個数を $F_{i}$ としてそれぞれ数え上げをします.
　それが $i$ 文字目にあるとき, $i+1$ 文字目以降は「コ」しか書かれていません. それに加えて, 「ココア」を部分文字列として含まないための必要十分条件は以下の通りです.

• $1$ 文字目から $i-1$ 文字目までに「コ」が連続しない.

　このことに留意して, $F_{i}$ を実際に求めてみましょう. $F_1=1, F_2=2$ で, $i\geq3$ について,

• $i-1$ 文字目が「ア」であるとき, $F_{i-1}$ 通り.
• $i-1$ 文字目が「コ」であるとき, $i-2$ 文字目が「ア」となることから $F_{i-2}$ 通り.

より $F_{i}=F_{i-1}+F_{i-2}$ が成り立ちます. これより $F_{12}=233$ まで順に求まり, $F_1+F_2+…+F_{12}=1+2+…+233=608$ 通りとなります.
　以上より, 「ココア」を部分文字列として含むような場合の数は $2^{12}-(1+608)=\bf{3487}$ 通りです.

　補足として, フィボナッチ数列の和について. $g_1=g_2=1, g_{n+2}=g_{n+1}+g_{n} (n=1,2,…)$ で定められるフィボナッチ数列 $\{ g_{n} \}$ の第 $n$ 項までの和 $S_{n}$ について, $S_{n}=g_{n+2}-1$ が成り立ちます. これは $g_{i}=g_{i+2}-g_{i+1}$ という式に $i=1,2,…,n$ を代入して, それらを辺々順に足すことによって得られます. この式を利用すれば, 上の $F_1+F_2+…+F_{12}$ は, $$F_1+F_2+…+F_{12}= g_2+g_3+…+g_{13}=g_{15}-1-g_1=608$$ とも求められます.