# Number of Ternary sequences least one $2$ appears to the left of a $0$

Find a recurrence for $a_n$, the number of ternary sequences of length $n$ in which at least one $2$ appears to the left of a $0$.

I am not sure how to think of this. If you start with a $0, 1$ or $2$ it seems like it should be $a_n = 3a_{n-1}$. However, I think that is an oversimplification.

• Do you mean that at least one $2$ appears before the first $0$? – N. F. Taussig Nov 12 '17 at 23:11

I would try to find a general formula of $a_n$ because it seems easy. we have a sequence of n number ( can be 0, 1 or 2). The inverse problem is that there is no 2 that appears to the left of a 0. that means for the first 2 appearing in the sequence, all elements at the left are 0 or 1, and all elements at the right are 1 or 2. if there is no 2 in the sequence, we have $2^n$ possible sequence. if there is at least one, we fix it at the position k (k between 1 and n), we have 2 possible options in each side so we have $2^{n-1}$ possible sequence, now the first 2 can take n position, so there is $n2^{n-1}$ sequence. As a result : the number is $(2+n)2^{n-1}$ (the inverse problem)
So $a_n = 3^n -(2+n)2^{n-1}$ verify with $n=2$ , $a_n=9-8=1$ (2,0) is the unique solution....
if you want a recursive formula you just need to replace $3^n$ using the general formula to obtain:
$a_n=3a_{n-1}+(n-1)2^{n-2}$