We often meet groups first as abstract multiplication tables, but the first groups most people actually use are groups of rearrangements. If three roots of a polynomial are unnamed points on a page, there are six ways to relabel them. If four vertices of a tetrahedron are numbered, every symmetry of the labelled set is a permutation. The symmetric group is the universal home for these rearrangements: it records every possible bijective relabelling of a finite set, and it turns the idea of a group into something visible and computable.

The basic question is this: how complicated can the group of all rearrangements of $n$ objects be, and how can we calculate inside it without listing all $n!$ permutations? The answer begins with cycles. A permutation may look like a scrambled table of values, but its repeated action decomposes the underlying set into disjoint directed loops. This single observation explains orders of elements, conjugacy classes, signs, generators, and many homomorphisms out of $S_n$.

[example: Three Letters Already Give Non-Commutativity] Let $X=\{1,2,3\}$. Define $\sigma,\tau:X\to X$ by \begin{align*} \sigma(1)=2,\quad \sigma(2)=1,\quad \sigma(3)=3,\quad \tau(1)=1,\quad \tau(2)=3,\quad \tau(3)=2. \end{align*} We compare the two possible orders of composition on the single input $1$. Since $\tau(1)=1$ and $\sigma(1)=2$, \begin{align*} (\sigma\circ\tau)(1)=\sigma(\tau(1))=\sigma(1)=2. \end{align*} In the other order, since $\sigma(1)=2$ and $\tau(2)=3$, \begin{align*} (\tau\circ\sigma)(1)=\tau(\sigma(1))=\tau(2)=3. \end{align*} The two composite functions have different values at $1$, so $\sigma\circ\tau\ne \tau\circ\sigma$. Thus even in $S_3$, composition of bijections depends on the order in which the relabellings are performed. [/example]

This failure of commutativity is not a defect; it is the point. A permutation remembers order of operations, and different orders of relabelling can produce different outcomes. The symmetric group is therefore the natural testing ground for group theory: every abstract group can be represented inside some symmetric group, but symmetric groups themselves already contain rich internal structure.

## Definition

The parent concept is a [group](/page/Group): a set with an associative binary operation, identity, and inverses. For a finite set, the most natural group operation on bijections is composition. The symmetric group isolates this construction for the standard $n$-element set.

[definition: Symmetric Group] Let $n \in \mathbb{N}$. The symmetric group on $n$ letters is \begin{align*} S_n := \{\sigma: \{1,\dots,n\} \to \{1,\dots,n\} : \sigma \text{ is a bijection}\}, \end{align*} equipped with the group operation given by composition of functions. [/definition]

The identity element is the identity map $\operatorname{id}_{\{1,\dots,n\}}$, usually written simply as $e$ once the ambient group is fixed. The inverse of $\sigma \in S_n$ is its inverse function $\sigma^{-1}: \{1,\dots,n\} \to \{1,\dots,n\}$. The convention in this page is that products are composed right-to-left: $\sigma\tau$ means $\sigma \circ \tau$, so $\tau$ acts first.

A definition in terms of maps is precise, but calculations still need a compact way to record the images of all letters. Two-line notation solves the bookkeeping problem by putting the domain in a fixed order and writing the corresponding images underneath in prose-readable form.

[definition: Two-Line Notation] Let $\sigma \in S_n$. The two-line notation for $\sigma$ is the array whose first row is $1,2,\dots,n$ and whose second row is $\sigma(1),\sigma(2),\dots,\sigma(n)$. [/definition]

Two-line notation is close to the definition, but it hides the repeated motion of a point under the permutation. To see that motion, follow $i$, then $\sigma(i)$, then $\sigma(\sigma(i))$, and continue until returning to $i$. This leads to cycle notation, which records the orbits of this repeated motion.

[definition: Cycle] Let $n \in \mathbb{N}$, and let $a_1,\dots,a_k \in \{1,\dots,n\}$ be distinct. The cycle $(a_1\ a_2\ \cdots\ a_k)$ is the permutation $\sigma: \{1,\dots,n\} \to \{1,\dots,n\}$ defined by sending $a_i$ to $a_{i+1}$ for $1 \le i < k$, sending $a_k$ to $a_1$, and fixing every element of $\{1,\dots,n\} \setminus \{a_1,\dots,a_k\}$. [/definition]

A cycle of length $1$ fixes its single element, so such cycles are usually omitted from notation. The cycle $(1\ 3\ 4)$ means $1 \mapsto 3$, $3 \mapsto 4$, $4 \mapsto 1$, and every other letter is fixed. Since the same loop can be started at any point, $(1\ 3\ 4)$, $(3\ 4\ 1)$, and $(4\ 1\ 3)$ represent the same permutation.

[example: Converting a Table into Cycles] Let $\sigma \in S_5$ be given by $\sigma(1)=4$, $\sigma(2)=5$, $\sigma(3)=3$, $\sigma(4)=1$, and $\sigma(5)=2$. To convert this table into cycles, follow each unused letter under repeated application of $\sigma$. Starting at $1$, the given values give \begin{align*} 1 \mapsto \sigma(1)=4. \end{align*} Then \begin{align*} 4 \mapsto \sigma(4)=1. \end{align*} So the letters $1$ and $4$ form the cycle $(1\ 4)$. The smallest unused letter is now $2$. Since $\sigma(2)=5$ and $\sigma(5)=2$, we have \begin{align*} 2 \mapsto 5 \mapsto 2. \end{align*} This gives the cycle $(2\ 5)$. Finally, \begin{align*} \sigma(3)=3, \end{align*} so $3$ is a fixed point and may be omitted from cycle notation. Therefore \begin{align*} \sigma=(1\ 4)(2\ 5). \end{align*} This cycle expression records exactly the same images as the original table, but it groups the letters by their repeated motion under $\sigma$. [/example]

## Cycles and Element Structure

The first structural problem is to decide whether cycle notation is merely convenient or actually canonical. A general product of cycles can be hard to read because cycles may move the same letters. The useful case is when the cycles are disjoint, since then each letter belongs to at most one moving loop.

[definition: Disjoint Cycles] Two cycles $(a_1\ \cdots\ a_r)$ and $(b_1\ \cdots\ b_s)$ in $S_n$ are disjoint if \begin{align*} \{a_1,\dots,a_r\} \cap \{b_1,\dots,b_s\}=\varnothing. \end{align*} [/definition]

Disjoint cycles act on separate letters, so their product can be read independently on each part of the set. The next theorem answers the normal-form question: every permutation can be broken into these noninterfering loops, and there is no hidden choice except the order in which the loops are written.

[quotetheorem:775]

The decomposition theorem converts questions about a permutation into questions about several independent loops. To compare two permutations, though, we need a way to remember the sizes of those loops while ignoring the accidental names of the letters. That invariant is the cycle type.