I had a combinatorics problem that I was hoping someone could help with:
Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2
To begin, I think I figured out some initial conditions, $a_1$ = 3 and $a_2$ = 8 (I'm not sure about $a_4$, but doing it by hand gets long a tedious and I'm not entirely sure 20 is correct).
I've tried to think of it in terms of the last letter (and what was before it), but I'm not sure this is the right approach. For example, my guess was that if we look at all sequences ending with 0 (and 2), we have all possibilities (that is any digit could come before it. For example, a sequence ending in 0 has 0 0, 1 0, or 2 0 as options for the last two digits in the sequence and 2 has 0 2, 1 2 and 2 2 as options), however, we only have two possibilities (0 or 1) if the sequence ends in 1 (The sequence can end with either 1,1 or 0,1).
I'm not sure how to express this in a recurrence relation. I'm pretty sure though that it has to be non-homogenous. I would really appreciate some help! Thanks in advanced!!
P.S. Because recurrence relations are so confusing, a detailed explanation in your answer would be helpful! Let me know if you have any questions or concerns! Thanks!
Best Answer
Introduce an auxiliary variable: let $b_n$ be the number of ternary sequences of length $n$ that do not contain a $2$. If a sequence of length $n$ contains a $2$, you can append a $0$ or a $2$; if it does not contain a $2$, you can append a $0$, a $1$, or a $2$. In particular, you can always append a $0$ or a $2$, and if it does not contain a $2$, you can also append a $1$. Thus,
$$a_{n+1}=2a_n+b_n\;.$$
Clearly $b_{n+1}=2b_n$, and in fact it’s not hard to see that $b_n=2^n$: you’re just counting binary strings of length $n$. Thus, $$a_{n+1}=2a_n+2^n\;.$$
I’ll leave the solution to you for now.