# The Symmetric Groups on n Elements

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

For example:

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

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:

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

(5)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 have exactly $n!$ elements (permutations).

Proposition: 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$