Permutation

A Permutation of a set $X$ is a bijection from $X$ to $X$, or more simply, a rearrangement of itself.

There are various notations to show permutations, but we’ll use three main ways: two graphical, one normal. In order of their importance…

1. Cycle notation: $\sigma =(24367)$, read right-to-left.
2. Bijection notation: $\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ 1& 4& 6& 3& 5& 7& 2\end{array}$
3. Drawn cycle notation:

\begin{document}
\begin{tikzpicture}[
  every node/.style={circle, draw, thick, minimum size=7mm},
  every path/.style={->, thick}
]
 
% Left 1-cycle
\node (one) at (-3,0) {1};
\draw (-3,0.6) arc[start angle=90,end angle=450,radius=0.6];
 
% Right 5-cycle
\node (five) at (3,0) {5};
\draw[->] (3,0.6) arc[start angle=90,end angle=450,radius=0.6];
 
% Middle 5-cycle (2 4 3 6 7)
\node (two) at (0,1.8)  {2};
\node (four) at (-1,0.9){4};
\node (three) at (-0.6,-0.9){3};
\node (six) at (0.6,-0.9){6};
\node (seven) at (1,0.9){7};
 
\draw[->,bend left=15] (two)   to (four);
\draw[->,bend left=15] (four)  to (three);
\draw[->,bend left=15] (three) to (six);
\draw[->,bend left=15] (six)   to (seven);
\draw[->,bend left=15] (seven) to (two);
 
\end{tikzpicture}
\end{document}

Formal Definition

Let $a_1,a_2,\dots ,a_r$ be distinct elements of a set $X$. Then, $\sigma =(a_1{a}_2\dots a_r)$ is the permutation of $X$ sending $a_1\to a_2,a_2\to a_3,\dots ,a_r\to a_1$, and fixing all elements in $X\setminus \{a_1,a_2,\dots ,a_r\}$. Such a permutation is called an $r$-cycle, or a cycle of length $r$.

What is the size of $\text{Sym}(X)$?

By understanding that we initially have $n$ choices to rearrange the set, and then $n-1$ after that choice, and so on, we can prove inductively that the modulus of the set (for finite $X$) $|\text{Sym}(X)|=|X|!$.

The Order of a Permutation

The Order of a Permutation $g\in \text{Sym}(X)$, denoted $o(g)$, is the smallest $n\in \mathbb{N}$ such that $g^n=e$, the identity element, if such an $n$ exists; if not then the order of $g$ is infinite.

Quick Inverse Proposition

Let $X$ be a set and suppose $\sigma \in \text{Sym}(X)$. We know that we can write $\sigma$ as a product of disjoint cycles, $\sigma =c_1{c}_2\dots c_n$, hence:

1. The inverse of any cycle $(x_1{x}_2\dots x_m)$ is $(x_m{x}_{m-1}\dots x_1)$, and
2. ${\sigma }^{-1}=c_1^{-1}{c}_2^{-1}\dots c_n^{-1}$.

This can be proven directly.