Question

Discrete Structures problem

numbers are b = 3 and c = 6.

Substitute your values for b and c in the questions below.

Show work for all the questions. Do enough typing to convince me you are calculating values by hand, without using a calculator.

a) How many total distinct bitstrings are there or length 9?

b)  How many bitstrings of length 9 are there with at least b zeros and fewer than c zeros?

c) How many bitstrings are there of length 9 with either fewer than b zeros or at least c zeros. Use parts a and b.

d) How many bitstrings are there of length 9 in which each '0' is immediately followed by a '1' ?

e) In what format did I deliver the lecture on RSA?

Answer 1

given, b=3 and c=6

here aCb= a combination b = a!/(a-b)!b!

in all questions bitstring lenght is 9

a) since lenght of bitstring is 9, there are 9 positions of '1's and '0's. and for each position there are two choices either '1' or '0'. so number of bitstrings = 2*2*2*2*2*2*2*2*2 (9 times correspoding to each of 9 positions).

Ans. number of bitstrings of lenght 9 = 2^9 = 512

b) number of bitstrings with atleast 3 zeros and less than 6 zeros.

= number of bitstrings with (exactly 3 zeros) + (exactly 4 zeros) + (exactly 5 zeros).

= 9C3 (chosing 3 positions out of 9 for 0 and placing 1 on other positions)   + 9C4 + 9C5 (similarly for 4 zeros and 5 zeros.)

9C3= 9!/6!3! = 7*8*9/6 =84, 9C4= 9!/5!4!= 6*7*8*9/24=126, 9C5= 126 similarly.

so Ans = 9C3+9C4+9C5= 84+126+126= 336

c) fewer than 3 zeros and atleast 6 zeros.

= number of bitstring with ( exactly 0 zeros) + ( exactly 1 zeros) + ( exactly 2 zeros) + ( exactly 6 zeros) + ( exactly7 0 zeros) + ( exactly 8 zeros) + ( exactly 9 zeros)

= 9C0+ 9C1 + 9C2 + 9C6 + 9C7 + 9C8 + 9C9

= 1 + 9 +36 + 84 + 36 + 9 + 1 =176

Ans = 176

d) bitstrings in which each '0' is immediately followed by a '1'

0 cannot be at 9th position since it cannot be followed by 1. so 9th position must be 1.

on first 8 positions each 0 is followed by 1. so there can be atmost 4 zeros. we again make cases on number of '0's.

if number of '0' is zero. then only one bitstring possible with all '1's. = 1

if number of '0' is one. then 0 can be placed at any of 8 places. = 8 btstrings

if number of '0's is two. then two '0's can be placed at any two places of 8 expect consecutive ones. = 8C2 - 7( consecutive positions) = 28-7= 21.

if number of '0's is three. = 24 ( in this case we again have to consider cases with case 1 being 1st position have zero then second must have '1' and ways of putting 2 '0's in 6 remaining position is 6C2-5. case 2 being 2nd position have '0' then 1st and third must have '1' and ways of putting 2 '0's in remaing 5 places is 5C2 - 4. case 3 being first 2 positions are '1's are third one is '0'. so ways of putting 2'0's in 4 places is 4C2-3.) adding them gives 24

if number of '0's is four. only two bitstrings possible with alternate zeros. = 2

Ans. = 1 + 8 + 21 + 24 + 2 = 56.