1
$\begingroup$

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.

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

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.