Kenneth Rosen Edition 6 Question 45 (Page No. 346)

Question

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

Comments

it seems more like DLD.

---

Is the answer 245?

---

ans 147

---

@srestha They have asked for no. of strings. How are you getting fraction?

---

ohh yes

then will be 2*2!=4

---

The answer is most probably 147 according to this

---

00001111

00011111

11111000

11110000

01111000

10001111

00011110

11110001

these are I am getting by hand

what will be more than this?

---

@srestha The question uses "OR" and not "AND"

---

$2^{5}+2^{4}-8=40$

---

@minipanda, what's your doubt in the answer provided by the link ?

---

I didn't understand the approach..a different way would be better..or else can you please elaborate the same..?

---

can u plz chk anything missing

---

@Arjun

sir, can you check these answers ?

and i want to know, is there any other approach to this question ?

---

This is one of the lengthy question. I still got different solution with different approach. Plz correct me if something missing

---

@ Shaikh bro superbb explaination

Answer 1

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

Comments

@Arjun-Sir here $M(n-5)$ would represent all bit strings of length $n-5$ not containing $1111$ and to this we add $01111$ to get bit strings of length n which contain 4 consecutive one's.

Am I correctly getting it?

 

---

Thank you very much. I still don’t get the two cases intriduced for $n-1$ and $n-4$?

---

Recurrence Relation for Number of Bit Strings of length n Containing Three Consecutive 0’s: https://www.youtube.com/watch?v=3DIsc2LgU1E&list=PLIPZ2_p3RNHhhTH0o1JBMgscMUvxs4E_4&index=6 

Answer 2

Case 1: Three consecutive 0's 

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

             000xxxxx = 2⁵ ways

             1000xxxx= 2⁴ 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 

            

Comments

why not solve this problem in inclusion-exclusion principle

---

Solution based on inclusive -exclusive principle only ..

---

How can you identify  that only these strings are repeated 00011000,   00010000, 00010001, 00001000, 10001000 i am not getting this can you please explain????

---

00010000

you have counted this as part of the 147 , which is your answer , but this is not a valid string as this contains 4consecutive zero substring .
Am i right , is my understanding of the question correct.

Answer 3

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

= 2⁸ - T(8)

= 256 - 109

= 147

Answer 4

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 =  2⁵  =  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

Comments

Total number of binary strings of length 8 is 256. How can the answer exceed that? and for every case of positioning 000 ( 6 cases)  u consider the possibility of all other bits being 0 which means counting the string 00000000 6 times.