Editing Permutation (section)

==Permutations of totally ordered sets==
In some applications, the elements of the set being permuted will be compared with each other. This requires that the set ''S'' has a [[total order]] so that any two elements can be compared. The set {1, 2, ..., ''n''} with the usual ≤ relation is the most frequently used set in these applications.

A number of properties of a permutation are directly related to the total ordering of ''S,'' considering the permutation written in one-line notation as a sequence <math>\sigma = \sigma(1)\sigma(2)\cdots\sigma(n)</math>.

===Ascents, descents, runs, exceedances, records===
{{anchor|Descents}}
An ''ascent'' of a permutation&nbsp;''σ'' of ''n'' is any position ''i''&nbsp;&lt;&nbsp;''n'' where the following value is bigger than the current one. That is, ''i'' is an ascent if <math>\sigma(i)<\sigma(i{+}1)</math>. For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.

Similarly, a ''descent'' is a position ''i''&nbsp;&lt;&nbsp;''n'' with <math>\sigma(i)>\sigma(i{+}1)</math>, so every ''i'' with <math>1 \leq i<n</math> is either an ascent or a descent.

An ''ascending run'' of a permutation is a nonempty increasing contiguous subsequence that cannot be extended at either end; it corresponds to a maximal sequence of successive ascents (the latter may be empty: between two successive descents there is still an ascending run of length&nbsp;1). By contrast an ''increasing subsequence'' of a permutation is not necessarily contiguous: it is an increasing sequence obtained by omitting some of the values of the one-line notation.
For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367.

If a permutation has ''k''&nbsp;−&nbsp;1 descents, then it must be the union of ''k'' ascending runs.{{sfn|Bóna|2004|p=4f}}

The number of permutations of ''n'' with ''k'' ascents is (by definition) the [[Eulerian number]] <math>\textstyle\left\langle{n\atop k}\right\rangle</math>; this is also the number of permutations of ''n'' with ''k'' descents. Some authors however define the Eulerian number <math>\textstyle\left\langle{n\atop k}\right\rangle</math> as the number of permutations with ''k'' ascending runs, which corresponds to {{math|''k'' − 1}} descents.{{sfn|Bona|2012|pages=4–5}}

An exceedance of a permutation ''σ''<sub>1</sub>''σ''<sub>2</sub>...''σ''<sub>''n''</sub> is an index ''j'' such that {{math|''σ''<sub>''j''</sub> > ''j''}}. If the inequality is not strict (that is, {{math|''σ''<sub>''j''</sub> ≥ ''j''}}), then ''j'' is called a ''weak exceedance''. The number of ''n''-permutations with ''k'' exceedances coincides with the number of ''n''-permutations with ''k'' descents.{{sfn|Bona|2012|page=25}}

A ''record'' or ''left-to-right maximum'' of a permutation ''σ'' is an element ''i'' such that ''σ''(''j'') < ''σ''(''i'') for all ''j < i''.

=== Foata's transition lemma ===
[[Dominique Foata|Foata]]'s ''fundamental bijection'' transforms a permutation {{mvar|&sigma;}} with a given canonical cycle form into the permutation <math>f(\sigma) = \hat\sigma   </math> whose one-line notation has the same sequence of elements with parentheses removed.<ref name="Stanley2012" />{{sfn|Bona|2012|pp=109–110}} For example:
<math display="block">\sigma = (513)(6)(827)(94)
= \begin{pmatrix}
1&2&3&4&5&6&7&8&9\\
3&7&5&9&1&6&8&2&4
\end{pmatrix},
</math>

<math display="block">\hat\sigma = 513682794
= \begin{pmatrix}
1&2&3&4&5&6&7&8&9\\
5&1&3&6&8&2&7&9&4
\end{pmatrix}.
</math>

Here the first element in each canonical cycle of {{mvar|&sigma;}} becomes a record (left-to-right maximum) of <math>\hat\sigma
</math>. Given <math>\hat\sigma
</math>, one may find its records and insert parentheses to construct the inverse transformation <math>\sigma=f^{-1}(\hat\sigma)
</math>. Underlining the records in the above example: <math>\hat\sigma = \underline{5}\, 1\, 3\, \underline{6}\, \underline{8}\,2\,7\,\underline{9}\,4
</math>, which allows the reconstruction of the cycles of {{mvar|&sigma;}}.

The following table shows <math>\hat\sigma  </math> and {{mvar|&sigma;}} for the six permutations of ''S'' = {1, 2, 3}, with the bold text on each side showing the notation used in the bijection: one-line notation for <math>\hat\sigma  </math> and canonical cycle notation for {{mvar|&sigma;}}.

