# The Symmetric Groups, Sn

Definition: Consider the $n$-element set $\{1, 2, ..., n \}$. A Permutation on $\{ 1, 2, ..., n \}$ is a bijection function $\sigma : \{ 1, 2, ..., n \} \to \{ 1, 2, ..., n \}$. The set of all permutations on $\{ 1, 2, ..., n \}$ is denoted $S_n$. |

A permutation $\sigma$ of $\{ 1, 2, ..., n \}$ can be written in "matrix form", i.e., of the form:

(1)Where $\{a_1, a_2, ..., a_n \} = \{ 1, 2, ..., n \}$ and $\sigma$ is defined such that $\sigma(j) = a_j$ for each $1 \leq j \leq n$. For example:

(2)In general, $S_n$ will have $n!$ distinct permutations $\sigma_1, \sigma_2, ..., \sigma_{n!}$. This set of permutations along with the operation $\circ$ of function composition will define an important type of group that we formally define below.

Definition: The Symmetric Group on the $n$-element set $\{1, 2, ..., n \}$ is the set of permutations $S_n = \{ \sigma_1, \sigma_2, ..., \sigma_{n!} \}$ along with the operation $\circ : S_n \to S_n$ of function composition defined for all $f_1, f_2 \in S_n$ as $(f_1 \circ f_2)(x) = f_1(f_2(x))$. |

For example, consider the group $S_3$ from above with the operation $\circ$. The composition of two permutations of the set $\{1, 2, 3 \}$ be a permutation of the set $\{1, 2, 3 \}$ so $S_3$ is closed under $\circ$. We've already seen that the composition of three functions is associative too. The identity permutation is $\sigma_1 = \begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix}$, and for permutation in $S_3$ there exists another permutation in $S_3$ that returns us to the identity permutation. In fact, the inverses are somewhat self-defined. For example, consider the following permutation:

(3)Then the inverse permutation is assigned $1 = \sigma^{-1}(3)$, $2 = \sigma^{-1}(1)$ and $3 = \sigma^{-1}(2)$ to get:

(4)Then $\sigma(\sigma^{-1}(x)) = x = \sigma^{-1}(\sigma(x))$ for all $x \in \{1, 2, 3\}$

We will now look at a nice result which will tell us that a symmetric group on $n$-elements will indeed have exactly $n!$ elements (permutations).

Proposition 1: The symmetric group $(S_n, \circ)$ has order $n!$. |

**Proof:**Let $n \in \mathbb{N}$. Then any permutation $\sigma \in S_n$ is of the following form:

- Where $x_1, x_2, ..., x_n \in \{ 1, 2, ..., n \}$ are distinct. The value of $x_1$ can be one of $n$ numbers. The value of $x_2$ can be one of $n - 1$ numbers, and so forth. The final choice for $x_n$ must be fixed. Hence there are $n!$ such permutations $\sigma$ - each of which is indeed a permutation and is indeed unique. So the order of $(S_n, \circ)$ is $n!$. $\blacksquare$