The Gateway to Computer Science Excellence
+2 votes
553 views

How many bit strings of length ten either start with a $1$ bit or end with two bits $00$ ?

  1. $320$
  2. $480$
  3. $640$
  4. $768$
in Combinatory by
edited by | 553 views
0
Ans $3)$

using inclusion-exclusion

2 Answers

+3 votes

Answer - (3) 640

 

The problem can be divided into two parts,

Part 1 - No. of bit strings of length 10 that start with bit 1.

So, the strings will be of the form

1 _ _ _ _ _ _ _ _ _

which means $9$ empty places to fill with either $0$ or $1$, hence $2^9$ ways.

 

Part 2 - No. of bit strings of length 10 that end with two bit zeros. 

Now, we have already counted the strings that end with two bit zeros in the part 1, but all those strings were starting with a bit 1. So, we still haven't counted the bit strings that start with a zero, and end with two zeroes. So, such strings will be of the form 

0 _ _ _ _ _ _ _ 0 0

which means 7 empty places to fill with either 0 or 1, hence $2^7$ ways.

Hence, total no. of ways = Part 1 + Part 2 (because OR)

$ = 2^9 + 2^7$

$ = 2^7 (2^2 + 1)$

$ = 2^7 (5) = 640$

 

One more way to solve this would be,

Let, $N_A$ = No. of bit strings of length 10 that start with 1 = $2^9$

$N_B$ = No. of bit strings of length 10 that end with two zeros = $2^8$ 

So, $N_{A \cap B}$ = No. of bit strings of length 10 that start with 1 and end with two zeros = $2^7$

Now, by inclusion-exclusion principle, 

No. of bit strings of length 10 that start with 1 OR end with two zeros,

$N_{A \cup B} = N_A + N_B - N_{A \cap B} = 2^9 + 2^8 - 2^7 = 2^7 (4 + 2 - 1) = 2^7 \cdot 5 = 640.$

by
+1 vote

According to the principle  of mutual inclusion-exclusion:

The number of strings either start with a $1$ bit or end with two bits $00 = 2^{9}+2^{8}-2^{7} = 640$

by
edited by
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
52,345 questions
60,517 answers
201,937 comments
95,368 users