austin adams

Counting Strings Recursively in Combinatorics

December 19, 2016

In my combinatorics class, we covered many neat subjects, some easier and some harder. But one topic performed a near 180° in difficulty once I understood the process: writing recursive functions to count strings meeting certain criteria.

Simple Example

As an easy example, consider counting nonempty binary strings. Imagine such a string of length $n \in \mathbb{Z}$. We have two possibilities: it ends with $1$, preceded by a binary string of length $n - 1$; or it ends with $0$, preceded by another binary string of length $n - 1$. Thus, if $p(n)$ denotes the number of nonempty binary strings of length $n$, by the addition rule,

\[ \begin{split} p(n) &= p(n - 1) + p(n - 1) \\ &= 2p(n - 1) \end{split} \]

Now, we should define our base cases. Recall that our string is nonempty, so the smallest length to consider is $1$. Since only two one-length binary strings exist,

\[ p(1) = 2 \]

This is also the last base case we need, since our recursive definition of $p(n)$ reaches backwards only one ‘deep.’ So we should specify that $n > 1$ in our solution:

Base cases
$p(1) = 2$

Recursion
$p(n) = 2p(n - 1),\ n > 1$

Approaching Harder Problems

Next, let’s use the approach described above to solve a tougher problem:

Give a recursion for the number $g(n)$ of ternary strings of length n that do not contain $102$ as a substring.

(This is problem 3 in Section 3.11 of Applied Combinatorics by Keller and Trotter. The book is free as in freedom — you can browse it here!)

As before, to find a recursion, imagine a valid string of length $n$ and consider the three cases of the final character:

Now, using the addition rule, we find

\[ \begin{split} g(n) &= g(n - 1) + g(n - 1) + (g(n - 1) - g(n - 3)) \\ &= 3g(n - 1) - g(n - 3) \end{split} \]

Since our recursive definition invokes $g(n - 3)$ at the deepest, we need to provide a base case for $n = 1,2,3$. $g(1) = 3^1$ and $g(2) = 3^2$ since neither one- nor two-length ternary strings are long enough to contain the forbidden substring. $g(3) = 3^3 - 1$ because one of the strings is illegal.

Hence, our answer is:

Base cases
$g(1) = 3$
$g(2) = 9$
$g(3) = 26$

Recursion
$g(n) = 3g(n - 1) - g(n - 3),\ n > 3$