Permutation

of $ n $ elements

A finite sequence of length $ n $ in which all the elements are different, i.e. a permutation is an arrangement of $ n $ elements without repetition. The number of permutations is $ n! $.

Usually, one takes as the elements to be permuted the elements of the set $ \mathbf Z _ {n} = \{ 1 \dots n \} $; a one-to-one mapping $ \pi $ of $ \mathbf Z _ {n} $ onto itself defines the permutation $ \overline \pi \; = ( \pi ( 1) \dots \pi ( n)) $. The mapping $ \pi $ is also called a substitution of $ \mathbf Z _ {n} $. Many problems related to the enumeration of permutations are formulated in terms of substitutions, such as, for example, the enumeration of permutations with various restrictions on the positions of the permuted elements (cf. e.g. [1], [2]). A permutation $ \overline \pi \; $ can be regarded as an ordered set consisting of $ n $ elements if one assumes that $ \pi ( i) $ precedes $ \pi ( i+ 1) $, $ i = 1 \dots n $.

Examples. 1) The pair $ \{ \pi ( i) , \pi ( j) \} $ forms an inversion in $ \overline \pi \; $ if $ \pi ( i) > \pi ( j) $ for $ i < j $; if $ a _ {r} $ is the number of permutations of $ n $ elements with $ r $ inversions, then

$$ \sum _ {r=0} ^ { \left ( \begin{array}{c} n \\ 2 \end{array} \right ) } a _ {r} x ^ {r} = \ \frac{( 1- x) \dots ( 1- x ^ {n} ) }{( 1- x) ^ {n} } . $$

2) If $ b _ {n} $ is the number of permutations $ \overline \pi \; $ consisting of $ n $ elements such that $ \pi ( i) > \pi ( i- 1) $ for $ i $ even and $ \pi ( i) < \pi ( i- 1) $ for $ i $ odd, then

$$ \sum _{n=0} ^ \infty b _ {n} \frac{x ^ {n} }{n!} = \mathop{\rm tan} x + \mathop{\rm sec} x. $$

Often a permutation is defined to be a bijective mapping of a finite set onto itself, i.e. a substitution (cf. also Permutation of a set).

Comments

See also Permutation group.

References

[1]	V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[2]	J. Riordan, "An introduction to combinational analysis" , Wiley (1958)