View source for Permutation

''of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722701.png" /> elements''

A finite sequence of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722702.png" /> in which all the elements are different, i.e. a permutation is an [[Arrangement|arrangement]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722703.png" /> elements without repetition. The number of permutations is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722704.png" />.

Usually, one takes as the elements to be permuted the elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722705.png" />; a one-to-one mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722706.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722707.png" /> onto itself defines the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722708.png" />. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p0722709.png" /> is also called a substitution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227010.png" />. 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. [[#References|[1]]], [[#References|[2]]]). A permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227011.png" /> can be regarded as an ordered set consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227012.png" /> elements if one assumes that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227013.png" /> precedes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227015.png" />.

Examples. 1) The pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227016.png" /> forms an inversion in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227017.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227018.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227019.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227020.png" /> is the number of permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227021.png" /> elements with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227022.png" /> inversions, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227023.png" /></td> </tr></table>

2) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227024.png" /> is the number of permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227025.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227026.png" /> elements such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227027.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227028.png" /> even and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227029.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227030.png" /> odd, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072270/p07227031.png" /></td> </tr></table>

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|Permutation of a set]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.N. Sachkov,   "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Riordan,   "An introduction to combinational analysis" , Wiley  (1958)</TD></TR></table>



====Comments====
See also [[Permutation group|Permutation group]].