retagged by
8,865 views
9 votes
9 votes
How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?
retagged by

9 Answers

Best answer
19 votes
19 votes

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

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

So, no. of bit strings of length $n$ not containing 3 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 3 consecutive 0's in two ways:

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

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

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

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

We get,

$T(4) = 2T(3) + 2^0 - T(0) = 3$

$T(5)  = 2T(4) + 2^1 - T(1) = 8$

$T(6) = 2T(5) + 2^2 - T(2) = 20$

$T(7) = 2T(6) + 2^3 - T(3) = 47$

$T(8) = 2T(7) + 2^4 - T(4) = 107$

Now, let $M(n)$ denote the number of bit string having 4 consecutive 1's. We get

$M(0) = M(1) = M(2) = M(3) = 0, M(4) = 1$

$M(n) = 2M(n-1) + M(n-5)' \\= 2M(n-1) + 2^{n-5} - M(n-5)$

$M(5) = 2M(4) + 2^0 - M(0) = 3$

$M(6) = 2M(5) + 2^1 - M(1) = 8$

$M(7) = 2M(6) + 2^2 - M(2) = 20$

$M(8) = 2M(7) + 2^3 - M(3) = 48$

Now, we need to find the number of bit strings of length 8 containing 1111 as well as 000. We get the following 4 and their 4 reverse strings. 

11110001
11110000
01111000
11111000
 

Thus no. of bit strings of length 8 having either three consecutive 0's or 4 consecutive 1's = 107 + 48 - 8 = 147

edited by
8 votes
8 votes

Case 1: Three consecutive 0's 

             here 3 consecutive 0's can placed staring from 1,2,3,4,5,6 th places.

             000xxxxx = 25 ways

             1000xxxx= 24 ways we need to fix 1 else some string will be repeated.

             same way for other places so total ways = 32 + 5 * 16

            Below strings are repeated :

            00011000,   00010000, 00010001, 00001000, 10001000

            112 -5= 107

Case 2: Same logic applied for 4 Consecutive 1's

             Places where 4 consecutive 1's can be arranged are 1,2,3,4,5

             Total ways = 16 + 4*8 = 48

Case 3:  4 Consecutive 1's and 3 Consecutive 0's 

              00011110, 00011111,11110001, 11111000, 01111000, 00001111, 11110000,10001111 

             Total 8 strings.

Ans=107+48-8 = 147 

            

1 votes
1 votes

The negation of the statement:

(  >=3 consecutive zero's  OR  >=4 consecutive ones  )

is:

(<3 consecutive zeros   AND  <4 consecutive ones)

Now, lets find out the number of strings for the negation part.

We set up a recurrance relation.

ZER(n)

= strings of length 'n' starting with 0 or 00 and containing less than 3 zeros

= (starting is single zero).ONE(n-1) + (starting is 00).ONE(n-2)

ONE(n)

= strings of length 'n'  starting with 1 or 11 or 111 and containing less than 4 ones

= (starting with 1).ZER(n-1)  + (starting with 11).ZER(n-2) + (starting with 111).ZER(n-3)

Now, we set up the base conditions:

ZER(0)=1    

ZER(1)=1 (i.e.the string 0)

ZER(2)=2 (i.e. the string 01 and 00)

ONE(0)=1

ONE(1)=1  (i.e the string 1)

ONE(2)=2  (i.e the string 10 and 11)

Now, let the total strings of length 'n' containing less than 3 consecutive zeros and less than 4 consecutive ones

= T(n)

$\therefore$ T(n) = ZER(n) + ONE(n)

Now, we start calculating the values one by one.

T(3) = ZER(3) + ONE(3)   ............(1)

ZER(3) = ONE(2) + ONE(1) = 3

ONE(3) = ZER(2) + ZER(1) + ZER(0) = 2+1+1 = 4

(Note: If we take ZER(0)=0 then ONE(3)=3 which gives wrong answer. If I take ZER(0)=0 then the string 111 which will come under ONE(3) as ZER(0) will be counted as 0 and not 1).

$\therefore$ From (1), T(3) = 3+4 = 7

Similarly, 

T(4) = ZER(4) + ONE(4) = 5 + 6 = 12

T(5) = ZER(5) + ONE(5) = 9 + 10 = 21

T(6) = ZER(6) + ONE(6) = 16 + 17 = 36

T(7) = ZER(7) + ONE(7) = 27 + 30 = 63

T(8) = ZER(8) + ONE(8) = 47 + 52 = 109

Now, Strings containing either 3 consecutive zeros or 4 consecutive ones

= total bit strings of length 8

    - strings containing less than 3 consecutive zeros and less than 4 consecutive ones

= 28 - T(8)

= 256 - 109

= 147

edited by
1 votes
1 votes

Here we use inclusion exclusion with a bit of combinatorics..

Let n(A ∪ B) be the required no of strings which contain 3 consecutive 0's or 4 consecutive 1's..

So n(A) : no of bit strings which contain 3 consecutive 0's

    n(B) : no of bit strings which contain 4 consecutive 1's

   n(A ⋂ B) : no of bit strings which contain 3 consecutive 0's and  4 consecutive 1's

Let us find each of this :

For n(A) , we consider 3 0's as a unit and hence 6 units in total as string is of 8 characters..So we select a place for this group of 0's which can be done in               =     C(6,1)   =  6 ways

After that we can fill the remaining units with either 0 or 1 which can be done in =  25  =  32 ways

So n(A)   =   32 * 6   =  192 

Similarly  n(B)  =  C(5,1)  *  16  =  80

n(A ⋂ B)   :   C(2,1)  * 2   =  4

Hence n(A U B)   =  192 + 80  -  4

                          =  268

Hence required no of strings  =   268

Answer:

Related questions

0 votes
0 votes
0 answers
1
admin asked May 1, 2020
233 views
How many ways can n books be placed on k distinguishable shelvesif the books are indistinguishable copies of the same title?if no two books are the same, and the position...
2 votes
2 votes
1 answer
3
anumita asked May 17, 2017
390 views
How many partial functions are there from a set with m elements to a set with n elements, where m and n are positive integers.Answer : (n+1)^mHow . Can anyone please help...
2 votes
2 votes
1 answer
4
anumita asked May 17, 2017
880 views
A palindrome is a string whose reversal is identical to the string. how many bit strings of length n are palindromes ?