How many sequences are there in which each 1 is separated by at least two 0s? (Assume that for this part m ≥ 2(n−1).)

Question

i) How many sequences (lists) of m 0s and n 1s are there?

ii) How many sequences are there in which each 1 is separated by at least two 0s? (Assume that for this part m ≥ 2(n−1).)

For i) I got (m+n)!/m!n!, which I think is correct. But how to do part ii?

Answer 1

It may be helpful to think of building sequences using "0" and "100" as letters, instead of "0" and "1". You may have to do some casework regarding sequences that end with a single "1" though.

Answer 2

I always find it best to attack such questions with a specific, non-trivial example. It should be easy to see that the two extreme cases [n=0 or m=2(n-1)] yield only one sequence each. So let's consider the case when m=12 and n=4.

Since we have four 1's, we have to place a minimum of six 0's in between them which gives us the sequence

$$1001001001$$

This leaves us six more zeroes, each of which can be placed in any of five locations: at the beginning or end, or in between any pair of 1's:

$$^\downarrow 10^\downarrow 010^\downarrow 010^\downarrow 01^\downarrow\\ $$

"Stars and bars" [see note below] tells us this can be done in $\binom{6+5-1}{5-1} = \binom{6+4}{4}$ ways.

Looking at the numbers in the second binomial coefficient, it's not difficult to see that the 6 is the number of remaining 0's to be distributed, which in general would be m-2(n-1); and the 4's are one less than the number of locations those remaining 0's can be placed, which in turn is the number of 1's in the sequence, i.e. n. Thus the general formula for the number of possible sequences would be

$$\binom{[m-2(n-1)]+n}{n} \;=\; \binom{m-n+2}{n}$$

P.S. If you're unfamiliar with the "Stars and Bars" method, there's a good description on the wikipedia page: Stars and Bars (Combinatorics)

Answer 3

How many sequences of $m$ 0's and $n$ 1's are there?

Your answer is correct.

How many sequences of $m$ 0's and $n$ 1's are there in which each 1 is separated by at least two zeros?

A.J.'s answer is correct. Let's modify angryavian's strategy to eliminate casework.

Observe that the number of sequences of length $m + n$ consisting of $m$ 0's and $n$ 1's in which each 1 is separated by at least two zeros is equal to the number of sequences of length $m + n + 2$ consisting of $m + 2$ 0's and $n$ 1's in which each 1 is immediately followed by two zeros.

To illustrate with A.J.'s example of $m = 12$ and $n = 4$, the sequence of length $16$ $$1000100010001000$$ corresponds to the sequence of length $18$ $$1001001001\color{red}{00}000$$ while the sequence of length $16$ $$1000010000100001$$ corresponds to the sequence of length $18$ $$1000010000100001\color{red}{00}$$ since we can extend our sequence of length $16$ with $12$ 0's and $4$ 1's in which each 1 is separated by at least two 0's to one of length $18$ with $14$ 0's and $4$ 1's in which each 1 is followed by at least two 0's by inserting two 0's after the final 1.

In general, we can extend a sequence of $m$ 0's and $n$ 1's in which each 1 is separated by at least two zeros to a sequence of $m$ 0's and $n$ 1's in which each 1 is followed by at least two zeros by inserting two zeros immediately after the final 1.

The number of sequences of length $m + n + 2$ consisting of $m + 2$ 0's and $n$ 1's in which each 1 is followed by at least two zeros can be found by arranging $n$ blocks of 100 and $m + 2 - 2n$ 0's, which can be done in $$\binom{m + 2 - 2n + n}{n} = \binom{m - n + 2}{n}$$ since we must choose which $n$ of the $m - n + 2$ positions required for $m + 2 - 2n$ 0's and $n$ 100's will be filled with 100's.