Cardinality of Set of Subsets/Proof 2

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:

$\dbinom n m = \dfrac {n!} {m! \paren {n - m}!}$

Let $\dbinom n m$ denote the number of subsets of $m$ elements of $S$.

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

Consider the way ${}^m P_n$ can be calculated.

First one makes the selection of which $m$ elements of $S$ are to be arranged.

This number is $\dbinom n m$.

Then for each selection, the number of different arrangements of these is $m!$, from Number of Permutations.

So:

$\ds m! \cdot \dbinom n m$

$=$

$\ds {}^m P_n$

$\ds $

$=$

$\ds \frac {n!} {\paren {n - m}!}$

$\ds \leadsto \ \ $

$\ds \dbinom n m$

$=$

$\ds \frac {n!} {m! \paren {n - m}!}$

$\blacksquare$