0
$\begingroup$

I want to show that the number of subsets of cardinality $p$ of a set $E$ of cardinality $n$ is ${n \choose p}$. I've read a proof that I couldn't understand it basically says that for any injection $f:\{1,..,p\}\to E$ there is a subset of cardinality $p$ which is $\{f(1),\cdots , f(p)\}$ and in the other direction any $p$-subset $\{e_1,\cdots,e_p\}$ of $E$ is the image of $\{1,\cdots,p\}$ of $p!$ distinct injections. Hence the result. Is there a way to clarify this or to write another proof by constructing a bijection between the set of $p$-subsets of $E$ and some other set for which we can simply compute the cardinality ? thank you for your help!!

$\endgroup$
  • $\begingroup$ How did you define $\binom{n}{p}$? $\endgroup$ – Najib Idrissi Sep 27 '14 at 13:26
  • $\begingroup$ It is $\dfrac{n!}{p!(n-p)!}$ $\endgroup$ – palio Sep 27 '14 at 13:59
0
$\begingroup$

Order all $n$ elements of your set, and take the first $p$ as your subset. This clearly generates all $p$-size subsets. There are $n!$ ways to order the set. The order of the last $n-p$ many does not matter, nor does the order of the first $p$ matter; this will give the exact same subset. So $n!$ counts every effective subset $p! (n-p)!$ times, so we divide by that to get the right number. Which is ${n \choose p}$ in your definition.

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