Combinatorics question about binary string

Question

There exist a 20-digits sequence consists of 10 zeros and 10 ones. What is the number of combinations in which no three consecutive zeros are in the sequence.

The answer provided is 24068, and has to do with something like choosing M blocks of 2 zeroes from a set of 11.

Could someone explain this to me? Thank you!

Answer 1

The method that the solution is referring to is probably straightforward casework. Another way to do it would be to do complementary counting.

Another way we could ask the question is, how many strings are there without a string of $n$ zeroes where $3\leq n \leq 10$? To do this all we have to do is find the number of strings with a string of three or more zeroes and subtract those values from the total number of strings which is $\binom {20}{10}$

The trivial bashing is left to you. Next time it would be helpful uf you posted the solution and any work that you have already done :)

Answer 2

Let $M$ be the blocks of 2 consecutive zeroes. Let $N$ be the isolated zeroes.

Then we must have $2M+N=10$ (total zeroes), and we have a total of $M+N=10-M$ blocks (double o single) of zeroes.

For any given $M=0,1 \cdots 5$, the number of ways of arranging the $M+N$ blocks is

$$ \frac{(N+M)!}{N!M!}=\frac{(10-M)!}{M! (10-2M)!}$$

These blocks can be placed between the ones, for which we have 11 available positions. THe choosing of these positions can be made in

$$\binom{11}{N+M}=\binom{11}{10-M}$$

ways. Then the total number of strings is

$$ \sum_{M=0}^5 \binom{11}{10-M} \frac{(10-M)!}{M! (10-2M)!}=\sum_{M=0}^5 \frac{11!}{M! (M+1)!(10-2M)!}=24068$$

Answer 3

I arrived at the same answer as leonbloy, by slightly different reasoning. I've recast my answer to use his notation, to keep this as short as possible. We have $10-M$ blocks of zeroes, and there must be at least one one separating consecutive blocks. This accounts for $9-M$ ones, and leaves $M+1$ ones to distribute into $11-M$ spots, since in addition to putting ones between the blocks of zeroes, we can put them before the first block or after the last. By stars and bars, there are $\binom{11}{M+1}$ ways to do this, giving $$ \sum_{M=0}^5{\frac{(10-M)!}{M!(10-2M)!}\frac{11!}{(M+1)!(10-M)!}}= \sum_{M=0}^5{\frac{11!}{M!(M+1)!(10-2M)!}}=24,068 $$