# Number of Permutations

## 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 1 (Informal)

We pick the elements of $S$ in any arbitrary order.

There are $n$ elements of $S$, so there are $n$ options for the first element.

Then there are $n - 1$ elements left in $S$ that we haven't picked, so there are $n-1$ options for the second element.

Then there are $n - 2$ elements left, so there are $n - 2$ options for the third element.

And so on, to the $r$th element of our selection: we now have $n - \paren {r - 1}$ possible choices.

Each mapping is independent of the choices made for all the other mappings, so by the Product Rule for Counting, the total number of ordered selections from $S$:

\(\displaystyle {}^r P_n\) | \(=\) | \(\displaystyle n \paren {n - 1} \paren {n - 2} \cdots \paren {n - r + 1}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle n \paren {n - 1} \paren {n - 2} \ldots \paren {n - r + 1} \dfrac {\paren {n - r}!} {\paren {n - r}!}\) | multiplying top and bottom by $\paren {n - r}!$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \dfrac {n!} {\paren {n - r}!}\) | simplifying the numerator |

$\blacksquare$

## Proof 2 (Formal)

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$

## Examples

### $4$ from $52$

The number of ways of choosing $4$ objects in order from a set of $52$ (for example, cards from a deck) is:

- ${}^4 P_{52} = 52 \times 51 \times 50 \times 49 = \dfrac {52!} {48!} = 6 \, 497 \, 400$

## Sources

- 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $24$ - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $24$