Construction of Permutations
Contents |
Theorem
The number of permutations ${}^nP_n$ of $n$ objects is $n!$.
Proof
The following is an inductive method of creating all the permutations of $n$ objects.
Base Case
There is clearly one way to arrange one object in order.
Inductive Hypothesis
We assume that we have constructed all $n!$ permutations of $n$ objects.
Induction Step
WLOG let a set $S_n$ of $n$ objects be $\left\{{1, 2, \ldots, n}\right\}$.
Take a permutation of $S_n$:
- $a_1 \, a_2 \, a_3 \, \ldots \, a_n$
Now we take the number $n+1$.
We can form $n+1$ permutations from this one by putting $n+1$ in all places possible:
- $a_{n+1} \, a_1 \, a_2 \, a_3 \, \ldots \, a_n, \quad a_1 \, a_{n+1} \, a_2 \, a_3 \, \ldots \, a_n, \quad a_1 \, a_2 \, a_{n+1} \, a_3 \, \ldots \, a_n, \quad \ldots, \quad a_1 \, a_2 \, a_3 \, \ldots \, a_n \, a_{n+1}$
It is clear that all permutations of $n+1$ objects can be obtained in this manner, and no permutation is obtained more than once.
As there are ${}^nP_n$ permutations on $n$ objects, there are $\left({n + 1}\right) {}^nP_n$ permutations on $n+1$ objects.
Hence by induction, and the recursive definition of the factorial:
- ${}^n P_n = n!$
