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

-
It seems to me that you comprehend just fine how to use induction here! – Qiaochu Yuan Jun 10 '12 at 0:14
@QiaochuYuan, Thank you. I was worried that I was making some overtly obvious error and just didn't see it at all. – 000 Jun 10 '12 at 0:17
Actually, hm. I thought I understood what you were doing but after rereading I see that I don't. Namely, I thought you were moving $(n+1)$ one step to the left each time (as visualized in the second row of that two-row notation) but you aren't. What are you actually doing? – Qiaochu Yuan Jun 10 '12 at 0:21
Each symbol gets sent to a new place. In $p(1,\dots,(n+1))$, we start with the identity $p(1,\dots,(n+1))$ and send $2$ to $1$. Then, we send $3$ to $1$, . . ., and so forth. Eventually, we send $n$ to $1$ and then $(n+1)$ to $1$. This process can be repeated for any particular symbol. We would start with the 2nd permutation $p(2,1,3,\dots,n,(n+1))$ for repeating this process for the symbol $2$. So we'd have: $p(3,1,2,\dots,n,(n+1))$, $p(4,1,3,\dots,n,(n+1))$, $\dots$, $p(n,1,3,\dots,2,(n+1))$, and $p((n+1),1,3,\dots,n,2)$. [cont below] – 000 Jun 10 '12 at 0:30
It gets more and more confusing, but I am pretty certain there are $n$ permutations each time. So, the total of these permutations is $n!n$. Including the original $n!$ permutations, there are thusly $n!n+n!=(n+1)!$ permutations in total. – 000 Jun 10 '12 at 0:31

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.

-
So, $n$ permutations of $1$, $n-1$ permutations of $2$,$\dots$, $2$ permutations of $n-1$, and $1$ permutation of $n$. The sum of these permutations is $n!$? How is that so? (I am likely misunderstanding.) – 000 Jun 10 '12 at 0:48
Are we instead suppose to take the product of these permutations? $n \cdot (n-1)\cdots 2\cdot 1=n!$? If so, can you explain why? – 000 Jun 10 '12 at 0:51
@Limitless Well it's a combinatorial argument. We are arguing how many different ways we can arrange our permutation. So we are supposed to take the product since there are $n$ ways to where to send the first element to. Take for example say we want to make a line of $4$ people. There are $4$ choices for the first person in line, $3$ for the next, $2$ for the next and finally $1$ for the last one. So we can arrange the line in $4!$ ways! – Eugene Jun 10 '12 at 0:56
So, we are using "there are $n!$ ways to arrange $n$ distinct objects" as an axiom? – 000 Jun 10 '12 at 0:59
Certainly not. We are exploiting the fact that the symmetric group is a $bijection$ to itself. If it were not we could send both $1$ and $2$ to $n$ and the permutation would make no sense and we would have $n^n$ possibilities instead. Like the line example we are using the fact that only one person can stand in one place. – Eugene Jun 10 '12 at 1:00

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$.
-
I can't qualify how good this answer is because I do not yet know what left coset representatives are. However, I do think I did what you just stated at first, "Identify $S_n$ with the subgroup of $S_{n+1}$ consisting of those permutations that fix $n+1$." – 000 Jun 10 '12 at 0:38
@Limitless Ah, sorry. Hard to tell what people know and don't know on here. I'll try to give your proof another look, in view of your responses to Qiaochu. You could (and this is what a left coset is) say, look at the equivalence classes of the equivalence relation $\sigma \sim \tau$ $\Leftrightarrow$ $\tau^{-1}\sigma \in S_n$ and argue that way. It would be much the same. – Dylan Moreland Jun 10 '12 at 0:41
It's not your fault, haha. I can understand a little what you just said, but I don't immediately understand how to implement it. I am just now starting Abstract Algebra, so much of this is still sinking in. – 000 Jun 10 '12 at 0:42

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

-