# Number of binary strings of length 8 that contain either three consecutive 0s or four consecutive 1s

How many bit strings (Consists of only 0 or 1) of length 8 contain either three consecutive 0s or four consecutive 1s?

I am getting answer 256 but the provided answer is 147 . Can anyone explain why it is 147?

### Attempt

Case 1. Let's take 3 zeros as a single unit. They can be placed in 6 positions (2 sides positions and 4 positions in between 5 elements) rest of the five elements can be selected in $2^5$ ways (they can either be 0 or 1). So total $n_1=6\cdot 2^5$ but here you can have 8 ways to get 4 consecutive 1s..

In same way for Case 2. $n_2$ will be $5\cdot 2^4$ and here also we can find 8 ways to get 3 consecutive 0s. Thus total $= n_1+n_2-(8+8)=272-16=256$.

• Can you show your work? It would be more instructive to see where you went wrong in your calculation than to just give you the proper answer. – A.E Sep 7 '14 at 16:42
• Inclusion-Exclusion, I guess you counting twice some cases, like the string '00001111' – Snufsan Sep 7 '14 at 16:42
• @A.E case-1-->lets take 3 0s as a single unit they can be placed in 6 positions (2 sides positions and 4 positions in between 5 elements) rest of the five elements can be selected in 2^5 ways(they can either be 0 or 1). so total n1=6x2^5 but here you can have 8 ways to get 4 consecutive 1s..in same way for case 2 --> n2 will be 5x2^4and here also we can find 8 way to get 3 consecutive 0s. thus total= n1+n2-(8+8)=272 – user131459 Sep 7 '14 at 17:07

Lets use inclusion-exclusion method.

First we find the number of bit-strings from size of $n$ that doesn't contain the sequence '000'. We will construct recursion formula, let $F(n)$ be that number.

• If the first bit is '1' then the rest is just a string that doesnt contain '000' from size $n-1$
• If the first bits is '01' then the rest is just a string that doesnt contain '000' from size $n-2$
• If the first bit is '001' then the rest is just a string that doesnt contain '000' from size $n-2$

Therfore we get: $F(n) = F(n-1)+F(n-2)+F(n-3)$

With the initial conditions $F(0) =1, F(1) =2, F(2) =2^2$

With te same method we get: $G(n) = G(n-1)+G(n-2)+G(n-3)+G(n-4)$

With the initial conditions $G(0) =1, G(1) =2, G(2) =2^2, G(3)=2^3$

Where $G(n)$ is the number of bit-strings from size of $n$ that doesn't contain the sequence '1111'.

Now, by opening the recursion up we get $F(8)= 149$ and $G(8)=208$

So if we define:

• A = bit-string of size 8 that contain '000'
• B = bit-string of size 8 that contain '1111'

and by what we calculated we have $|A| = 2^8-F(8)$ and $|B| = 2^8-G(8)$

What left to complete inclusion exclusion is to find the size of $|A\cap B|$, which is easy since the only strings that satisfy both are: '00001111' , '11110000', '11111000', '00011111', '00011110', '10001111', '01111000', '11110001'

Now the desiered number is $|A|+|B|-|A \cap B|$

• According to this solution answer is 211...but provided answer is 147 – user131459 Sep 7 '14 at 17:21
• I had calculation error, it's indeed 147: $|A|=256-149=107$ , $|B|=256-208=48$ and finally we have: $107+48-8=147$ – Snufsan Sep 7 '14 at 17:32
• great explanation, thanks – Inoryy Dec 27 '14 at 14:07