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!