Number of Permutations/Proof 2
Jump to navigation
Jump to search
Theorem
Let $S$ be a set of $n$ elements.
Let $r \in \N: r \le n$.
The number of $r$-permutations of $S$ is:
- ${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
Using the falling factorial symbol, this can also be expressed:
- ${}^n P_r = n^{\underline r}$
Proof
From the definition, an $r$-permutation of $S$ is an ordered selection of $r$ elements of $S$.
It can be seen that an $r$-permutation is an injection from a subset of $S$ into $S$.
From Cardinality of Set of Injections‎, we see that the number of $r$-permutations ${}^n P_r$ on a set of $n$ elements is given by:
- ${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
$\blacksquare$