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 < j ≤ n and u(i) > u(j). Then, in the weak order, we define u ≤ v 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.
Read more about this topic: Inversion (discrete Mathematics)
Famous quotes containing the words weak, order and/or permutations:
“Power corrupts ... when the weak band together in order to ruin the strong, but not before. The will to power ... far from being a characteristic of the strong, is, like envy and greed, among the vices of the weak, and possibly even their most dangerous one.”
—Hannah Arendt (1906–1975)
“The intellectual is a middle-class product; if he is not born into the class he must soon insert himself into it, in order to exist. He is the fine nervous flower of the bourgeoisie.”
—Louise Bogan (1897–1970)
“The new shopping malls make possible the synthesis of all consumer activities, not least of which are shopping, flirting with objects, idle wandering, and all the permutations of these.”
—Jean Baudrillard (b. 1929)