Answer the following counting questions about bit strings. What is the number of

Question

Answer the following counting questions about bit strings. What is the number of 0/1 bit strings with 20 "0"s and 5 "1"s, so that there are no adjacent "1"s? (b) You want to count the number of 0/1 bit strings with 15 "0"s and 4 "1"s, so that between every two "l"s there are at least two "0"s. You want to count the number of bit strings of length 10 that contains 4 consecutive "1"s, c.g. 0001111110, 0011110010. Barry Bruin proposes the following: There are 7 possible starting positions of 4 consecutive "1"s, (it cannot start at the last 3 positions). Once we know where are the 4 consecutive "l"s, the remaining 6 bits can be either 0 or 1. Hence the answer should be 7 "middot 2^6. Explain why Barry Bruin is wrong, and calculate the correct answer.

Explanation / Answer

A)

Lets lay down all 0s

_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_

So there are 21 spaces around 0s where 1s can come.

so, 21C5 possibilities

Ans is 21C5 = 20349 bitstrings

B)

Between every 2 1s there should be atleast 2 0s

Lets make a string of 1001001001

so now we have 9 more 0s to fit in

they can go anywhere between/before/after the 1s

_ _ _ _ _ _ _ _ _ 1 0 0 _ _ _ _ _ _ _ _ _ 1 0 0 _ _ _ _ _ _ _ _ _ 1 0 0 _ _ _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ _ _

so we have 45 blank spaces of which 9 have to be chosen

So there are 45C9 possibilities.

Ans: 45C9 = 886163135 possibilities

C)

In the above solution for part c), several combinations are being double counted.

For example when we have 1111_ _ _ _ _ _ , the combination 1111100000 is counted

Then with 1111s at 2nd position, we have _1111_ _ _ _ _ , the combination 1111100000 is again counted.

To avoid this,

Lets start with 1st position,

1111_ _ _ _ _ _, the remaining 6 bits can be either 0 or 1, so 26 possibilities.

Now, we have already considered 1 at first position, so for all other starting positions, we consider combination of 01111

so,

01111_ _ _ _ _

_ 01111_ _ _ _

_ _ 01111_ _ _

_ _ _ 01111_ _

_ _ _ _ 01111_

_ _ _ _ _ 01111

so we have 6 x 2 5 combinations,

total combinations = 26+ 6. 25

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---