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

Informal Proof

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 second element.

And so on, to the $r$th element of our selection: we now have $n - \left({r-1}\right)$ 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$:

$n \left({n-1}\right) \left({n-2}\right) \ldots \left({n-r+1}\right) = \dfrac {n!} {\left({n - r}\right)!}$

This is made more rigorous in Construction of Permutations.

Formal Proof

From the definition, an $r$-permutations 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$

Sources

• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 3.6$: Example $54$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 1.6$
• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.5$
• Ian D. Macdonald: The Theory of Groups (1968): Appendix