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.
|
|
