World Library  
Flag as Inappropriate
Email this Article

Weak order of permutations

Article Id: WHEBN0000595010
Reproduction Date:

Title: Weak order of permutations  
Author: World Heritage Encyclopedia
Language: English
Subject: Permutation, List of permutation topics, Order (mathematics)
Publisher: World Heritage Encyclopedia

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.


Formally, let (A(1), \ldots, A(n)) be a sequence of n distinct numbers. If i < j and A(i) > A(j), then the pair (i, j) 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{inv}(A) = \# \{(A(i),A(j)) \mid i < j \text{ and } A(i) > A(j)\}.[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[i] = \left\vert\{k \mid k < i \text{ and } A(k) > A(i)\}\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.

See also

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


Source bibliography

Further reading

Presortedness measures

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.