Im currently studying for my final exams and I am currently stuck in this problem. I Could someone give me some tips on how to solve them?
I know the answer for the first one is $C(10,4)$, However I have no idea why. Thanks.
$\endgroup$How many bit strings of length 10 contain:
a) Exactly four 1s? b) At most four 1s? c) At least four 1s? d) An equal number of 0s and 1s?
2 Answers
$\begingroup$You have a string $x\in\{0,1\}^{10}$. For it to have exactly 4 ones, you need to select exactly 4 distinct indices (positions) out of 10, write a $1$ in these four positions and a $0$ in every one of the 6 others.
Therefore, the number of such bit strings is exactly the number of sets of exactly 4 elements out of 10. This is $\binom{10}{4}$ (i.e., $C(10,4)$) by definition:
Another occurrence of this number is in combinatorics, where $\binom{n}{k}$ gives the number of ways, disregarding order, that $k$ objects can be chosen from among $n$ objects; more formally, the number of $k$-element subsets (or $k$-combinations) of an $n$-element set.
The same type of reasoning should help you to solve the others: for instance, "at most four ones" means "exactly 0 ones, or exactly 1 one, or exactly 2 ones, or exactly 3 ones, or exactly 4 ones." So you can apply the previous reasoning to each "exactly $k$ ones" and sum the possibilities.
$\endgroup$ $\begingroup$Use this in order to answer (a) and (d):
The number of bit strings containing exactly $m$ ones out of $n$ bits:
$$\binom{n}{m}$$
Use this in order to answer (b):
The number of bit strings containing at most $m$ ones out of $n$ bits:
$$\sum\limits_{k=0}^{m}\binom{n}{k}$$
Use this in order to answer (c):
The number of bit strings containing at least $m$ ones out of $n$ bits:
$$\sum\limits_{k=m}^{n}\binom{n}{k}$$
$\endgroup$ 2
