Prove that the symmetric group on $n$ letters, $S_n$, has order $n!$.

Question

Here's my proof in which I've used another theorem to prove this one. I want you suggest me another proof without using this theorem, please.

Proof: By the theorem Cardinality of set of injections, we have:

Let $S$ and $T$ be sets.
The number of injections from $S$ to $T$ where $|S|=m, |T|=n$ is often denoted $P_{nm}$, and is
$P_{nm}=\left\{ \begin{array}{rl} \frac{n!}{(n-m)!} & m\leq n \\ 0 & m>n \end{array}\right.$

Since the symmetric group on $n$ letters is a bijection (and therefore and injection), and that by the operation $f\circ g:S\rightarrow S$ we have $m=n$, then $|S_n|=n!/0!=n!$ $\square$

Answer 1

Induction.

First, $|S_1| = 1$, trivially.

Now suppose $n > 1$. Let's count the number of permutations of the numbers $1, \ldots, n$ by counting those that send $n$ to $i$ for each $i = 1, 2, \ldots, n$. We'll show that these counts will all turn out to be the same number $c$, so the total will be $nc$, and that the number $c$ is exactly $|S_{n-1}|$, which is, by the inductive hypothesis, $(n-1)!$.

Here are the details:

Let $V_i \subset S_n$ be the set of permutations that send $n$ to $i$ for some particular $i$. To compute $|V_i|$, let $u$ be some such permutation. To each element $v$ of $V_i$, associate the element $u^{-1} \circ v$, which is an element of $V_n$. This association is clearly a bijection. So $|V_i| = |V_n|$. Thus we need only compute $|V_n|$.

Now $V_n$ consists of all permutations that send $n$ to $n$; by restricting the domain (removing $n$), we get a permutation of $1\ldots (n-1)$; this correspondence with $S_{n-1}$ is clearly invertible: to each permutation $s \in S_{n-1}$, assign the permutation $$ s'(k) = \begin{cases} s(k) & k = 1, 2, \ldots, n-1 \\ n & k = n \end{cases} $$ Then $s'$ is an element of $V_n$ that corresponds to $s$ under our "restriction" map.

So $|V_n| = |S_{n-1}|$.

That's it!.

Answer 2

The objects of $S_n$ are the bijections from a set of size $n$ to another. If we order each of the elements of the list then we can specify each of these bijections by a list including all of the letters exactly once.

For example the list $b_1,b_2\dots b_n$ means $a_1$ gets mapped to $b_1$, $a_2$ gets mapped to $b_2$ and so on. So the order of $S_n$ is equal to the number of these lists.

How many of these lists exist? we have $n$ options for the first element, $n-1$ options for the second one $\dots$

So we get $n\cdot(n-1)\dots \cdot 2\cdot 1=n!$ lists, and thus $|S_n|=n!$