4

I worked this problem using a recursive sequence, i.e. it can end in $1$, leaving $a_{n-1}$, or $10$, leaving $a_{n-2}$, $100$ leaving $a_{n-3}$, $1000$ leaving $a_{n-4}$, $10000$ leaving $a_{n-5}$, and finally $00000$ leaving $2^{n-5}$ possibilities. $a_{0}=a_{1}=a_{2}=a_{3}=a_{4}=0$ Then I worked it up to $n=8: a_{5}=1, a_{6}=1+2^{6-5}=3, a_{7}=3+1+2^{7-5}=8, a_{8}=8+3+1+2^{8-3}=20$.

My question is, aside from counting each individual bit string (which I did, by the way), how else can this type of problem be worked?

Thanks!

Jabernet
  • 1,724
  • 2
    Correct apart from a minor typo. The same idea works for $n+1$ consecutive out of $2n$ or $2n+1$. For longer strings, we can useInclusion/Exclusion. – André Nicolas Aug 12 '15 at 05:27

1 Answers1

1

Here's another way to work this type of problem.

The earliest string of five consecutive $0$s either comes at the very beginning or else is preceded by a $1$. If it comes at the very beginning, there are clearly $8$ ways to fill in the final three bits. If it's preceded by a $1$, there are $4$ choices for the other two bits and the $6$-bit string $100000$ comes either before, between, or after them, for another $4\times3=12$ possibilities, which gives a total of $8+12=20$.

Note, this approach works to count the number bitstrings of length $n$ with $k$ consecutive $0$s whenever $k\le n\le2k$. It begins to falter (which is to say, you need to start doing some inclusion-exclusion) when the string is long enough to both start with $k$ consecutive $0$s and have a string preceded by a $1$.

Barry Cipra
  • 79,832