retagged by
8,874 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

1 votes
1 votes

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

edited by
0 votes
0 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
0 votes
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

0 votes
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$

edited by
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
392 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
882 views
A palindrome is a string whose reversal is identical to the string. how many bit strings of length n are palindromes ?