Number of length $8$ binary strings with no consecutive $0$'s 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?

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
$
