#jsDisabledContent { display:none; } My Account |  Register |  Help

# Weak order of permutations

Article Id: WHEBN0000595010
Reproduction Date:

 Title: Weak order of permutations Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Weak order of permutations

In computer science and discrete mathematics, an inversion is a pair of places of a sequence where the elements on these places are out of their natural order.

## Definitions

Formally, let $\left(A\left(1\right), \ldots, A\left(n\right)\right)$ be a sequence of n distinct numbers. If $i < j$ and $A\left(i\right) > A\left(j\right)$, then the pair $\left(i, j\right)$ is called an inversion of $A$.[1][2]

The inversion number of a sequence is one common measure of its sortedness.[3][2] Formally, the inversion number is defined to be the number of inversions, that is,

$\text\left\{inv\right\}\left(A\right) = \# \\left\{\left(A\left(i\right),A\left(j\right)\right) \mid i < j \text\left\{ and \right\} A\left(i\right) > A\left(j\right)\\right\}$.[3]

Other measures of (pre-)sortedness include the minimum number of elements that can be deleted from the sequence to yield a fully sorted sequence, the number and lengths of sorted "runs" within the sequence, and the smallest number of exchanges needed to sort the sequence.[4] Standard comparison sorting algorithms can be adapted to compute the inversion number in time O(n log n).

The inversion vector V(i) of the sequence is defined for i = 2, ..., n as $V\left[i\right] = \left\vert\\left\{k \mid k < i \text\left\{ and \right\} A\left(k\right) > A\left(i\right)\\right\}\right\vert$. In other words each element is the number of elements preceding the element in the original sequence that are greater than it. Note that the inversion vector of a sequence has one less element than the sequence, because of course the number of preceding elements that are greater than the first is always zero. Each permutation of a sequence has a unique inversion vector and it is possible to construct any given permutation of a (fully sorted) sequence from that sequence and the permutation's inversion vector.[5]

## Weak order of permutations

The set of permutations on n items can be given the structure of a partial order, called the weak order of permutations, which forms a lattice.

To define this order, consider the items being permuted to be the integers from 1 to n, and let Inv(u) denote the set of inversions of a permutation u for the natural ordering on these items. That is, Inv(u) is the set of ordered pairs (i, j) such that 1 ≤ i < jn and u(i) > u(j). Then, in the weak order, we define uv whenever Inv(u) ⊆ Inv(v).

The edges of the Hasse diagram of the weak order are given by permutations u and v such that u < v and such that v is obtained from u by interchanging two consecutive values of u. These edges form a Cayley graph for the group of permutations that is isomorphic to the skeleton of a permutohedron.

The identity permutation is the minimum element of the weak order, and the permutation formed by reversing the identity is the maximum element.

Sequences in the OEIS:

• Index entries for sequences related to factorial numbers
• Reflected inversion vectors: A108731
• Sum of inversion vectors, cardinality of inversion sets: A034968
• Inversion sets of finite permutations interpreted as binary numbers: A211363)
• Finite permutations that have only 0s and 1s in their inversion vectors: A211364)
• Numbers of permutations of n elements with k inversions; Mahonian numbers: A000140)
• Number of connected labeled graphs with n edges and n nodes: A057500
• Arrays of permutations with similar inversion sets and inversion vectors: A051683