The Gateway to Computer Science Excellence
+8 votes
2.4k views
How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?
in Combinatory by Loyal (5.8k points)
retagged by | 2.4k views
0

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

0
ohh yes

then will be 2*2!=4
0

The answer is most probably 147 according to this

0
00001111

00011111

11111000

11110000

01111000

10001111

00011110

11110001

these are I am getting by hand

what will be more than this?
0

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

0
$2^{5}+2^{4}-8=40$
0
@minipanda, what's your doubt in the answer provided by the link ?
0
I didn't understand the approach..a different way would be better..or else can you please elaborate the same..?
0
can u plz chk anything missing
0

@Arjun

sir, can you check these answers ?

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

0

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

0
@ Shaikh bro superbb explaination

8 Answers

+13 votes
Best answer

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

by Veteran (431k points)
edited by
0

@Arjun, could you tell whats missing in the recurrance I have set up here?

0
@Arjun. Got the mistake.....initial base condition.
0

@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?

 

+6 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 

            

by Boss (25.7k points)
0
why not solve this problem in inclusion-exclusion principle
0
Solution based on inclusive -exclusive principle only ..
+1
How can you identify  that only these strings are repeated 00011000,   00010000, 00010001, 00001000, 10001000 i am not getting this can you please explain????
+1 vote

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

by Boss (18.5k points)
edited by
+1 vote

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

by Veteran (102k points)
+3
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.
+1 vote

How many bit strings of length eight contain 3 consecutive 0's or 4 consecutive 1's?

As we go with Mutual Inclusion and Exclusion principle :

| A ∪ B | = | A | +| B | - | A ∩ B | 

A --- bit strings of length eight contain 3 consecutive 0's

B --- bit strings of length eight contain 4 consecutive 1's

 

Coming to |A| :- bit strings of length eight contain 3 consecutive 0's

total eight positions, in which 3 are fixed to 0's and remaining are have 2 chocies = 2$^5$.

But those 3 zero's are should be contiguous ==> 3 contiguous locations in 8 locations = 8-3+1 = 6.

i) 000 _ _ _ _ _

ii) _ 000 _ _ _ _

iii) _ _ 000  _ _ _

iv) _ _ _000 _ _

v) _ _ _ _000 _

vi) _ _ _ _ _000

So total = 6 * 2$^5$, But note that there are some sequences which may over counted !

So we have to subtract some count from  6 * 2$^5$.

 

let think consecutive zero's of length 4 :- 0000 _ _ _ _

this can be look as ${\color{Red}{000}} 0 \_\; \_\; \_\; \_\;$ or $ 0 \color{Magenta}{000}  \_\; \_\; \_\; \_\;$

these type of sequences counted twice, we have to remove one of the sequences.

those 4 contiguous locations in 8 locations = 8-4+1 = 5.

total of 4 length = 5 * 2$^4$.

 

let think consecutive zero's of length 5 :- 00000 _ _ _

this can be look as $ \color{red}{000} 0 0  \_\; \_\; \_\; $ or $ 0 {\color{Magenta}{000}} 0 \_\; \_\; \_\; $ or $ 0 0 \color{green}{000} \_\; \_\; \_\; $

these type of sequences counted thrice, we have to remove two of the sequences, But wait !

all those extra sequences are covered in " consecutive zero's of length 4 "  ! 

So, don't worry about them !!

So, no need to worry about 5,6,7,8 lengths to subtract !

 

But note that, if more than 2 groups of consecutive three 0's exist in the sequence ?

i mean to say,

i)  000 __ __ 000 ===> this counted twice due to visualizing it as $ \color{red}{000}  \_\; \_\; \_\; \_\;$ or $ \_\; \_\; \_\; \_\; \color{Magenta}{000} $

these type of sequences are over counted, so need to subtract for the original sum ! 

0 0 0 $\color{red}{\_}\;\; \color{Magenta}{\_} $ 0 0 0, for having two groups, there must be atleast one 1 should be present .

if i place 1 in red blank ==> Magenta blank can be 0 or 1. ===> 2 possibilities

if i place 1 in Magenta blank ==> red blank can be 0 ( but 1 is already counted in previous case ) ===> 1 possibilities

ii) _ 000 _ 000 ===> _ 000 1 000 ==> the blank can be 1 ( but 0 is already counted in previous case ) 

iii) 000 _ 000 _ ===> 000 1 000 _  ==> the blank can be 1 ( but 0 is already counted in previous case ) 

Total = 2+1+1+1 = 5

 

|A| = 6 * 2$^5$ -  5 * 2$^4$ - 5 = 6*32 - 5*16 - 5 = 192 - 80 - 5 = 107

 

Coming to |B| :- bit strings of length eight contain 4 consecutive 1's

total eight positions, in which 4 are fixed to 1's and remaining are have 2 chocies = 2$^4$.

But those 4 one's are should be contiguous ==> 4 contiguous locations in 8 locations = 8-4+1 = 5.

So total = 5 * 2$^4$, But note that there are some sequences which may over counted !

So we have to subtract some count from  5 * 2$^4$.

 

let think consecutive one's of length 5 :- 11111 _ _ _

this can be look as $ \color{red}{1111} 1  \_\; \_\; \_\; $ or $ 1 \color{Magenta}{1111}  \_\; \_\; \_\; $

these type of sequences counted twice, we have to remove one of the sequences.

those 5 contiguous locations in 8 locations = 8-5+1 = 4.

total of 5 length = 4 * 2$^3$.

 

let think consecutive zero's of length 6 :- 111111 _ _

this can be look as $ \color{red}{1111} 1 1  \_\; \_\;$ or $ 1 \color{Magenta}{000} 0 \_\; \_\;$ or $ 1 1  \color{green}{1111} \_\; \_\; $

