0
$\begingroup$

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?

$\endgroup$
0
$\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.

| cite | improve this answer | |
$\endgroup$
0
$\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}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot guys for the quick response guys. much appreciation $\endgroup$ – Ñach Huidobro Dec 21 '15 at 11:20
  • 2
    $\begingroup$ @ÑachHuidobro: I'm just one guy. $\endgroup$ – barak manos Dec 21 '15 at 12:28

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.