Cardinality of Set of Subsets

Theorem

Let $S$ be a set such that $\left|{S}\right| = n$.

Then if $m \le n$, the number of subsets $T$ of $S$ such that $\left|{T}\right| = m$ is $\dfrac {n!} {m! \left({n - m}\right)!}$

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

Also see

This expression crops so often in mathematics it has been given a special notation.

For all $m, n \in \N$, the number of subsets of $m$ elements of a set having $n$ elements is defined as:

$\displaystyle \forall m, n \in \N: \binom n m = \begin{cases} \frac {n!} {m! \left({n - m}\right)!} & : m \le n \\ 0 & : m > n \end{cases}$

The number $\displaystyle \binom n m$ is known as a binomial coefficient.

The reason for this is apparent from the Binomial Theorem.

Sources

• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 2.3$: Example $35$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $5.4$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 19$: Theorem $19.8$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.6$: Theorem $8: \ 3$
• George E. Andrews: Number Theory (1971): $\S 3.1$: Theorem $3.2$