Proof: For any integer $n$ with $n \ge 1$, the number of permutations of a set with $n$ elements is $n!$.

Question

I am trying to use mathematical induction to prove the following theorem:

For any integer $n$ with $n \ge 1$, the number of permutations of a set with $n$ elements is $n!$.

---

Proof

Let $P(n)$ be the above statement.

Take the set of elements $\{ x_1, x_2, \dots, x_n \mid n \ge 1 \}$.

$P(1)$ holds because the number of permutations of $1$ element is size $1$ and $1! = 1$.

Now assume that $P(n)$ is true for some $n = m \ge 1$.

$P(m + 1)$ means that we have the set $\{ x_1, x_2, \dots, x_{m + 1} \}.$

I'm not sure how to proceed from here. I was thinking of using the multiplication rule somehow, but I've been unable to make progress on this.

I've also been unable to find any proofs for this theorem online.

I would greatly appreciate it if people could please help me prove this.

---

EDIT (Completed Proof):

Let $P(n)$ be the above statement.

Take the set $X = \{ x_1, x_2, \dots, x_n \mid n \ge 1 \}$.

$P(1)$ holds because the number of permutations of $1$ element is size $1$ and $1! = 1$.

Now assume that $P(n)$ is true for some $n = m \ge 1$.

And assume we have the sets $X = \{ x_1, x_2, \dots, x_m \}$ and $X' = \{ x_{m + 1} \}$.

Let task $T$ represent tasks $T_1, T_2, \dots, T_m$, where task $T_k, k = 1, 2, \dots, m$, represents the task where the $k$th element of the set $X$ is fixed and every permutation of the resultant set configuration is calculated.

Every time we fix one element and find all permutations of the resultant set, that leaves one set configuration that the next set cannot have since it would be identical to one of the permutations of the previous configuration. This is what we assumed to be true for a set with $m$ elements.

Let task $T_{m + 1}$ be the task where we take the set $X^* = X \cup X'$, fix the element $x_{m + 1}$, and calculate all permutations of the resultant set configuration. Since there are $m + 1$ elements in the set $X^*$, there are $m + 1$ ways to fix $x_{m + 1}$ ($m + 1$ set configurations) and calculate all permutations. Therefore, according to the multiplication rule, there are $(m!)(m + 1) = (m + 1)!$ ways to perform tasks $T$ and $T_{m + 1}$. $$\tag*{$\blacksquare$}$$

---

I would greatly appreciate it if people could please review the complete proof and provide feedback as to its correctness.

Answer 1

Your proof seems correct, but (in my opinion) it's too elaborate. It obscures the combinatorial simplicity of the argument. I might write the following:

Clearly, there is only one (that is, $1!$) permutation on a set containing a single element.

Suppose now (for the purpose of induction) that there are $m!$ permutations of a set containing $m$ elements. We seek to show that there are $(m+1)!$ permutations of a set containing $m+1$ elements.

We can construct all permutations of the latter set as follows:

1. Choose a permutation of the first $m$ elements.
2. Insert the final element into the permutation.

By the inductive hypothesis, Step 1 can be completed in $m!$ ways. Step 2 can be completed in $m+1$ ways, since there are $m+1$ locations into which the final element may be inserted. Therefore, we have (by the multiplication principle) that the number of permutations of an $m+1$ element set is equal to $m! \cdot (m+1)$, which is the desired $(m+1)!$.

Answer 2

When we are given $m+1$ items, we separate a special item from the other $m$ items. We sort the $m$ items and fix their order, that give us $m!$ options.

Now we have $m+1$ positions to choose to place our special items and none of them repeats.

Hence we have $m! \cdot (m+1)= (m+1)!$

Answer 3

Any rigorous proof that involves induction has to develop some rudimentary theory for the set of all permutations on a set. The fact that the result is so well known and can be directly proven using the rule of product does not mean that proof details can be glossed over.

---

Let $X$ be a finite set containing $n$ elements with symmetric group $\text{Sym}(X)$, i.e. the set of all permutations of $X$. Let $x' \notin X$ and set $X' = X \cup \{x'\}$ so that there is a natural inclusion $\text{Sym}(X) \subset \text{Sym}(X')$ - you extend any permutation $\rho$ on $X$ to all of $X'$ by defining $\rho(x') = x'$.

