-1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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 :)

$\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.