A permutation describes the (re)ordering of \(n\) elements of a finite set \(S\). If an ordering is not already present on the elements, the term “permutation” is often taken to mean the introduction of a specific ordering, i.e. a bijection \(\sigma: S \to [1, n]\). If an ordering is present, “permutation” is often taken to mean a reordering, i.e. a bijection \(\sigma: S \to S\) or equivalently \(\sigma: [1, n] \to [1, n]\). This document will mostly deal with the latter case.
There are \(n!\) distinct permutations of \(n\) elements.
The identity permutation is \(\sigma(i) = i,~ \forall i \in S\). The product \(\pi = \sigma \tau\) of two permutations \(\sigma\) and \(\tau\) is defined by function composition \(\pi(i) = \sigma(\tau(i))\) and is itself a permutation, i.e. the set of all permutations of a set is closed under this operation. The product is associative but not commutative in general. This means the collection of all permutations of a set forms a group, called the symmetric group.
One way to specify a permutation is to list all mappings. Note that this does not require an ordering to be present on the elements of \(S\). If however an order is given, and the set is finite, \(S = \{x_1, \ldots, x_n\}\), a more compact notation is to give the corresponding elements \(y_1, \ldots, y_n\), where \(y_i = \sigma(x_i)\). Since such an \(S\) is isomorphic to the positive integers no greater than \(n\), an even more compact notation is the list of integers \(i_1, \ldots, i_n\), where \(x_{i_1} = \sigma(x_1), \ldots, x_{i_n} = \sigma(x_n)\).