My colleague challenged me to solve this problem. I approached this by partitioning by the first digit…
Consider the 3 cases for the first digit of the sequence (0, 1, 2). If we have no restrictions, finding the number of ways to create all possible n-digit ternary sequences is trivial to express as a recurrence relation:
$0: a_{n-1} \ ways$
$1: a_{n-1} \ ways$
$2: a_{n-1} \ ways$
So the possible ways to form all possible n-digit ternary sequences can be expressed as: $a_n = 3a_{n-1}$
But if we can't have a "012" subsequence in the n-digit string, then things get a bit harder, but not by much. We can still partition by the first digit. If we have a zero, we may run into the problem where we have a "012" subsequence, but the number of ways for when 1 or 2 is the first digit is the same:
$0: ?$
$1: a_{n-1} \ ways$
$2: a_{n-1} \ ways$
How can we exclude the "012" subsequences? I did this by sub-partitioning when 0 is the first digit. If we have 00 as our first 2 digits, then we won't have the problem where "012" is a subsequence. There are $a_{n-2}$ ways to do this because we've already chosen the first 2 digits. The same applies for 02; we won't get the problematic sequence (i.e. 012).
If 01 are our first 2 digits, then we may have a problem. The only possible choices are 010 and 011 – 2 choices. We decided on the first 3 digits, so we have $2a_{n-3}$ ways to choose the remaining digits to form the n-digit string.
Here is my full partition:
$0:$
$ \ \ 00: a_{n-2} ways$
$ \ \ 01: 2a_{n-3} ways$
$ \ \ 02: a_{n-2} ways$
$1: a_{n-1} \ ways$
$2: a_{n-1} \ ways$
By the Addition Principle, I can sum all parts of the partition. This gives me:
$$a_n = 2a_{n-1} + 2a_{n-2} + 2a_{n-3}$$
or the cleaner:
$$a_n = 2(a_{n-1} + a_{n-2} + a_{n-3})$$
Am I correct?
Best Answer
This doesn't quite work. It is not the case that inserting $00$ or $010$ in front of a legal sequence necessarily gives a legal sequence. A simpler approach might be to note that inserting any digit in front of a legal sequence of length $n-1$ results in a legal sequence of length $n$ unless the inserted digit is $0$ and the sequence began with $12$. But inserting $12$ in front of a legal sequence of length $n-3$ always produces a legal sequence of length $n-1$, so we know that among the $a_{n-1}$ legal sequences of length $n-1$ there are $a_{n-3}$ that start with $12$. Therefore $$ a_n=3a_{n-1}-a_{n-3}. $$