these type of sequences counted thrice, we have to remove two of the sequences, But wait !

all those extra sequences are covered in " consecutive zero's of length 5 "  ! 

So, don't worry about them !!

So, no need to worry about 6,7,8 lengths to subtract !

 

is there any chance like that in previous case ?

But note that, if more than 2 groups of consecutive three 0's exist in the sequence ?

1111 _ 1111 ==> it leads to minimum length = 9 ===> don't worry about it !

|B| = 5 * 2$^4$ -  4 * 2$^3$ = 5*16 - 4*8 = 80-32 = 48

 

Coming to | A ∩ B |  :- bit strings of length eight contain 4 consecutive 1's 

total eight positions, in which 4 are fixed to 1's and 3 are fixed to 0's ==> only one bit is left.

i)  _ 000 1111 ( don't worry about the order of zero's and ones's )

ii)  000 _ 1111 ( don't worry about the order of zero's and ones's )

iii)  000 1111 _ ( don't worry about the order of zero's and ones's )

there for only 4 possible sequences without worrying of order

but in a sequence, either three 0's then four 1's or four 1's then three 0's orders are possible = 2.

Total = 4 * 2 = 8

 

Required answer = 107 + 48 - 8 = 107 + 40 = 147

by Veteran (65.7k points)
edited by
0

those 4 contiguous locations in 8 locations = 8-4+1 = 5.

 havenot got this equation

why 8-4?

0

by taking some examples you can understood why it is 8-4+1,

here 8 represents total length, 4 represents contiguous locations.

0

@Shaik Masthan

I have a doubt

if we take string 00001111

then which string counting twice?

0

@Shaik 

@MiNiPanda

plz chk my ans

0 votes

You can use this recurrence fn too;

T(n)=T(n-1)+T(n-2)+T(n-3)+2n-3

for three consecutive 0's

M(n)=M(n-1)+M(n-2)+M(n-3)+M(n-4)+2n-4

for four consecutive 1's

by Junior (579 points)
0 votes

In case of $3$ consecutive $0$

$0$    $0$   $0$   _   _    _   _    _      $=2^{5}=32$............................Case $1$

$1$    $0$    $0$  $0$   _   _    _   _    $=2^{4}=16$

_    $1$    $0$    $0$  $0$   _   _    _    $=2^{4}=16$

_    _.   $1$    $0$    $0$  $0$   _   _    $=2^{4}=16$.


_    _    _.   $1$    $0$    $0$  $0$   _     $=2^{4}=16-2=14$

[The cases same repeating as Case $1$ is 0 0 0 1 0 0 0 _=2 cases need to subtract]..........................Case $5$

_    _.    _    _   $1$    $0$    $0$  $0$    $=2^{4}=16-2=14$[can repeat in some cases as 1st and 5th like 00011000,00001000]

Now for $4$ consecutive $1$

$1$ $1$ $1$ $1$ _ _ _ _ $=2^{4}=16$

$0$ $1$ $1$ $1$ $1$ _ _ _  $=2^{3}=8$

_  $0$ $1$ $1$ $1$ $1$ _ _ $=2^{3}=8$

_   _  $0$ $1$ $1$ $1$ $1$ _  $=2^{3}=8$

_   _   _  $0$ $1$ $1$ $1$ $1$   $=2^{3}=8$
 

 

So, total $32+16+16+16+14+14+16+8+8+8+8=156-8$(This 8 subtracting when both 000 and 1111 present in string that is coming $2$ times while we counting)$=148$

by Veteran (119k points)
edited by
0

your case 2:- 1 0 0 0 _ _ _ _

have intersect with case 6 :- _ _ _ _ 1 0 0 0

that one possibility, you have to discard from total.

 

What is that string in common ?

1 0 0 0 1 0 0 0

0
my method is same as papesh done

I missed one

but still thinking why 000100000 will be subtracted from case 6?
0

but still thinking why 000100000 will be subtracted from case 6?

didn't get this, 0001000_ ------> subtracted from case 5, right ? 

0
no, it is added by case 5
0
mam, i didn't get your comments on this
0 votes

I have found Number of bit string with 


(1) (i)zero consecutive $0.$
(ii) one $0$
(iii) two  consecutive zero

or

(2)(i) zero consecutive 1s
(ii) one $1$
(iii) two consecutive $1's$
(iv)three consecutive $1's$



Now,

for (1)(i) I got $1$ string
 
(ii)$4$ string eliminated duplicates

(iii) $7+5+3+1=16$ string

(iv) we can arrange like (2,1) in two places or (1,1,1) in $3$ places


In 1st one I got 4+3+2+1=10 strings

In 2nd one I got 4+2+(5*4/2)=12 strings

Now we can take four $0's$ and arrangement will be (2,2), so that no three consecutive 

Here I got 4+2=6 strings

Again I can take five consecutive $0's$ and arrangement will be like (2,2,1)

Here I got 2 strings

And lastly I can take six $0's$, arrangement will be like (2,2,2), here I got $1$ string

So, total 52 strings
 


Now for $1's$

2)(i) that is string with no $1's=1$ string

(ii) string with one $1's$=4 string

(iii) No. of string with three $1's$

Arrangement can be (1,1,1), and there are $6+5+4=15$ strings

Arrangement can be (1,2) and there will be 4+3=7 strings

(:)Now  if there are four $1's$ and their arrangement will be (3,1) or arrangement (2,2)

there will be (9+7)=16 strings

(:) If there are five $1's$ arrangement will be like (3,2) or (2,2,1)

There will be 6+3=9 strings

(:) If there are  six 1's arrangement will be (2,2,2) or (3,3) 

There will be $16$ strings

Total $68$ strings


Now total string-(All previous string ) coming 136

by Veteran (119k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,367 answers
198,501 comments
105,271 users