Counting the number of bit strings of length eight contain either three consecutive 0s or four consecutive 1s

Q - How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?

Answer is = 147

My approach -

Let n(0) = Number of bit strings of length eight with three consecutive 0s

n(1) = Number of bit strings of length eight with four consecutive 1s

n(0 ∩ 1) = Number of bit strings of length eight with both three consecutive 0s and four consecutive 1s

Then according to inclusion-exclusion principle, we will get our solution i.e -

n(0 ∪ 1) = n(0) + n(1) - n(0 ∩ 1)

Also, consider X = 000 (three consecutive 0s) and Y = 1111 (four consective 1s)

1. n(0) :

X can be placed at any of the six positions in 8 bit string like :  X----- = 000----- , -X---- = -000----, ...., -----X = -----000

and the remaining 5 places can have 25 permutations.

So, n(0) = 6 * 25 = 192

Similarly, we can find :

2. n(1)  = 5 * 24 = 80

3. n(0 ∩ 1) = 3! * 21 = 12

Finally, n(0 ∪ 1) = 192 + 80 - 12 = 260, which is not the correct answer.

Can someone please guide me what is wrong with my approach ? Thanks in advance.

2Comments
Sumit Verma @sumitkgp
26 May 2017 03:54 pm
Ishan Bhardwaj @ishan58
27 May 2017 03:24 pm

Okay, I get it. 

Thanks a lot.