How many bit strings of length four do not have two consecutive 0s?
(A) 12. (B)6
(C)4. (D) 8
Answers
How many bit strings of length four do not have two consecutive 1s?
Total number of bit strings of length: 24Total number of length 4 bit strings with 4 consecutive 1s: 1Total positions for three consecutive 1s in length 4 bit string: 2 (111X, X111)Number of bit strings for each of above positions: 2 (X can be 0 or 1)Total positions for two consecutive 1s in length 4 bit string: 3 (11XX, X11X, XX11)Number of bit strings for each of above positions: 4By inclusion exlcusion principle, the desired count =24−3×4+2×2−1=16−12+4−1=7
There are 8-bit strings of length four that do not have two consecutive 0s.
(Option d)
Total number of bit strings of length: 2⁴
Total number of length 4-bit strings with four consecutive 0s: 0
Total positions for three consecutive 0s in length 4-bit string: 2 (111X, X111)
Number of bit strings for each of the above positions: 2 (X can be 0 or 1)
Total positions for two consecutive 0s in length 4-bit string: 3 (11XX, X11X, XX11)
Number of bit strings for each of the above positions: 4
Thus,
By inclusion-exclusion principle,
The desired count =2⁴−3×4+2×2−0
=16−12+4−0
= 8
As a result, there are 8-bit strings of length four that do not have two consecutive 0s.