How many bitstrings of length 10 have the following property:

193 Views Asked by At

How many bitstrings of length 10 have the following property:

a) sum of first $5$ bits are $3$?

b) sum of first $5$ bits equals sum of last $5$ bits?

c) the bits are written in increasing order (no $0$ after $1$)?

d) first and last bits are identical?

I guess the answer on a) is $C_5^3 \cdot 2^5 $ because we get 5 arbitrary positions and we need 3 $1$'s at the start and the answer on d) is $2^9$ because we have 8 arbitrary positions $2$ times for $0$ then $1$.

If those are correct, how to approach b) and c) ?

1

There are 1 best solutions below

0
On BEST ANSWER

Your solutions to the first and last question are correct. To solve the second question, we can divide the string in two parts. The number of ways to arrive at a sum of $n$ for each part equals ${5 \choose n}$, and the number of possible strings thus equals:

$$\sum_{i=0}^{5} {5 \choose i} {5 \choose i} = 1 \cdot 1 + 5 \cdot 5 + 10 \cdot 10 + 10 \cdot 10 + 5 \cdot 5 + 1 \cdot 1 = 252$$

To solve the third question, we only have to choose the number of $0$s, since the remaining $1$s are then put at the end of the string. The number of possible strings thus equals:

$$\sum_{i=0}^{10}1 = 11$$