counting

Question

How many bit strings of length 10 contain either five consecutive 0s or five consecutive 1s?

I got 382.Is it correct?

Comments

Yeah...382 is the correct answer

Answer 1

Let $T(n)$ denote the number of but strings of length $n$ containing 5 consecutive 0's. 

Total no. of bit strings of length $n = 2^n$

So, no. of bit strings of length $n$ not containing 5 consecutive 0's = $T(n)' = 2^n - T(n)$

Now, we can form a recurrence relation for $T_n$. We can for a bit string of length $n$ containing 5 consecutive 0's in two ways:

1. from a bit string of length $n-1$, containing 5 consecutive 0's by adding either 0 or 1 at end.
2. from a bit string of length $n-6$, not containing 5 consecutive 0's by adding 100000 at end.  

These two covers any possible bit strings containing 5 consecutive 0's. In the second case we needed "100000" and not "00000" as "00000" would cause strings already considered in 1.

$T(0) = T(1) = T(2)= T(3) = T(4) = 0, T(5) = 1$

$T(n) = 2T(n-1) + T(n-6)' \\= 2T(n-1) + 2^{n-6} -T(n-6) $

We get,

$T(6) = 2T(5) + 2^0 - T(0) = 3$

$T(7)  = 2T(6) + 2^1 - T(1) = 8 $

$T(8) = 2T(7) + 2^2 - T(2) = 20$

$T(9) = 2T(8) + 2^3 - T(3) = 48$

$T(10) = 2T(9) + 2^4 - T(4) = 112$

The number of bit strings having 5 consecutive 1's must also be 112. 

Now, we need to find the number of bit strings of length 10 containing 00000 as well as 11111. There are only 2 possibilities:

1111100000 and

0000011111 

Thus no. of bit strings of length 10, having either five consecutive 0's or 5 consecutive 1's = 112 + 112 - 2 = 222

Comments

Can u plz  explain case 2?

---

The first case contains all cases where "00000" is present in a string of length "n-1". Now, we have to consider the remaining strings. That is those which strictly do not contain "00000" with length "n-1". And we have to add "00000" to it. So, we consider strings of length "n-5". But there is a problem here. Suppose the string is ending with "0", and we append "00000" to it, we actually got "00000" within length "n-1" - which we have considered in case 1. So, to eliminate this we have to consider n-6 th character to be strictly "1". 

---

@arjun sir , how this method come in your thought process , i just did with set theory and combination ,.. i took too much time .. :(

---

@Arjun what beautiful concept u have given for this question , i have seen lots of solution for this question but first time i understood this , thanks a lot for beautiful concept

Answer 2

One more approach .

Consider 5 consecutive 0s first
the 5 consecutive 0’s can start at position 1, 2, 3, 4, 5, or 6 –
Starting at position 1 •
Remaining 5 bits can be anything: 2^5 = 32 –
Starting at position 2 •
First bit must be a 1  Otherwise, we are including possibilities from the previous case!
• Remaining bits can be anything: 2^4 = 16 –
Starting at position 3 •
Second bit must be a 1 (same reason as above) •
First bit and last 3 bits can be anything: 2^4 = 16 –
Starting at positions 4 and 5 and 6 , Same as starting at positions 2 or 3: 16 each – Total = 32 + 16 + 16 + 16 + 16 + 16 = 112 • The 5 consecutive 1’s follow the same pattern, and have 112 possibilities •
There are two cases counted twice (that we thus need to exclude): 0000011111 and 1111100000 • Total = 112 + 112 – 2 = 222

Comments

When we start at position 2, should we put 1 as first bit and 7th bit i.e

1 0 0 0 0 0 1 0/1 0/1 0/1 = $2^3$ ?

because if we put 0 at seventh bit place we will have 6 consecutive 0’s?

So I think we will have $2^3*4 + 2*2^4$ = 64 for 0’s consecutive and 64 for 1’s consescutive, 64 + 64 - 2 = 126