明らかに \(N =2,3\) のとき、答えは \(1\) です。以降は \(N>3\) を仮定します。

\(c_{\mathrm{AB}} =\) B の場合について説明します(Aの場合もほぼ同様です)。

\(c_{\mathrm{BB}} =\) B ならば作れる文字列は \(1\) 通りです。 以降は \(c_{\mathrm{BB}} =\) A であることを仮定します。

このとき、\(c_{\mathrm{BA}} =\) A ならば、先頭が AB、末尾が Bであるような文字列全てを構成可能です。よって答えは \(2^{N-3}\) 通りです。

\(c_{\mathrm{BA}} =\)B のときは、先頭が AB、末尾が B であるような文字列のうち、AA を部分文字列として含まないもの全て構成可能です。このときの答えは以下の漸化式で定義される \(F\) を用いて \(F_{N-2}\) 通りです。

\( F_{n} = \begin{cases} 1 & \text{if } n \leq 1 \cr F_{n-1} + F_{n-2} & \text{otherwise} \end{cases}\)