Permutation Function
Definition
For a finite set $X$, a bijection $\sigma : X \to X$ is called a permutation of $X$, or simply a permutation. When $|X| = n$, it is customary to number the elements and write them as follows.
$$ X = \left\{ 1, 2, \dots, n \right\} $$
Explanation
In fact, the set $X$ in the definition need not be finite, but for ease of explanation we restrict it to finite sets.
Since a permutation is defined as a bijective function, a permutation does the same job as rearranging the elements without duplicating or omitting any. Hence, if $|X| = n$, there are $n$ possible values for $\sigma(1)$, and once that is fixed there are $n-1$ remaining possible values for $\sigma(2)$, so $X$ has exactly $n!$ permutations, which equals the permutation as a counting number $_{n}P_{n}$.
$$ {}_{n}P_{n} = \dfrac{n!}{(n-n)!} = n! $$
For $X = \left\{ 1, 2, \dots, n \right\}$, the set of all permutation functions $\sigma : X \to X$ is denoted by $S_{n}$.
$$ S_{n} = \left\{ \sigma : X \to X \mid \text{$\sigma$ is bijective} \right\} $$
Notation
The most intuitive way to represent a permutation of $X = \left\{ 1, 2, \dots, n \right\}$ is to write the elements of $X$ in the top row and, in the bottom row, where each element is sent. For example, the permutation with $n = 4$ and $1 \mapsto 3$, $2 \mapsto 1$, $3 \mapsto 4$, $4 \mapsto 2$ is written as follows.
$$ \sigma = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{bmatrix} $$
Chaining the above mappings gives $1 \to 3 \to 4 \to 2 \to 1$, so the same permutation is also written as $\sigma = (1,3,4,2)$. However, not every permutation can be expressed as a single cycle. For example, for the permutation $\tau$ with $1 \mapsto 2$, $2 \mapsto 1$, $3 \mapsto 4$, $4 \mapsto 3$, chaining the mappings splits into two loops, $1 \to 2 \to 1$ and $3 \to 4 \to 3$, so it is written as the product of two disjoint cycles $\tau = (1,2)(3,4)$. In general, every permutation can be expressed as a product of disjoint cycles.
On the other hand, instead of viewing a permutation as a function that moves the elements of $X$, one may also let it act on the indices of variables and write $(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)})$. In the example above, this notation means $(x_{3}, x_{1}, x_{4}, x_{2})$.