# Counting binary strings with at least two adjacent zeros.

Considering 8-bit strings, how many strings contains at least two adjacent zeros?

Here is my progress.

0 zeros in string = 0

1 zero = 0

2 = 7

3 = ?

4 = $8\choose4$ - 2

5 = $8\choose5$

6 = $8\choose6$

7 = $8\choose7$

8 = $8\choose8$

But I can't figure out how it is with 3 zeros in string. Can you help me? Can you tell the rest of my consideration is all right? According to result, is has to be 201 in total, but it doesn't fit for my calculations.

-
You will probably find it easier to count the strings that have no two adjacent $0$s. –  André Nicolas Nov 9 '11 at 20:29

To count the number of 8-bit strings that have exactly 3 zeros and at least 2 are adjacent, you can count the number of 8 bit strings with exactly 3 zeros, and subtract those in which they are not adjacent.

The number of 8-bit strings with exactly 3 zeros is $\binom{8}{3}$. To count those with no two zeros adjacent, consider placing the five $1$s, leaving space between them for possibly adding a $0$: $$\Box \quad1\quad \Box\quad 1 \quad\Box \quad 1 \quad \Box\quad 1 \quad \Box \quad 1\quad \Box$$ Now you will select three of the six boxes to place a zero in. There are $\binom{6}{3}$ ways of doing this. So the number of $8$-bit strings with exactly $3$ zeros, and at least two zeros adjacent is $$\binom{8}{3} - \binom{6}{3} = 56 - 20 = 36.$$

I don't know how you counted for $4$. Doing the same thing as above, there are $\binom{8}{4}$ strings with exactly four $0$s; if you place all the $1$s first, there are five places where a zero may go, so you need to subtract $\binom{5}{4}$ strings that have no two zeros adjacent; that gives $\binom{8}{4}-5 = 65$ strings.

The rest seem okay.

Using these totals, we have: $0 + 7 + 36 + 65+ 56+28+8+1=201$ total.

-
Except brute force gives $201$. –  Thomas Andrews Nov 9 '11 at 20:52
@Thomas: Oops; I added $\binom{6}{3}$ to $\binom{8}{3}$ instead of subtracting; should be $36$. That will fix the total. Thank you. –  Arturo Magidin Nov 9 '11 at 21:00

The 'clever' way is to note that if $k$ is an $n$-bit number, such that there are no consecutive 1 digits, then the sum $x+2x = 3x$ is an $n+1$-bit number with all the ones occuring in pairs. And giving such an $n+1$-bit number, it is necessarily divisible by $3$.

So we want strings of length $n+1$ composed of $0$ and $11$. If $i+2j=n+1$, we can count the number of such strings with $i$ zeros and $j$ occurrences of $11$ as $i+j \choose i$.

So we can write this number as:

$$\sum_{i+2j=n+1} {i+j \choose j}$$

The number you are looking for is:

$$2^n - \sum_{i+2j=n+1} {i+j \choose j}$$

for $n=8$.

-
You're complementing to deal with "consecutive 1s" instead of "consecutive 0s", right? You might want to mention that... –  Arturo Magidin Nov 9 '11 at 21:18
Whoops, quite right, I am counting 8-bit numbers without consecutive 1s, which should be the same as 8-bit numbers without consecutive 0s :) –  Thomas Andrews Nov 9 '11 at 21:24
I don't like characters :D I prefer explanation such as Arturo M. wrote. But I appreciate yours, because it is totally cool :)) –  Ondrej Janacek Nov 9 '11 at 22:00

The following is a less sophisticated version of the method of Thomas Andrews. We will count the complement, the strings that have no pair of consecutive $0$s. Then we can subtract this number from $256$, the total number of strings.

If there are no $0$s , the answer is easy, $1$. And if there is one $0$, the answer is equally easy, $8$.

We deal with two $0$s. So there will be six $1$s. Line them up in a row. The six $1$'s determine $7$ "gaps" (including the gaps at the two ends) that we can stuff a $0$ into. Choosing the $2$ gaps we use can be done in $\binom{7}{2}$ ways.

We deal next with three $0$s. So there will be five $1$'s, which determine $6$ "gaps" to stuff a $0$ into. Choosing the $3$ gaps we use can be done in $\binom{6}{3}$ ways.

Finally, we deal with four $0$s. We will have four $1$s, so $5$ gaps. The $4$ gaps we need for the $0$s can be chosen in $\binom{5}{4}$ ways.

That's all: if there are five or more $0$s, adjacency is unavoidable. Our count is therefore $$\binom{9}{0}+\binom{8}{1}+\binom{7}{2}+\binom{6}{3}+\binom{5}{4}.$$ (For fun, the easy cases of no $0$'s, one $0$ have been made to look like the others.)

Finally, calculate. We get $55$.

-
Nice one, André :) –  Ondrej Janacek Nov 9 '11 at 22:02