Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Weak order of permutations
Main Page | See live article | Alphabetical index

Weak order of permutations

In mathematics, the symmetric group, Sn, has a poset structure given by the weak order of permutations, given by u≤v if Inv(u) is a subset of Inv(v). Here Inv(u) is the set of inversions of u, defined as the set of ordered pairs (i, j) with

1 ≤ i < jn


u(i) > u(j).

The edges of the Hasse diagram of the order are given by permutations u and v such that

u < v

and v is obtained from u by interchanging two consecutive values of u.

The identity permutation is the minimum element of Sn and the permutation (n n-1 ... 1) is the maximum element.

Moreover, Sn is a lattice with this order.

This article is a stub. You can help Wikipedia by [ expanding it].