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!!
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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.
answered Sep 27 '14 at 20:14
