Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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, 000x1111, 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

share|improve this question
1  
Why can't the three consecutive zeros start at 7, or at 8? –  Gerry Myerson Aug 4 '12 at 0:04
    
because the string can have the following forms 000xxxxx, 1000xxxx, x1000xxx, xx1000xx, xxx1000x, xxxx1000 –  turingcomplete Aug 4 '12 at 0:12
1  
You seem to want bit-strings of length 8, then. You've double counted the strings 00011111 and 00001111, to start, but that won't get us going in the right direction unfortunately. –  Kevin Carlson Aug 4 '12 at 0:16
    
ah yes, so sorry. I will edit the question now. Thanks for pointing that out. –  turingcomplete Aug 4 '12 at 0:18
3  
I'm assuming you want the length to be $8$. The number of bitstrings with three consecutive zeroes is $107$; the number with four consecutive ones is $48$; the number with both is $8$; and $107 + 48 - 8 = 147$. I can't understand where your expression for the number with $3$ consecutive zeroes ($2^5 + 5 \times 2^4$) comes from at all, but I think your basic problem is overcounting strings with multiple copies of the target substring. –  mjqxxxx Aug 4 '12 at 0:26
add comment

2 Answers 2

up vote 3 down vote accepted

You've left out accounting for strings that have two triple zeroes. So $00010000,00010001,00001000,00011000,10001000$ were added to your total twice. This didn't cause any problems in your count of strings with four $1$s, however, since we can't put four $1$s in two separated places in an $8$-bit string. So the union now has $155$ elements, and cutting out the two duplicates from each symmetry of your intersection calculation turns that to $8$, for a total $107+48-8=147$.

share|improve this answer
    
Aha, I see. I missed those duplicates. Thanks, now I understand it. –  turingcomplete Aug 4 '12 at 1:09
add comment

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 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.

share|improve this answer
    
This is another nice way to think about it, I did not think of that. Thank you. –  turingcomplete Aug 4 '12 at 1:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.