How many 9-bit strings are there which:
a) Start with the sub-string 101?There are 2 ways to choose each of of the 6 remaining bits,
so the answer to a) is 26 = 64
b) Have weight 5 and start with 101?Since 101 has weight 2, the last 6 bits must contain 3 1's
There are "6 places choose 3" or 6C3 = 20
c) Have weight 5 or start with 101?Case 1: Have weight 5.
From the 9 places to have digits, there are 5 places to
have 1's.
That's "9 choose 5" = 9C5 = 126
Case 2: Start with 101
That's problem a), or 64
Case 3. Have weight 5 and start with 101.
That's problem b), or 20
Let A = the set of 9-bit strings with weight 5.
Let B = the set of 9-bit strings that start with 101.
N(A or B) = N(A)+N(B)-N(A and B)
N(A or B) = 126+64-20 = 170
Edwin
