Counting Strings Recursively in Combinatorics
December 19, 2016In 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 onelength 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:

Case 0: The last character is a $0$. The string of length $n  1$ preceding this character can be anything, so we have $g(n  1)$ possible strings in this case.

Case 1: The last character is a $1$. Just like in case 0, we can produce a valid $n$length string by appending a $1$ to any valid string of length $n  1$, so we have $g(n  1)$ possibilities for this case too.

Case 2: The last character is a $2$. Since we assumed our string complies with our requirements, we know our ending $2$ cannot be preceded by $10$. Otherwise, we’d have a string ending with $102$, violating the assumption that our string is valid.
So our answer for this case is the number of strings of length $n  1$ not terminated by $10$. We can use the inclusionexclusion principle to find this number: first calculate the number of valid strings of length $n  1$, and then subtract the number of valid strings of length $n  1$ ending in $10$. The former is $g(n1)$. The latter is $g(n  1  2)$, since we fix $10$ as the end of our $n  1$length string. Then we have $g(n  1)  g(n  3)$ as our solution.
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 twolength 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$