counting ternary string witout substring “00”

I know there is recurence solution, but thats not what I am interested in, I want pure combinatorial solution, similar to this post. What I tried and started with but never realy finished was:

I know all count of all ternary strings is $3^n$ where n is length of string, so my plan is to subtract $T_n$ from $S_n$ where $T_n$ is number of all ternary strings with "00" substring, I am only able to count part of $T_n$ as it is very problematic since many of those cases overlap. Maybe I am supposed to use inclusion/exclusion principle but I dont know how to use it exactly, I am only aware that something like that exist and maybe could be useful here, but even there you have to count those overlappign cases.

Anyone could give me a hit how to solve it without any recursion ?

How many have $k$ zeroes?

First, select the places where your zeroes are going to go. This problem is choosing $k$ spots, out of $n$, so that no two are consecutive. Here is a solution to that problem, it turns out to be $\binom{n-k+1}{k}$.

After this there are $2^{n-k}$ ways to select the other positions (they can be $1$ or $2$).

Therefore we obtain

$$\sum\limits_{k=0}^{\lceil n/2 \rceil}\binom{n-k+1}{k}2^{n-k}$$

• what if you just chosen 011110 string, yes you did chose 2 zeros but they are not together, what am I missing ? and why are we summing to n/2, what if n is odd – lllook Dec 18 '15 at 19:53
• We need for all the zeroes to be distance at least $1$ apart, so we have to choose non-consecutive zeroes. We are summing to $\frac{n}{2}$ because that is the maximum number of zeroes we can have, any more and it is impossible for them to not be conecutive. – Jorge Fernández Hidalgo Dec 18 '15 at 20:01
• actually this formula doesnt work take n=3 it gives you 20, but it should be 22, as 27 is all possible - 5 that contain 00 as substring textmechanic.com/Combination-Generator.html – lllook Dec 18 '15 at 21:46
• which is correct right? – Jorge Fernández Hidalgo Dec 18 '15 at 21:48
• no, formula gives you 20 it shoudl be 22 – lllook Dec 18 '15 at 21:49