Cardinality of Set of Subsets/Proof 1

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a set such that $\card S = n$.

Let $m \le n$.


Then the number of subsets $T$ of $S$ such that $\card T = m$ is:

${}^m C_n = \dfrac {n!} {m! \paren {n - m}!}$


Proof

For each $X \subseteq \N_n$ and $Y \subseteq S$, let $B \left({X, Y}\right)$ be the set of all bijections from $X$ onto $Y$.

Let $\Bbb S$ be the set of all subsets of $S$ with $m$ elements.

By Cardinality of Power Set of Finite Set and Cardinality of Subset of Finite Set, $\Bbb S$ is finite, so let $s = \left|{\Bbb S}\right|$.

Let $\beta: B \left({\N_n, S}\right) \to \Bbb S$ be the mapping defined as $\forall f \in B \left({\N_n, S}\right): \beta \left({f}\right) = f \left({\N_m}\right)$.


For each $Y \in \Bbb S$, the mapping:

$\Phi_Y: \beta^{-1} \left({Y}\right) \to B \left({\N_m, Y}\right) \times B \left({\N_n - \N_m, S - Y}\right)$

defined as:

$\Phi_Y \left({f}\right) = \left({f_{\N_m}, f_{\N_n - \N_m}}\right)$

is also (clearly) a bijection.


By Cardinality of Set of Bijections:

$\left|{B \left({\N_m, Y}\right)}\right| = m!$

and:

$\left|{B \left({\N_n - \N_m, S - Y}\right)}\right| = \left({n - m}\right)!$

So by Cardinality of Cartesian Product:

$\left|{\beta^{-1} \left({Y}\right)}\right| = m! \left({n - m}\right)!$

It is clear that $\left\{{\beta^{-1} \left({Y}\right): Y \in \Bbb S}\right\}$ is a partition of $B \left({\N_n, S}\right)$.

Therefore by Number of Elements in Partition:

$\left|{B \left({\N_n, S}\right)}\right| = m! \left({n - m}\right)! s$

Consequently, as $\left|{B \left({\N_n, S}\right)}\right| = n!$ by Cardinality of Set of Bijections, it follows that:

$m! \left({n - m}\right)! s = n!$

and the result follows.

$\blacksquare$


Sources