Proving that $S_n$ has order $n!$

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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).