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×2^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×2^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.

did you do it like this cz m also confused:- initially fixing first 3 pos for 0s thus getting 2^5 ways and then fixing a 1 before three 0s and thn shifting the 4 digits together towards other end thus getting 2^4 ways 4 times. i guess then 10001000 would be counted twice

i guess there is one more number that will repeat which is 10001000..it is counted 2 times. but this type of case will nt occur while calc for 4 consecutive ones because we wont have enough places to get a repeated number