7
$\begingroup$

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.

  • 0
    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.2012-06-10

3 Answers 3

8

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.

  • 1
    Thank you, I think I understand now.2012-06-10
2

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

1

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$.
  • 0
    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.2012-06-10