Question

How many 10-bit strings are there which: (a) Have weight 4?
|(b) Have weight 4 and start with the substring 101?
|(c) Have weight 5 and start with 101 or end with 11 (or both)?|

Answer 1

Answer:

(a) 210

(b) 21

(c) 86

Step-by-step explanation:

(a)

We need to find how many 10-bit strings there are with only 4 bits = 1.

As the order does not matter, this number is a combination of 10 bits taken 4 at a time (those that are equal to 1)

$\binom{10}{4}=\frac{10!}{(10-4)!4!}=\frac{10!}{6!4!}=\frac{10.9.8.7.6!}{6!4!}=\frac{10.9.8.7}{4.3.2}=210$

So, there are 210 10-bit strings of weight 4

(b)

As the 10-bit strings start with 101, we need a 7-bit tail with only 2 bits =1.

The order does not matter, so this a combination of 7 taken 2 at a time

$\binom{7}{2}=\frac{7!}{(7-2)!2!}=\frac{7!}{5!2!}=\frac{7.6.5!}{5!2!}=\frac{7.6}{2}=\frac{42}{2}=21$

And there are 21 10-bit strings of weight 4 starting with 101

(c)

Let's compute first the number of 10-bit strings starting with 101 and having weight 5.

In this case, we need a 7-bit tail with only 3 bits =1.

$\binom{7}{3}=\frac{7!}{(7-3)!3!}=\frac{7!}{4!3!}=\frac{7.6.5.4!}{4!3!}=\frac{7.6.5}{3.2}=7.5=35$

Now, the 10-bit strings ending with 11. In this case, we need a 8-bit string with only 3 bits =1.

$\binom{8}{3}=\frac{8!}{(8-3)!3!}=\frac{8!}{5!3!}=\frac{8.7.6.5!}{5!3!}=\frac{8.7.6}{3.2}=8.7=56$

The number of 10-bit strings of weight 5 starting with 101 or ending with 11,  would be 35+56 subtracting the strings starting with 101 and ending with 11, which were counted twice.

But these are 5-bit strings with only 1 bit =1, and there are 5.

So, the number of 10-bit strings of weight 5 starting with 101 or ending with 11 or both is

35+56-5 = 86.