# Definition: Permutations

Let $$V=\{a_i,~i\in I\}$$ be a finite (or infinite) set with a given index $$I$$ of its elements $$I=\{1,\ldots,n,\ldots\}$$. A permutation of $$V$$ is a bijective map on this order $$\pi:I\mapsto I$$.

A permutation can be generated by selecting elements from an ordered collection $$A$$ and moving them from this collection into a new ordered collection $$P$$.

### Notation:

There are different ways a permutation $$\pi$$ can be notated. As a permutation does not depend on the specific elements of $$a_i\in V$$, all notations are related to the index set $$i$$.

Possibility 1 (Two-Line Notation): $\pi=\left( \begin{matrix} 1 & 2 & 3 & \cdots & n-1 & n \\ \pi(1) & \pi(2) & \pi(3) & \cdots & \pi(n-1) & \pi(n) \\ \end{matrix} \right)~~~~~~~~~~~~\text{e.g. for }n=9:~~~~\left( \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 7 & 8 & 6 & 4 & 9 & 3 & 2 & 1 & 5\\ \end{matrix} \right)$ As the indices of the first line always appear in their natural order, they do not provide any additional information. Therefore the following one-line notation is more common:

Possibility 2 (One-Line Notation): $\pi=( \begin{matrix} \pi(1) & \pi(2) & \pi(3) & \cdots & \pi(n-1) & \pi(n) \\ \end{matrix} )~~~~~~~~~~~~\text{e.g. for }n=9:~~~~( \begin{matrix} 7 & 8 & 6 & 4 & 9 & 3 & 2 & 1 & 5\\ \end{matrix} )$

Possibility 3 (Cycle Notation): The third possibility focuses on the effect of successively applying the permutation. In this context, a permutation is equivalent to a set of cycles, i.e. ordered partitions $$C$$ on the set $$I$$ such that the permutation $$\pi$$ does not changes the order and composition of the partitions. In the previous example $[1,7,2,8],$ $[3,6],$ $[4 ],$ $[5,9]$ are cycles, so $\pi=\{C_1, C_2, \ldots, C_k\}~~~~~~~~~~~~\text{e.g. for }n=9:~~~~\{[1,7,2,8], [3,6], [^4], [5,9]\}$

Corollaries: 1
Definitions: 2 3 4
Explanations: 5
Parts: 6
Problems: 7
Proofs: 8 9 10
Propositions: 11 12 13
Solutions: 14

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Aigner, Martin: "Diskrete Mathematik", vieweg studium, 1993