permutation

Tags: #definition

permutation

A permutation of $n$ letters is a rearrangement of those $n$ letters. More precisely, it is a bijective map $w : [n] \to [n]$ .

There are many ways of writing these:

1-line notation - $w = w_{1}, w_{2}, \dots, w_{n}$ where each $w_{i} \in {1, 2, \dots, n}$ (to represent $i \mapsto w_{i}$ )
2-line notation - having a row at the top 1 through n and below each $i$ showing where it sends $i$

w = (\begin{matrix} 1 & 2 & \dots & n \\ w_{1} & w_{2} & \dots & w_{n} \end{matrix})

graphic notation - directed graph where each vertex is labeled $i$ and each vertex has exactly one in edge and one out edge. The arrows show where $i$ gets sent.
cycle notation - we may break down the graph into connected components (cycles). Then, we may write each cycle in a parenthesis, with each number being sent to the one on its right (with the last item being sent to the first)

This forms a group called the symmetric group on $n$ letters, $S_{n}$ .

Operation: composition $u v = u \circ v$ .
Inverse: the inverse map
- To calculate this quickly, you can just flip and rearrange the 2-line notation

Examples

and the cycle notation for this is given by

w = (1, 6, 3, 4) (2) (5, 10, 7) (8, 9)

Properties