<math display="block">
\begin{array}{l|l}
\hat\sigma = f(\sigma)           & \sigma=f^{-1}(\hat\sigma) 
\\
\hline
\mathbf{123}=(\,1\,)(\,2\,)(\,3\,) & 123=\mathbf{(\,1\,)(\,2\,)(\,3\,)}
\\
\mathbf{132}=(\,1\,)(\,3\,2\,) & 132=\mathbf{(\,1\,)(\,3\,2\,)}
\\
\mathbf{213}=(\,2\,1\,)(\,3\,) & 213=\mathbf{(\,2\,1\,)(\,3\,)} 
\\
\mathbf{231}=(\,3\,1\,2\,) & 321=\mathbf{(\,2\,)(\,3\,1\,)} 
\\
\mathbf{312}=(\,3\,2\,1\,) & 231=\mathbf{(\,3\,1\,2\,)} 
\\
\mathbf{321}=(\,2\,)(\,3\,1\,) & 312=\mathbf{(\,3\,2\,1\,)}
\end{array}
</math>
As a first corollary, the number of ''n''-permutations with exactly ''k'' records is equal to the number of ''n''-permutations with exactly ''k'' cycles: this last number is the signless [[Stirling number of the first kind]], <math>c(n, k)</math>. Furthermore, Foata's mapping takes an ''n''-permutation with ''k'' weak exceedances to an ''n''-permutation with {{math|''k'' − 1}} ascents.{{sfn|Bona|2012|pp=109–110}}  For example, (2)(31) = 321 has ''k ='' 2 weak exceedances (at index 1 and 2), whereas {{math|''f''(321) {{=}} 231}} has {{math|1=''k'' − 1 = 1}} ascent (at index 1; that is, from 2 to 3).

===Inversions===
{{main|Inversion (discrete mathematics)}}
[[Image:15-Puzzle.jpg|thumb|In the [[15 puzzle]] the goal is to get the squares in ascending order.  Initial positions which have an odd number of inversions are impossible to solve.<ref name="Slocum">{{cite web
  | last1     = Slocum
  | first1    = Jerry
  | last2     = Weisstein
  | first2    = Eric W.
  | title = 15 – puzzle
  | work = MathWorld
  | publisher = Wolfram Research, Inc.
  | date = 1999
  | url = http://mathworld.wolfram.com/15Puzzle.html
  | access-date = October 4, 2014
}}</ref>]]

An ''[[inversion (discrete mathematics)|inversion]]'' of a permutation&nbsp;''σ'' is a pair {{math|(''i'', ''j'')}} of positions where the entries of a permutation are in the opposite order: <math>i < j</math> and <math>\sigma(i)> \sigma(j)</math>.{{sfn|Bóna|2004|p=43}}  Thus a descent is an inversion at two adjacent positions. For example, {{math|''σ'' {{=}} 23154}} has (''i'', ''j'') = (1, 3), (2, 3), and (4, 5), where (''σ''(''i''), ''σ''(''j'')) = (2, 1), (3, 1), and (5, 4).

Sometimes an inversion is defined as the pair of values (''σ''(''i''), ''σ''(''j'')); this makes no difference for the ''number'' of inversions, and the reverse pair (''σ''(''j''), ''σ''(''i'')) is an inversion in the above sense for the inverse permutation ''σ''<sup>−1</sup>.

The number of inversions is an important measure for the degree to which the entries of a permutation are out of order; it is the same for ''σ'' and for ''σ''<sup>−1</sup>. To bring a permutation with ''k'' inversions into order (that is, transform it into the identity permutation), by successively applying (right-multiplication by) [[adjacent transposition]]s, is always possible and requires a sequence of ''k'' such operations. Moreover, any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition of ''i'' and {{math|''i'' + 1}} where ''i'' is a descent of the permutation as modified so far (so that the transposition will remove this particular descent, although it might create other descents). This is so because applying such a transposition reduces the number of inversions by&nbsp;1; as long as this number is not zero, the permutation is not the identity, so it has at least one descent. [[Bubble sort]] and [[insertion sort]] can be interpreted as particular instances of this procedure to put a sequence into order. Incidentally this procedure proves that any permutation ''σ'' can be written as a product of adjacent transpositions; for this one may simply reverse any sequence of such transpositions that transforms ''σ'' into the identity. In fact, by enumerating all sequences of adjacent transpositions that would transform ''σ'' into the identity, one obtains (after reversal) a ''complete'' list of all expressions of minimal length writing ''σ'' as a product of adjacent transpositions.

The number of permutations of ''n'' with ''k'' inversions is expressed by a [[Mahonian number]].{{sfn|Bóna|2004|pp=43ff}} This is the coefficient of <math>q^k</math> in the expansion of the product

<math display="block">[n]_q! = \prod_{m=1}^n\sum_{i=0}^{m-1}q^i = 
1 \left(1 + q\right)\left(1 + q + q^2\right) \cdots \left(1 + q + q^2 + \cdots + q^{n-1}\right),</math>

The notation <math>[n]_q!</math> denotes the [[q-factorial]]. This expansion commonly appears in the study of [[Necklace (combinatorics)|necklaces]].

Let <math>\sigma \in S_n, i, j\in \{1, 2, \dots, n\} </math> such that <math>i<j</math> and <math>\sigma(i)>\sigma(j)</math>.
In this case, say the weight of the inversion <math>(i, j)</math> is <math>\sigma(i)-\sigma(j)</math>.
Kobayashi (2011) proved the enumeration formula 
<math display="block">\sum_{i<j, \sigma(i)>\sigma(j)}(\sigma(i)-\sigma(j)) = |\{\tau \in S_n \mid \tau\le \sigma, \tau \text{ is bigrassmannian}\}</math>

where <math>\le</math> denotes [[Bruhat order]] in the [[symmetric group]]s. This graded partial order often appears in the context of [[Coxeter group]]s.