Expert: Ahmed Salami - 5/19/2004

Question
how many nine digit binary numbers do not have any consecutive zeros?

Answer
Hi,
Sorry for the delay.
I'll try to go through this pretty easily.
The first digit of the nine digit binary numbers must be 1 otherwise we wouldn't have a nine digit number.
all numbers would be of the form 1--------
The remaining eight digit would range from 00000000 to 11111111 both in base 2
i.e 0 to 2^7 + 2^6 + 2^5 + .......... + 2 + 1
giving us 0 to 2^8 - 1 or simply 0 to 255
we therefore have 256 numbers to consider, or we can simply say that each of the eight spaces can be filled in 2 ways giving us a total of 2^8 i.e 256 ways.
Now, to the solution. For an eight digit number not to have consecutive zeros, it mustn't have more than four zeros. For the situations where we have 4,3,2,1 and no zeros there are 5C4,6C3,7C2,8C1 and 9C0 numbers without consecutive zeros.
These numbers represent the number of ways of arranging the zeros with at least one 1 in between any pair of zeros.
as an example consider the situation with four zeros and four ones; the zeros are to be arranged in the spaces before, between and after the ones as shown
     *1*1*1*1*
There are therefore 5 spaces for the four zeros to be filled in resulting in 5C4 options. The other considerations are similar.

So the number of nine digit binary numbers without consecutive zeros is 5C4+6C3+7C2+8C1+9C0
 = 5+20+21+8+1 =55
there are therefore 55 numbers.

Hope it was helpful.
You can always ask more.