Science Fair Project Encyclopedia
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.
Last updated: 08-22-2005 14:07:18
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details