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 < j ≤ n
and
- 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.