Answer to Question #307159 in Discrete Mathematics for Ash

Question

How many 9-bit strings (that is, bit strings of length 9) are there which:

(a) Start with the sub-string 101? Explain.

(b) Have weight 5 (i.e., contain exactly five 1’s) and start with the sub-string 101? Explain.

(c) Either start with 101 or end with 11 (or both)? Explain.

(d) Have weight 5 and either start with 101 or end with 11 (or both)?Explain

Answer 1

Solution (a)

There are 9-bits, and we start with 101. It means there are 6 remaining bits.

Therefore, there will be $2^6 = 64$ strings (9-bits strings) 

Solution (b)

Given the weight of the string is 5 and since it starts with 101, and has a total of 5 1’s, it means the last 6-bits must have three 1’s.

So, there will be 6 places out of which three will be occupied by three 1’s. So, there will be $6C3$, strings (9-bits string) starting with 101 and will have weight equal to 5. 

Solution (c)

Let us consider the string starts with 101.

Then there will be $2^6 = 64$ strings (9-bits strings)

 

Let us consider the string ends with 11.

Then there will be $2^7 = 128$ strings (9-bits strings)

 

When the string starts with 101 and ends with 11, then there will be $2^4 = 16$ strings (9-bits strings) 

Solution (d)

 

If the 9-bits string has a weight of 5, then

From the 9 places to have digits, there are 5 places to have 1's.

Therefore, there will be 9C5 = 126 strings (9-bits strings)

n(A) = 9C5 = 126 strings (9-bits strings)

  

The string starts with 101 and has a weight of 5. Then there will be 6C3 =20 strings (9-bits strings)

That is 

Then there will be 20 strings (9-bits strings)

 

Now when the strings start with 101, ends with 11 and have the weight 5, we will have

$n(A or B) = n(A) + n(B) – n(A and B)\\$

$n(A or B) = 126 + 64 – 20$

$n(A or B) = 170$