Content deleted Content added
→Weak order of permutations: Link to Hasse diagram page |
m clean up spacing around commas and other punctuation fixes, replaced: ,B → , B, ,m → , m, ,x → , x |
||
Line 12:
There is an '''inversion''' of <math>\pi</math> between <math>i</math> and <math>j</math> if <math>i < j</math> and <math>\pi(i) > \pi(j)</math>. The inversion is indicated by an ordered pair containing either the places <math>(i, j)</math>{{sfn|Aigner|2007|pp=27}}{{sfn|Comtet|1974|pp=237}} or the elements <math>\bigl(\pi(i), \pi(j)\bigr)</math>.{{sfn|Knuth|1973|pp=11}}{{sfn|Pemmaraju|Skiena|2003|pp=69}}{{sfn|Vitter|Flajolet|1990|pp=459}}
The [[#Example:_All_permutations_of_four_elements|inversion set]] is the set of all inversions. A permutation's inversion set using place-based notation is the same as the [[Permutation#Definition|inverse permutation's]] inversion set using element-based notation with the two components of each ordered pair exchanged. Likewise, a permutation's inversion set using element-based notation is the same as the inverse permutation's inversion set using place-based notation with the two components of each ordered pair exchanged.{{sfn|Gratzer|2016|pp=221}}
Inversions are usually defined for permutations, but may also be defined for sequences:<br>Let <math>S</math> be a [[sequence]] (or [[multiset]] permutation{{sfn|Bóna|2012|pp=57}}). If <math>i < j</math> and <math>S(i) > S(j)</math>, either the pair of places <math>(i, j)</math>{{sfn|Bóna|2012|pp=57}}{{sfn|Cormen|Leiserson|Rivest|Stein|2001|pp=39}} or the pair of elements <math>\bigl(S(i), S(j)\bigr)</math>{{sfn|Barth|Mutzel|2004|pp=183}} is called an inversion of <math>S</math>.
Line 71:
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 (order)|lattice]].
The [[
If a permutation is assigned to each inversion set using the place-based definition, the resulting order of permutations is that of the permutohedron, where an edge corresponds to the swapping of two elements with consecutive values. This is the weak order of permutations. The identity is its minimum, and the permutation formed by reversing the identity is its maximum.
Line 120:
|url = https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics
| chapter = 6.4 Inversions of a permutation of [n]
| publisher = D. Reidel Pub. Co | ___location = Dordrecht, Boston | year = 1974 | isbn = 9027704414 }}
* {{cite book
| first1=Thomas H. |last1=Cormen |authorlink1=Thomas H. Cormen
| |||