# Discrete Mathematics- Counting Bit Strings

So I'm a little bit stuck on how to continue about this problem. "How many bit strings of length eight do not contain six consecutive 0s?"

So what I did first is I found the total amount of bit strings 2^8 = 256.

I know that there must be at least one string with 8 consecutive 0's, at least one with 7 consecutive 0's, and one with at least 6 consecutive 0's. But how do I find how many of each is contained without listing out all the 8 bit strings?

Thanks.

• Hint: your problem is equivalent to counting how many ways there are to fit $0, 1,$ or $2$ pins in $8$ holes... – A.P. Mar 26 '15 at 23:04
• Count the strings with at least $6$ consecutive $0$ (bad strings), and subtract from $2^8$. For bigger numbers we might have to get fancier, but your cases approach works fine here. There is $1$ string with $8$ consecutive $0$'s. There are $2$ with $7$ consecutive but not $8$, namely $10000000$ and the reversal of this. For $6$ consecutive but not $7$, the $0$'s could start at the beginning. So we get $0000001x$, where $x$ is anything, so $2$. Then there is $10000001$. Finally, there is $x1000000$ so $2$ more. Add up. – André Nicolas Mar 26 '15 at 23:05

You are saying (correctly) that the number you are looking for is $2^8-B$ where $B$ is the number of bad strings, i.e., those containing six consecutive zeros. And to know what $B$ is you say correctly that it is the sum $B_6+B_7+B_8$, where $B_k$ is the number of $8$-bit strings containing $k$ consecutive zeros. Now, what is $B_8$ (hint: that is very easy to answer). What is $B_7$ (hint: not a large number at all, you can list all such strings). What is $B_6$ (hint: a slightly bigger number, but do you notice some symmetry?)