How many ternary strings over alphabet {0,1,2} are there which do not contain 2 or more consecutive non-zero characters?

I have figured out recursive relation which is $f_n=f_{n-1}+2\cdot f_{n-2}$ where $f_1=3$ and $f_2=5$

I am looking for combinatorial solution (using sums and combination numbers).

what I tried so far was $\sum_{k=\lfloor n/2\rfloor}^n \binom{n}{k}2^{n-k}$, i choose k zeros and for the remaining $n-k$ spaces I choose either $1$ or $2$, k must be $\lfloor n/2\rfloor$ because if there are less then there exist no such string, but this fails for $n=3$ since it counts string $0xx$ and and $xx0$ as valid where $x$ can be $1$ or $2$

examples: 12000102 is not valid string because it contains 12, 00102000202 is valid

Any ideas?

Edit: another idea is to view all consecutive zeros as a separators, where i can shrink them into one and then fill remaining free slots with 1s and 2s

  • 1
    $\begingroup$ In this case there is a straightforward closed form solution of the shape $a2^n +b(-1)^n$. No combinatorial expression can match this in simplicity. $\endgroup$ – André Nicolas Dec 20 '15 at 17:48
  • 1
    $\begingroup$ While this is not as simple as the solution to the recursive relation, you can write the answer as $\sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n+1-k}{k}\cdot 2^k$ $\endgroup$ – user84413 Dec 20 '15 at 17:51
  • $\begingroup$ how did you get this sum $\endgroup$ – lllook Dec 20 '15 at 17:56
  • $\begingroup$ I explained this in an answer below. $\endgroup$ – user84413 Dec 20 '15 at 18:03

Let $k$ be the number of nonzero digits, so there are $2^k$ choices for these digits.

We must insert a zero between each of these so that they are not consecutive,

which leaves $n-k-(k-1)=n-2k+1$ zeros left to distribute, with the $k$ nonzero digits as dividers.

Since there are $\dbinom{n-k+1}{k}$ ways to distribute these zeros,

there are a total of $\displaystyle\sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-k+1}{k}\cdot 2^k$ such words.


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.