I am trying to count the number of bit-strings of length 8 with 3 consecutive zeros or 4 consecutive ones. I was able to calculate it, but I am overcounting. The correct answer is $147$, I got $148$.
I calculated it as follows:
Number of strings with 3 consecutive zeros = $2^5+5\times2^4 = 112$, because the 3 zeros can start at bit number 1, 2, 3, .., 6
Number of strings with 4 consecutive ones = $2^4+4\times2^3 = 48$, I used the same reasoning.
Now I am trying to count the number of bit-strings that contain both 3 consecutive zeros and 4 consecutive 1s. I reasoned as follows:
the strings can be of the following forms: 0001111x, 000×1111, x0001111..thus there are $2+2+2 = 6$ possibilities for bit-strings where the 3 consecutive zeros come first. Symmetrically there are $6$ bit-strings where the 4 consecutive ones come first.
Thus the answer should be = $112+48-12 = 148$.
clearly there's something wrong with my reasoning, if someone could point it out, that would be awesome. Thanks
Best Answer
Here's one way to get the 107 and the 48 in the comment by mjqxxxx.
Let $a_n$ be the number of bit-strings of length $n$ with 3 consecutive zeros. Then $$a_n=2a_{n-1}+2^{n-4}-a_{n-4}$$ because you can get such a string from a such a string of length $n-1$ by putting a zero or a one at the end, or from a string of length $n-4$ with no 3 consecutive zeros by tacking 1000 on at the end. Clearly $a_0=a_1=a_2=0$ and $a_3=1$, and then you can use the recursion to find $a_4=3$, $a_5=8$, $a_6=20$, $a_7=47$, $a_8=107$.
For bit-strings with 4 consecutive ones, the same logic gets you to $$b_n=2b_{n-1}+2^{n-5}-b_{n-5}$$ and then you proceed as before.