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

Then the number of $r$-permutations of $S$ is:

- ${}^r P_n = \dfrac {n!} {\left({n - r}\right)!}$

When $r = n$, this becomes:

- ${}^n P_n = \dfrac {n!} {\left({n - n}\right)!} = n!$

Using the falling factorial symbol, this can also be expressed:

- ${}^r P_n = 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 ${}^r P_n$ on a set of $n$ elements is given by:

- ${}^r P_n = \dfrac {n!} {\left({n-r}\right)!}$

From this definition, it can be seen that a bijection $f: S \to S$ is an $n$-permutation.

Hence the number of $n$-permutations on a set of $n$ elements is:

- ${}^n P_n = \dfrac {n!} {\left({n - n}\right)!} = n!$

$\blacksquare$