Number of length $8$ binary strings with no consecutive $0$'s

Question

How many $8$ bit strings are there with no consecutive $0$'s?

I just sat an exam, and the only question I think I got wrong was the above(The decider for a high-distinction or a distinction :SSS)

I took Number with consecutive $0$'s

1 zero $0$

2 zeros $\frac{7!}{6!}$

3 zeros above + $\frac{6!}{5!}$

4 zeroes above + $\frac{5!}{4!}$

5 zeros above + $\frac{4!}{3!}$

6 zeroes above + $\frac{3!}{2!}$

7 zeroes above + $\frac{2!}{1!}$

8 zeroes above + $1$

$(7*7)+(6*6)+(5*5)+(4*4)+(3*3)+(2*2)+1=140$

and we have $2^8 - 140=116$

Is this correct?

Answer 1

(Edited): The number of $n$-bit strings with no consecutive zeros is the Fibonacci number $F_{n+2}$. There are $F_{n+1}$ of these strings ending in $1$ and $F_{n}$ ending in $0$ (prove by induction).

Answer 2

A bit string with no consecutive zeros is composed of 1 and 10 units, but may also begin with one 0 unit. (That is, every zero is either preceeded by a one or is at the start of the string).

Let $N_{x,y}$ count the permutations of a bit string composed of $x$ 1 and $y$ 10 units.

$$N_{x,y} = \frac{(x+y)!}{x!\, y!}$$

So $N_{6,1}$ counts permutations of an eight bit string of $6$ 1 and $1$ 10.

$N_{5,1}$ counts permutations of an eight bit string beginning with 0, and the remainder composed of $5$ 1 and $1$ 10. (The starting 0 is fixed and cannot move.)

And so forth ...

You want to calculate: $N_{8,0} + N_{7,0} + N_{6,1} + N_{5,1} + N_{4,2}+ N_{3,2} + N_{2,3} + N_{1,3} + N_{0,4} \\ = \frac{8!}{8!\, 0!}+ \frac{7!}{7!\, 0!}+ \frac{7!}{6!\, 1!}+ \frac{6!}{5!\, 1!}+\frac{6!}{4!\, 2!}+\frac{5!}{3!\, 2!}+\frac{5!}{2!\, 3!}+\frac{4!}{1!\, 3!}+\frac{4!}{0!\, 4!} \\ = 1 + 1 + 7 + 6 + 15 + 10 + 10 + 4 + 1 \\ = 55 $

Answer 3

I can’t follow all of your work, but your final answer is off by quite a bit. Here’s a straightforward analysis by cases that’s probably about as quick as any if you’re not aware of the connection with Fibonacci numbers that Robert Israel gives in his answer.

Call a string good if it does not have consecutive $0$s. Clearly there is one good string with no $0$s, and there are $8$ good strings with one $0$. There are $\binom82=28$ strings with two $0$s, but $7$ of them are bad, so $21$ of them are good.

With three $0$s you have to have something like $_01_01_0_$, where each of the underscores may but need not represent one or more $1$s. This leaves three $1$s to be distributed into those underscores. You can put all of them into the same blank in $4$ ways. You can put two of them into one blank and one into another, and there are $4\cdot3=12$ ways to choose the blanks. Finally, you can put them into $3$ different blanks, and there are $\binom43=4$ ways to do this. This yields a grand total of $4+12+4=20$ good strings with three $0$s.

With four $0$s you have to have $_01_01_01_0_$, and the remaining $1$ can go into any of the five blanks.

A little thought will show that if you have more than four $0$s, two of them must be adjacent, so we’re done: there are

$$1+8+21+20+5=55$$

good strings. (In passing I note that $55$ is indeed $F_{10}$.)

Answer 4

I can't say what the cleanest answer is, but here's how I was able to work it. In such a sequence, there are at most 4 zeros. So we have 5 cases.

If there are no zeros, there is 1 solution.

If there is 1 zero, there are 8 solutions.

If there are 2 zeros, we can count the solutions as follows: Put the 1st $0$ in the 1st place. Then there are 6 places that the 2nd $0$ can go. If the 1st $0$ is in the 2nd place, then there are 5 places for the 2nd $0$, and so on. So we get $6 + 5 + 4 + 3 + 2 + 1 = 21$ solutions.

If there are 3 zeros... This case is trickier but the argument is similar. Put the zeros as close to the beginning as possible, eg. $01010111$. The last $0$ can be where it is, or it can move to occupy the place of the last three $1$s, so we count $4$ solutions from this configuration. Next, we move the second $0$ to get the sequence $01101011$. Here the last $0$ has $3$ places to choose from.

By counting this way, we get $(4 + 3 + 2 + 1) + (3 + 2 + 1) + (2 + 1) + (1) = 20$ solutions.

Finally, if there are $4$ zeros, you can use the same technique to show there are $5$ solutions.

So the final answer is $1 + 8 + 21 + 20 + 5 = 55$.