Editing Permutation (section)

===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.