If we have a set of permutations, we can generate a larger set by taking all possible products (i.e. functional composition) of the permutations. Whenever we generate these 'algebraic closures' we throw in the identity mapping for good measure.

Proposition 1: If $\text{Sym}(X)$ is generated by the set of all transpositions then the set $\text{Sym}(X')$ is also generated by the set of transpositions.
Proof
Let $f \in \text{Sym}(X')$ and set $\tau = \left(\,x' \;\; f^{-1}(x')\,\right)$ and $g = f \circ \tau$. It is immediate that $g(x') = x'$ so that $g$ is a product of transpositions. But then $f = g \circ \tau^{-1}$ is also the composition of transpositions, since $\tau^{-1} = \tau$. $\quad \blacksquare$

Note: In the preceding proof, $\tau$ can represent the identity. So we are abusing the notation used for a transposition, but this is convenience that we will continue to implicitly employ in what follows.

In general, the following equations hold true for transpositions:

\begin{align}(T1) \quad (ab)(ab)&=1_{Id}\\ (T2) \quad (ab)(cd)&=(cd)(ab)\\ (T3) \quad (ab)(ac)&=(bc)(ab)\\ (T4) \quad (ab)(bc)&=(bc)(ac)\end{align}

If $f \in \text{Sym}(X')$ is a product of transpositions, locate the first one $\tau$ from the left side (if any) that swaps $x'$ with another element and start 'pushing it' step-by-step to the far right using
$\text{(T1)}$ thru $\text{(T3)}$ . When using $\text{(T2)}$ or $\text{(T3)}$ progress is made as $\tau$ is closer to the right and none of the transpositions on the left of $\tau$ swap $x'$. If at any step $\text{(T1)}$ comes into play, then the 'composition string' is reduced by $2$ transpositions (progress) and you have to start over.

When this pushing algorithm has ended, we can write

$\tag 1 f =g \circ \left(\,x' \;\; x\,\right) \, \text{ with } (x \in X) \;\land\; (g \in \text{Sym}(X))$.

Let $\mathcal S$ be the collection of all transpositions in $\text{Sym}(X')$ swapping $x'$ with another element. Again, as a convenience the identity is a member of $\mathcal S$ and so $\text{#}(\mathcal S) = n + 1$.

Proposition 2: The mapping $\left(g,\tau\right) \mapsto g \circ \tau$ defines a bijective correspondence

$\quad \text{Sym}(X) \times \mathcal S \equiv \text{Sym}(X')$.

Proof
We've already demonstrated that the mapping is a surjection and the injectivity is an easy argument. $\blacksquare$

As easy consequence of proposition 2 is that

$\quad \text{#}\left(\text{Sym}(X')\right) =\text{#} \left( \text{Sym}(X) \times \mathcal S \right)= \text{#} \left( \text{Sym}(X) \right) \times \text{#} \left(\mathcal S \right) = \text{#} \left( \text{Sym}(X) \right) \times (n+1) $

The following can be derived using induction and the above theory:

Theorem 3: If $X$ has $n$ elements then $\text{Sym}(X)$ contains $n!$ elements.

Answer 4

Consider all the $m!$ permutations of the $m$ first elements and insert the $m+1^{th}$ in all the possible places. As there are $m+1$ possible places per permutation, we get a total of $(m+1)m!$.

Remains to show that we didn't forget any new permutation nor repeat any.

1. by hypothesis, we started with all permutations of the first $m$; a permutation of the $m+1$ is perforce a permutation of the $m$ with the $m+1^{th}$ inserted somewhere. We tried all insertion points, nothing is missed.

2. all permutations of $m$ are distinct. All permutations obtained by inserting the new element in position $k$ are distinct from each other, and distinct for all $k$. Thus all new permutations are distinct.

Answer 5

If $X$ is a set, then $S_X$ shall denote the set of all permutations of $X$ (that is, of all bijections from $X$ to $X$). You want to prove that every finite set $X$ satisfies $\left|S_X\right| = \left|X\right|!$. (Note that this is perfectly true when $X$ is empty.)

---

If you want a fully rigorous proof written up in all detail, then one place you can find it is Corollary 7.82 in my Notes on the combinatorial fundamentals of algebra, 10th of January 2019. This proof can be summarized as follows:

• If $X$ is a set, and if $x$ and $y$ are two elements of $X$, then we let $t_{x, y}$ be the permutation of $X$ that swaps $x$ with $y$ while leaving all other elements of $X$ unchanged. (This is the identity map when $x = y$, and otherwise is a transposition.)

• Now let $n$ be a nonnegative integer, and set $\left[n\right] := \left\{1,2,\ldots,n\right\}$. Prove (Exercise 5.9 in op. cit.) that each permutation $\sigma$ of $\left[n\right]$ can be written in the form $\sigma = t_{1, i_1} \circ t_{2, i_2} \circ \cdots \circ t_{n, i_n}$ for a unique $\left(i_1, i_2, \ldots, i_n\right) \in \left[1\right] \times \left[2\right] \times \cdots \times \left[n\right]$. Roughly speaking, this simply means that $\sigma$ can be turned into the identity permutation by first swapping $n$ with its image, then swapping $n-1$ with its image (under the resulting permutation), and so on, until all numbers $n, n-1, \ldots, 1$ are in their proper places. I formalize this as an induction argument.

• The above statement can be interpreted as a bijection between the set $\left[1\right] \times \left[2\right] \times \cdots \times \left[n\right]$ and the set $S_{\left[n\right]}$ of all permutations of $\left[n\right]$. The former set clearly has size $n!$; hence, so does the latter. Thus, the set $S_X$ of all permutations of any $n$-element set $X$ has size $n!$ as well (to prove this, fix some bijection between $X$ and $\left[n\right]$, and use it to construct a bijection from $S_X$ to $S_{\left[n\right]}$).

---

This is not the shortest proof. The post by @CopyPasteIt suggests a different argument, but muddles it up somewhat in my opinion, so here is a sketch of how I would do it:

• Proceed by induction on $\left|X\right|$. The induction base ($\left|X\right| = 0$) is obvious. For the induction step, you need to show that if $X$ is a finite set and $x \in X$ is arbitrary, then $\left|S_X\right| = \left|X\right| \cdot \left|S_{X \setminus \left\{x\right\} }\right|$.

• So let us fix a finite set $X$ and some $x \in X$. Let $W$ be the set of all permutations $\tau \in S_X$ satisfying $\tau\left(x\right) = x$. It is not hard to see that there is a bijection from $S_{X \setminus \left\{x\right\} }$ to $W$. (Indeed, this follows from Proposition 5.58 (e) in op. cit., applied to $Y = X \setminus \left\{x\right\}$; but you really should prove this yourself, as it is a straightforward formalization of a clear statement: A permutation of $X$ that fixes $x$ is "really" just a permutation of $X \setminus \left\{x\right\}$. When you formalize the "really", you get a very natural bijection.) Hence, $\left|W\right| = \left|S_{X \setminus \left\{x\right\} }\right|$.

• If $\sigma \in S_X$ is any permutation, then there is a unique $y \in X$ satisfying $t_{x, y} \circ \sigma \in W$ (namely, this $y$ is $\sigma\left(x\right)$). Hence, each $\sigma \in S_X$ can be written as $t_{x, y} \circ w$ for a unique pair $\left(y, w\right) \in X \times W$. In other words, the map $X \times W \to S_X,\ \left(y, w\right) \mapsto t_{x, y} \circ w$ is a bijection. Thus, $\left|S_X\right| = \left|X \times W\right| = \left|X\right| \cdot \left|W\right| = \left|X\right| \cdot \left|S_{X \setminus \left\{x\right\} }\right|$ (since $\left|W\right| = \left|S_{X \setminus \left\{x\right\} }\right|$). This completes the induction step.

---

Things get somewhat easier once you get used to combinatorics and realize that the permutations of a finite $n$-element set $X$ are in bijection with the $n$-tuples $\left(x_1, x_2, \ldots, x_n\right)$ of distinct elements of $X$. Indeed, confusingly, the latter $n$-tuples are often called permutations of $X$ as well, although there is in general no canonical bijection between these two kinds of permutations (see Remark 5.4 in op. cit.). This confusion set aside, it is not hard to see using some versions of the product law that the number of $n$-tuples $\left(x_1, x_2, \ldots, x_n\right)$ of distinct elements of an $n$-element set $X$ is $n!$; in fact, more generally, for any nonnegative integer $m$, the number of $m$-tuples $\left(x_1, x_2, \ldots, x_m\right)$ of distinct elements of an $n$-element set $X$ is $n\left(n-1\right)\left(n-2\right)\cdots\left(n-m+1\right)$. This gives the perhaps shortest proofs of your claim, having the advantage that you don't really have to deal with permutations (once you have shown that they are in bijection with these tuples).

Answer 6

This answer might be more appropriate for students studying discrete mathematics and interested in combinatorics and/or computer science.

One can regard permutations as 'scrambled words';
see Permutation: One line notation.

So with the ordered alphabet $\mathcal A = \{a,b,c,\dots,z\}$ here are the lists of scrambled permutation words:

Scrambling first 1 letters: $P_1 = \{a\}$
Scrambling first 2 letters: $P_2 = \{ab,ba\}$
Scrambling first 3 letters: $P_3 = \{abc,acb,bac,cab,cba,bca\}$
etc.

These ideas can be implemented in Python; here we create $P_3$:

>>> import itertools
>>> list(itertools.permutations(['a','b','c'],3))
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

How many scrambled permutation words can be formed with the first $4$ letters, $\{a,b,c,d\}$?

There is a mapping from $P_4$ to $P_3$ defined by removing the letter $d$ from a word $\pmb \omega$ in $P_4$.

Examples: $abdc \mapsto abc$; $\;cdba \mapsto cba$.

It is easy to see that $4$ words in $P_4$ get mapped to each word in $P_3$.

So the number of words in $P_4$ is equal to $4 \times \text{#}(P_3)$.

In general it can be shown that

$\tag 1 \text{#}(P_{n+1}) = (n+1) \times \text{#}(P_n)$

The above is all that is needed to get the $n!$ permutation count using induction.

Answer 7

Here's the basis of a proof I might do for this. I'm going to use a numerical argument to make my point clearer, but it will hold for a general $n$ too.

Suppose we assume that the statement holds true for $n=4$ and we use the letters $A,B,C,D$ as our four elements in the set.

One such listing might be $ABCD$.

Suppose then we wish to add a fifth element, $E$, to this set, whilst keeping the other four in order. We can do this in five ways, clearly:

$$EABCD, AEBCD, ABECD, ABCED, ABCDE$$

This will be the case for every permutation of the set of $4$, and will cover every permutation of the set of $5$, without crossovers (the second condition eliminates them)

Thusly, the permutations of a set of $5$ is $4!\cdot 5 =5!$

Generalise this and you have a proof.

Answer 8

Here is another approach to proving $^nP_n = n!$.

Let n be any postive real number, we proceed by induction on $n$. The base case ($n=1$) is true since there is only one way of arranging one object.$^1P_1 = 1 = 1!$.

Now suppose inductively that the $^nP_n = n!$ is true for some $n=m$ i.e there are $m!$ ways arranging a set of $m$ elements. We wish to show that $^{(m+1)}P_{(m+1)} = (m+1)!$ i.e the number of ways of arranging any set of $m+1$ objects is $(m+1)!$. This is equivalent to assigning elements to the positions 1 through $m+1$ in an array of length $m+1$. This task can then be broken into two stages

1. Choose the first position in the array. This can be done in $m+1$ ways.
2. For each choice of first position choose an arrange the $m$ elements for the 2nd position to the $m+1$ positions of the array. By the induction hypothesis, this can be done in $m!$ ways.

Now applying the multiplication rule, there are $(m+1)\times m! = (m+1)!$ ways of arranging a set of $m$ elements. Hence $^{(m+1)}P_{(m+1)} = (m+1)!$. This conclude the proof by induction.