Elementary combinatorics

Question

You are given a string of $10$ characters, that can either be 'A' or 'B'. How many of them do not contain the string 'ABA'?

What I thought was to adopt a recursive approach. Supposing we know the number $n_7$ of strings of $7$ characters that don't contain 'ABA', then we have a choice of 8 places to put that string in, so there will be $2^{10}-(8 \cdot n_7)$ strings that satisfy the request. Similarly, we can find that $n_7$ is equal to $2^7-(5 \cdot n_4)$, and that $n_4=2^4-(2 \cdot n_1)$.

Since $n_1$ is obviously equal to $2$, we can subsitute that in and get

$n_4=2^4-4=12$

$n_7=2^7-60=68$

$n_{10}=2^{10}-544=480$

Is my reasoning correct?

Answer 1

For nonnegative integers $n,k$ with $k\le 2$, let $f(n,k)$ be the number of strings $s$ of length $n+k$ containing at least one substring matching 'ABA' and such that the first $k$ characters of $s$ match the first $k$ characters of 'ABA'.

Then $f(n,k)$ can be computed recursively as in the following Maple code

Explanation:

If $n < 3-k$, there's not enough space for an occurrence of 'ABA', so $f(n,k)=0$.

Next assume $n\ge 3-k$.

If $k=0$, the number of qualifying strings is

• $f(n-1,0)$ if the next character is 'B'.$\\[4pt]$
• $f(n-1,1)$ if the next character is 'A'.

If $k=1$, the number of qualifying strings is

• $f(n-1,1)$ if the next character is 'A'.$\\[4pt]$
• $f(n-1,2)$ if the next character is 'B'.

If $k=2$, the number of qualifying strings is

• $f(n-1,0)$ if the next character is 'B'.$\\[4pt]$
• $2^{n-1}$ if the next character is 'A'.

Applying the recursion, we get

\begin{array}{|c|c|c|c|} \hline n&f(n,0)&f(n,1)&f(n,2)\\ \hline 0&0&0&0\\ \hline 1&0&0&1\\ \hline 2&0&1&2\\ \hline 3&1&3&4\\ \hline 4&4&7&9\\ \hline 5&11&16&20\\ \hline 6&27&36&43\\ \hline 7&63&79&91\\ \hline 8&142&170&191\\ \hline 9&312&361&398\\ \hline 10&673&759&824\\ \hline \end{array}

Thus, since $f(10,0)=673$, the number of strings of length $10$ which contain no substring matching 'ABA' is $2^{10}-673=351$.