Let $X$ be a finite set. For concreteness rename its elements so that
$$
X={1,2, \ldots, n}
$$
Recall that $\mathcal{B}(X)$ denotes the set of all bijections (or shuffles of $X$ )
$$
f: X \rightarrow X
$$
Below are diagrams of two bijections $f_{1}: X \rightarrow X$ and $f_{2}: X \rightarrow X$ for $X={1,2,3} .$
Given two maps $f_{1}: X \rightarrow X$ and $f_{2}: X \rightarrow X$ we can compose them in any order we like. In terms of mapping diagrams as above this amounts to stacking the together. For instance $f_{1} \circ f_{2}$ (first $f_{2}$, then $f_{1}-$ right to left, as usual with compositions) has the mapping diagram as follows
Problem 1: Find the mapping diagram of $f_{2} \circ f_{1}$ and verify that $f_{2} \circ f_{1} \neq f_{1} \circ f_{2}$.
The set of bijections $\mathcal{B}(X)$ together with the composition operation form a group. Traditionally it is denoted by $S_{n}$, where $n=|X|$ is the cardinality of $X$, and its elements (bijections of $X$ ) are denoted by Greek letters $(\sigma, \tau, \mu, \ldots)$.
3. Definition 1: Permutation group
Permutation group $S_{n}$ of the set $X={1,2, \ldots, n}$ is the set of all bijections
$$
\sigma:{1,2, \ldots, n} \rightarrow{1,2, \ldots n}
$$
endowed with the composition operation.
4. Specifying elements of $S_{n}$.
The most straightforward way to specify an element $\sigma$ of $S_{n}$ is to encode all the images $\sigma(i)$ of individual elements $1 \leqslant i \leqslant n$. It is convenient to store this data in a table of size $2 \times n$ :
$$
\sigma=\left(\begin{array}{cccc}
1 & 2 & \ldots & n \
\sigma(1) & \sigma(2) & \ldots & \sigma(n)
\end{array}\right)
$$
For example map $f_{2}$ from above would be
$$
f_{2}=\left(\begin{array}{lll}
1 & 2 & 3 \
2 & 3 & 1
\end{array}\right)
$$
Problem 2: Consider a permutation $\sigma$ given by a table
$$
\left(\begin{array}{cccc}
1 & 2 & \ldots & n \
i_{1} & i_{2} & \ldots & i_{n}
\end{array}\right)
$$
Prove that the table of $\sigma^{-1}$ is obtained from
$$
\left(\begin{array}{cccc}
i_{1} & i_{2} & \ldots & i_{n} \
1 & 2 & \ldots & n
\end{array}\right)
$$
by reordering its columns according to the top values in the first row.
The neutral element of $S_{n}$ is given by the “trivial” table
$$
i d=\left(\begin{array}{llll}
1 & 2 & \ldots & n \
1 & 2 & \ldots & n
\end{array}\right)
$$
$\left|S_{n}\right|=n !$, where $n !=1 \cdot 2 \cdot 3 \cdots \cdots$
Proof. To specify the number of bijections $\sigma:{1,2, \ldots, n} \rightarrow{1,2, \ldots, n}$ we need to
- set $\sigma(1)$-we have $n$ choices for it (any element of ${1,2, \ldots, n}$ )
- set $\sigma(2)$ – we have $(n-1)$ choices left (any element of ${1,2, \ldots, n}$ except for $\sigma(1)$, since $\sigma$ is bijective) 3. …
n. set $\sigma(n)$ – we have exactly one choice left (the unique element other that $\sigma(1), \sigma(2), \ldots, \sigma(n-1))$.
Overall this gives $n \cdot(n-1) \cdots \cdots 1=n !$ options.
Permutation $\sigma \in S_{n}$ is called as cycle of length $k \geqslant 2$, if there exist $k$ distinct elements $i_{1}, \ldots, i_{k} \in{1,2, \ldots n}$ such that $\sigma$ cyclically rotates $i_{1}, \ldots, i_{k}$ :
$$
i_{1} \stackrel{\sigma}{\rightarrow} i_{2} \stackrel{\sigma}{\rightarrow} i_{3} \stackrel{\sigma}{\rightarrow} \ldots \stackrel{\sigma}{\rightarrow} i_{k} \stackrel{\sigma}{\rightarrow} i_{1}
$$
and all the remaining elements are kept in place.
For $\sigma$ as above, we will use a shorthand
$$
\sigma=\left(i_{1}, i_{2}, \ldots i_{k}\right)
$$
This presentation is clearly not uniques, as we can also write the same $\sigma$ as
$$
\sigma=\left(i_{2}, i_{3}, \ldots i_{k}, i_{1}\right)
$$
Element $\sigma \in S_{3}$
$$
\sigma=\left(\begin{array}{lll}
1 & 2 & 3 \
3 & 2 & 1
\end{array}\right)
$$
is a cycle of length 2, as it cyclically permutes 1 and $3 .$
On the contrary element $\tau \in S_{4}$
$$
\tau=\left(\begin{array}{llll}
1 & 2 & 3 & 4 \
3 & 4 & 1 & 2
\end{array}\right)
$$
is not a cycle, since it simultaneously swaps 1 with 3 and 2 with $4 .$
9. Definition 3: Independent cycles
We say that cycles $\sigma=\left(i_{1}, \ldots, i_{k}\right)$ and $\mu=\left(j_{1}, \ldots, j_{l}\right)$ are independent if
$$
\left{i_{1}, \ldots i_{k}\right} \cap\left{j_{1}, \ldots, j_{k}\right}=\varnothing
$$
i.e., the sets of elements, which they cyclically permute, do not intersect.
10. The following proposition is obvious.
If cycles $\sigma$ and $\mu$ are independent, then they commute:
$$
\sigma \circ \mu=\mu \circ \sigma
$$
12. Theorem 1: Factorization into independent cycles
If $\sigma \in S_{n}$ is any permutation, then there exist a collection of mutually independent cycles $\mu_{1}, \ldots, \mu_{l} \in S_{n}$ such that
$$
\sigma=\mu_{1} \circ \mu_{2} \cdots \circ \mu_{l}
$$
Proof. Start with any element $a$ in ${1,2, \ldots, n}$ which is not fixed by $\sigma$. Consider iterations
$$
a \mapsto \sigma(a) \mapsto \sigma^{2}(a) \mapsto \ldots \sigma^{k}(a) \mapsto \ldots .
$$
At some step $l_{1}$ we again encounter $a$. Denote the corresponding cycle as
$$
\mu_{1}=\left(a, \sigma(a), \ldots, \sigma^{l_{1}-1}(a)\right)
$$
Then $\mu_{1}$ and $\sigma$ act in the same way on all the elements $\left{a, \sigma(a), \ldots, \sigma^{l_{1}-1}(a)\right}$ (equivalently $\mu_{1}^{-1} \circ \sigma$ fix these elements).
Pick another element $b \in{1, \ldots, n}$ not fixed by $\mu_{1}^{-1} \circ \sigma$, and repeat the procedure, identifying new cycle $\mu_{2} .$ This cycle will be independent with $\mu_{1}$, and now $\mu_{2}^{-1} \circ \mu_{1}^{-1} \circ \sigma$ fixes even more elements then $\mu_{1}^{-1} \circ \sigma$. Iterate this procedure, until the permutation $\sigma$ is decomposed into a product of independent cycles.
Consider
$$
\sigma=\left(\begin{array}{lllll}
1 & 2 & 3 & 4 & 5 \
3 & 4 & 5 & 2 & 1
\end{array}\right)
$$
The following the above procedure we find a factorization
$$
\sigma=(1,3,5)(2,4)
$$
Factorization into independent cycles is unique up to a reordering of $\mu_{i}$ ‘s.