How many bit strings of length eight contain 3 consecutive 0's or 4 consecutive 1's?
As we go with Mutual Inclusion and Exclusion principle :
| A ∪ B | = | A | +| B | - | A ∩ B |
A --- bit strings of length eight contain 3 consecutive 0's
B --- bit strings of length eight contain 4 consecutive 1's
Coming to |A| :- bit strings of length eight contain 3 consecutive 0's
total eight positions, in which 3 are fixed to 0's and remaining are have 2 chocies = 2$^5$.
But those 3 zero's are should be contiguous ==> 3 contiguous locations in 8 locations = 8-3+1 = 6.
i) 000 _ _ _ _ _
ii) _ 000 _ _ _ _
iii) _ _ 000 _ _ _
iv) _ _ _000 _ _
v) _ _ _ _000 _
vi) _ _ _ _ _000
So total = 6 * 2$^5$, But note that there are some sequences which may over counted !
So we have to subtract some count from 6 * 2$^5$.
let think consecutive zero's of length 4 :- 0000 _ _ _ _
this can be look as ${\color{Red}{000}} 0 \_\; \_\; \_\; \_\;$ or $ 0 \color{Magenta}{000} \_\; \_\; \_\; \_\;$
these type of sequences counted twice, we have to remove one of the sequences.
those 4 contiguous locations in 8 locations = 8-4+1 = 5.
total of 4 length = 5 * 2$^4$.
let think consecutive zero's of length 5 :- 00000 _ _ _
this can be look as $ \color{red}{000} 0 0 \_\; \_\; \_\; $ or $ 0 {\color{Magenta}{000}} 0 \_\; \_\; \_\; $ or $ 0 0 \color{green}{000} \_\; \_\; \_\; $
these type of sequences counted thrice, we have to remove two of the sequences, But wait !
all those extra sequences are covered in " consecutive zero's of length 4 " !
So, don't worry about them !!
So, no need to worry about 5,6,7,8 lengths to subtract !
But note that, if more than 2 groups of consecutive three 0's exist in the sequence ?
i mean to say,
i) 000 __ __ 000 ===> this counted twice due to visualizing it as $ \color{red}{000} \_\; \_\; \_\; \_\;$ or $ \_\; \_\; \_\; \_\; \color{Magenta}{000} $
these type of sequences are over counted, so need to subtract for the original sum !
0 0 0 $\color{red}{\_}\;\; \color{Magenta}{\_} $ 0 0 0, for having two groups, there must be atleast one 1 should be present .
if i place 1 in red blank ==> Magenta blank can be 0 or 1. ===> 2 possibilities
if i place 1 in Magenta blank ==> red blank can be 0 ( but 1 is already counted in previous case ) ===> 1 possibilities
ii) _ 000 _ 000 ===> _ 000 1 000 ==> the blank can be 1 ( but 0 is already counted in previous case )
iii) 000 _ 000 _ ===> 000 1 000 _ ==> the blank can be 1 ( but 0 is already counted in previous case )
Total = 2+1+1+1 = 5
|A| = 6 * 2$^5$ - 5 * 2$^4$ - 5 = 6*32 - 5*16 - 5 = 192 - 80 - 5 = 107
Coming to |B| :- bit strings of length eight contain 4 consecutive 1's
total eight positions, in which 4 are fixed to 1's and remaining are have 2 chocies = 2$^4$.
But those 4 one's are should be contiguous ==> 4 contiguous locations in 8 locations = 8-4+1 = 5.
So total = 5 * 2$^4$, But note that there are some sequences which may over counted !
So we have to subtract some count from 5 * 2$^4$.
let think consecutive one's of length 5 :- 11111 _ _ _
this can be look as $ \color{red}{1111} 1 \_\; \_\; \_\; $ or $ 1 \color{Magenta}{1111} \_\; \_\; \_\; $
these type of sequences counted twice, we have to remove one of the sequences.
those 5 contiguous locations in 8 locations = 8-5+1 = 4.
total of 5 length = 4 * 2$^3$.
let think consecutive zero's of length 6 :- 111111 _ _
this can be look as $ \color{red}{1111} 1 1 \_\; \_\;$ or $ 1 \color{Magenta}{000} 0 \_\; \_\;$ or $ 1 1 \color{green}{1111} \_\; \_\; $
these type of sequences counted thrice, we have to remove two of the sequences, But wait !
all those extra sequences are covered in " consecutive zero's of length 5 " !
So, don't worry about them !!
So, no need to worry about 6,7,8 lengths to subtract !
is there any chance like that in previous case ?
But note that, if more than 2 groups of consecutive three 0's exist in the sequence ?
1111 _ 1111 ==> it leads to minimum length = 9 ===> don't worry about it !
|B| = 5 * 2$^4$ - 4 * 2$^3$ = 5*16 - 4*8 = 80-32 = 48
Coming to | A ∩ B | :- bit strings of length eight contain 4 consecutive 1's
total eight positions, in which 4 are fixed to 1's and 3 are fixed to 0's ==> only one bit is left.
i) _ 000 1111 ( don't worry about the order of zero's and ones's )
ii) 000 _ 1111 ( don't worry about the order of zero's and ones's )
iii) 000 1111 _ ( don't worry about the order of zero's and ones's )
there for only 4 possible sequences without worrying of order
but in a sequence, either three 0's then four 1's or four 1's then three 0's orders are possible = 2.
Total = 4 * 2 = 8
Required answer = 107 + 48 - 8 = 107 + 40 = 147