3
$\begingroup$

How many subsets of size 4 of the set S={1,2,....20} contain at least 1 of the elements 1,2,3,4,5?

$${5 \choose 4}{15 \choose 0}+{5 \choose 3}{15 \choose 1}+{5 \choose 2}{15 \choose 2}+{5 \choose 1}{15 \choose 3} + \binom50 \binom{15}4$$

5 "special elements"
15 "regular elements"

Is my answer correct?

$\endgroup$
  • $\begingroup$ Look at the last two terms again, I think you meant something different. $\endgroup$ – AlexR Feb 2 '15 at 23:29
  • $\begingroup$ ah yea typos! besides that its ok? $\endgroup$ – Math Major Feb 2 '15 at 23:30
  • 2
    $\begingroup$ ... Contain at least one element. You'll want to drop the last term. The rest is fine. $\endgroup$ – AlexR Feb 2 '15 at 23:31
  • $\begingroup$ oh righ thanks! $\endgroup$ – Math Major Feb 2 '15 at 23:33
  • $\begingroup$ You'll want to accept Meelo's answer then since there's nothing more to add. Note that {n \choose k} is superseeded by \binom{n}{k} for syntactical reasons ;) $\endgroup$ – AlexR Feb 2 '15 at 23:34
3
$\begingroup$

Your answer is almost correct - the last term is confusing and also wrong. Consider that any subset of size $4$ containing at least one of the $5$ special elements can be partitioned into a subset $S$ of special elements (of size $1$ through $4$) and a subset $R$ of regular elements (of size $0$ through $3$). Thus, the correct answer would simply be: $${5\choose 4}{15\choose 0}+{5\choose 3}{15\choose 1}+{5\choose 2}{15\choose 2}+{5\choose 1}{15\choose 3}$$ where we take the sum over the possible sizes of $S$ and $R$. This is basically what you have, except without the confusing last term, which would seem to represent the case if $S$ had size $0$ - which is not a case we are interested in - that case represents have no special elements.

$\endgroup$
3
$\begingroup$

The complementary subsets – those of size $4$ which contain none of $1,2,3,4,5$ are $\displaystyle \binom{15}{4}$, and there are $\displaystyle \binom{20}{4}$ subsets of size $4$ in all. Hence the number of subsets of size $4$ which contain at least one of these numbers is equal to

$$\binom{20}{4}-\binom{15}{4}=\frac{20!}{4!\,16!}-\frac{15!}{4!\,11!}=3480.$$

$\endgroup$

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.