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) ?


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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.