# Proving that $S_n$ has order $n!$

I have been working on this exercise for a while now. It’s in B.L. van der Waerden’s Algebra (Volume I), page $19$. The exercise is as follows:

The order of the symmetric group $S_n$ is $n!=\prod_{1}^{n}\nu$. (Mathematical induction on $n$.)

I don’t comprehend how we can logically use induction here. It seems that the first step would be proving $S_1$ has $1!=1$ elements. This is simply justified: There is only one permutation of $1$, the permutation of $1$ to itself.

The next step would be assuming that $S_n$ has order $n!$. Now here is where I get stuck. How do I use this to show that $S_{n+1}$ has order $(n+1)!$?

Here is my attempt: I am thinking this is because all $n!$ permutations of $S_n$ now have a new element to permutate. For example, if we take one single permutation
$$p(1,\dots,n) = \begin{pmatrix} 1 & 2 & 3 & \dots & n\\ 1 & 2 & 3 & \dots & n \end{pmatrix}$$
We now have $n$ modifications of this single permutation by adding the symbol $(n+1)$:

\begin{align}
p(1,2,\dots,n,(n+1))&=
\begin{pmatrix}
1 & 2 & \dots & n & (n+1)\\
1 & 2 & \dots & n & (n+1)
\end{pmatrix}\\
p(2,1,\dots,n,(n+1))&=
\begin{pmatrix}
1 & 2 & \dots & n & (n+1)\\
2 & 1 & \dots & n & (n+1)
\end{pmatrix}\\
\vdots\\
p(n,2,\dots,1,(n+1))&=
\begin{pmatrix}
1 & 2 & \dots & n & (n+1)\\
n & 2 & \dots & 1 & (n+1)
\end{pmatrix}\\
p((n+1),2,\dots,n,1)&=
\begin{pmatrix}
1 & 2 & \dots & n & (n+1)\\
(n+1) & 2 & \dots & n & 1
\end{pmatrix}
\end{align}

There are actually $(n+1)$ permutations of that specific form, but we take $p(1,\dots,n)=p(1,\dots,n,(n+1))$ in order to illustrate and prove our original statement. We can make this general equality for all $n!$ permutations: $p(x_1,x_2,\dots,x_n)=p(x_1,x_2,\dots,x_n,x_{n+1})$ where $x_i$ is any symbol of our finite set of $n$ symbols and $x_{n+1}$ is strictly defined as the symbol $(n+1)$.

We can repeat this process for all $n!$ permutations in $S_n$. This gives us $n!n$ permutations. Then, adding in the original $n!$ permutations, we have $n!n+n!=(n+1)n!=(n+1)!$. Consequently, $S_n$ has order $n!$.

How is my reasoning here? Furthermore, is there a more elegant argument? I do not really see my argument here as incorrect, it just seems to lack elegance. My reasoning may well be very incorrect, however. If so, please point it out to me.

#### Solutions Collecting From Web of "Proving that $S_n$ has order $n!$"

You can actually just use a combinatorial argument for this. The permutation group is a bijection from a set of $n$ elements to itself. So look at the first element in the permutation. There are $n$ choices to send that element to. Now for the second element, there are only $n-1$ choices left (because it is a bijection you cannot send two different elements in the domain to the same element in the codomain), and so on until you only have $1$ choice left for the last element. Thus we get $n!$ ways to arrange the permutation.

I start to get confused by the notation around halfway through. Here’s what I’d do: identify $S_n$ with the subgroup of $S_{n + 1}$ consisting of those permutations that fix $n + 1$. Choose elements $\sigma_1, \ldots, \sigma_{n + 1}$ of $S_{n + 1}$ such that $\sigma_i(n + 1) = i$. For example, you could take $\sigma_i$ to be $[i,n+1]$. Then prove that these are left coset representatives for $S_n$ in $S_{n + 1}$. In more detail, you need to do two things:

1. If $\sigma \in S_{n + 1}$, then find an $i$ such that $\sigma_i^{-1}\sigma$ fixes $n + 1$.
2. If $i \neq j$, then show that $\sigma_j^{-1}\sigma_i$ does not fix $n + 1$.

Here’s my answer using induction (it’s a similar proof, but seems more concise and understandable):

Our base is true.

Assume $S_n$ has $n!$ permutations.

Define all the original $n!$ permutations as permutations where $(n+1)$ is sent to itself. Thus, by definition, all other permutations (“the new permutations”) are the original permutations, except $(n+1)$ is sent to a place other than itself. There are $n$ places to send $(n+1)$ if we exclude $(n+1) \to (n+1)$. Since there are $n!$ original permutations, there must be $n!n$ new permutations. The reason for this is because, for all $n!$ permutations, there is $n$ different modifications of the $n!$ permutations (e.g. $(n+1) \to 1$, $(n+1) \to 2$, etc.). Therefore, the total amount of permutations of $S_{n+1}$ is $n!+n!n=(n+1)!$.

P.S. I only used induction because I wanted to do precisely as the exercise states; I try not to deviate in order to avoid erroneous proofs (in this case, I would prefer to deviate).