How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?
I have done like this
I have found Number of bit string with
(1) (i)zero consecutive $0.$
(ii) one $0$
(iii) two consecutive zero
or
(2)(i) zero consecutive 1s
(ii) one $1$
(iii) two consecutive $1's$
(iv)three consecutive $1's$
Now,
for (1)(i) I got $1$ string
(ii)$4$ string eliminated duplicates
(iii) $7+5+3+1=16$ string
(iv) we can arrange like (2,1) in two places or (1,1,1) in $3$ places
In 1st one I got 4+3+2+1=10 strings
In 2nd one I got 4+2+(5*4/2)=12 strings
Now we can take four $0's$ and arrangement will be (2,2), so that no three consecutive
Here I got 4+2=6 strings
Again I can take five consecutive $0's$ and arrangement will be like (2,2,1)
Here I got 2 strings
And lastly I can take six $0's$, arrangement will be like (2,2,2), here I got $1$ string
So, total 36 strings
Now for $1's$
2)(i) that is string with no $1's=1$ string
(ii) string with one $1's$=4 string
(iii) No. of string with three $1's$
Arrangement can be (1,1,1), and there are $6+5+4=15$ strings
Arrangement can be (1,2) and there will be 4+3=7 strings
(:)Now if there are four $1's$ and their arrangement will be (3,1) or arrangement (2,2)
there will be (9+7)=16 strings
(:) If there are five $1's$ arrangement will be like (3,2) or (2,2,1)
There will be 6+3=9 strings
(:) If there are six 1's arrangement will be (2,2,2) or (3,3)
There will be 16 strings
Now total string-(All previous string ) coming 150
but answer is 147
Moreover I have confused if some string is repeating in such a big calculation. Plz help me out. And also tell me some shortcut procedure if possible
Best Answer
Use the inclusion-exclusion principle with the following 11 properties: 000 starting at position 1, 2, 3, 4, 5, or 6; 1111 starting at position 1, 2, 3, 4, or 5.
Edit: on second thought, inclusion-exclusion would be quite cumbersome here. A simpler approach is to consider the complement (as you are doing) and condition on the initial run (0, 00, 1, 11, or 111). Doing so yields the following table, with a column for each length. The value in each cell indicates the number of "bad" strings (do not contain 000 or 1111) of that length.
The length 1 column is trivial, and the rest of the values can be obtained recursively from columns to the left.
The sum of the last column is 109, which subtracted from $2^8$ yields 147.