# How many bit strings have…

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.

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?

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.

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

• Thanks a lot guys for the quick response guys. much appreciation – Ñach Huidobro Dec 21 '15 at 11:20
• @ÑachHuidobro: I'm just one guy. – barak manos Dec 21 '15 at 12:28