2
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – lllook Dec 18 '15 at 19:53
  • 2
    $\begingroup$ 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. $\endgroup$ – Jorge Fernández Hidalgo Dec 18 '15 at 20:01
  • $\begingroup$ 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 $\endgroup$ – lllook Dec 18 '15 at 21:46
  • $\begingroup$ which is correct right? $\endgroup$ – Jorge Fernández Hidalgo Dec 18 '15 at 21:48
  • $\begingroup$ no, formula gives you 20 it shoudl be 22 $\endgroup$ – lllook Dec 18 '15 at 21:49

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.