combinat::permutations::leequalBruhat
--
Bruhat order on standard permutations
Functions related to the Bruhat order on permutations.
leequalBruhat(standard permutations p1, p2)
p1
smaller than
p2
in the Bruhat order?''
bruhatInversions(standard permutation p)
p
such that the application of
this inversion to p
decrements its number of inversions.
predBruhat(standard permutation p)
p
in the
Bruhat order, such that there is no permutation between one of those and
p
.
succBruhat(standard permutation p)
p
in the
Bruhat order, such that there is no permutation between p
and
one of those.
smallerBruhat(standard permutation p)
p
in
the Bruhat order.
greaterBruhat(standard permutation p)
p
in
the Bruhat order.To check whether a permutation is smaller than another thanks to the Bruhat order, you can call:
>> combinat::permutations::leequalBruhat([2,4,3,1],[3,4,2,1]);
TRUE
You can ask for the inversions of a given permutation by:
>> combinat::permutations::bruhatInversions([6, 1, 4, 5, 2, 3])
[{1, 2}, {1, 3}, {1, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}]
Applying those inversions to the previous permutation, you exactly get the permutations preceding it as you can check with
>> combinat::permutations::predBruhat([6, 1, 4, 5, 2, 3])
[[1, 6, 4, 5, 2, 3], [4, 1, 6, 5, 2, 3], [5, 1, 4, 6, 2, 3], [6, 1, 2, 5, 4, 3], [6, 1, 3, 5, 2, 4], [6, 1, 4, 2, 5, 3], [6, 1, 4, 3, 2, 5]]
Now, you can compute the transitive ideal generated by the predecessor relation and get (on the previous example, the answer is one page long)
>> combinat::permutations::smallerBruhat([4, 1, 2, 3])
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3], [3, 1, 2, 4], [4, 1, 2, 3]]
What was done with the permutations preceding a given one or smaller than it, can also be performed by the permutations succeeding a given one or greater than it by:
>> combinat::permutations::succBruhat([6, 1, 4, 5, 2, 3]);
combinat::permutations::greaterBruhat([4, 1, 2, 3])
[[6, 4, 1, 5, 2, 3], [6, 2, 4, 5, 1, 3], [6, 1, 5, 4, 2, 3], [6, 1, 4, 5, 3, 2]] [[4, 3, 2, 1], [4, 3, 1, 2], [4, 2, 3, 1], [4, 2, 1, 3], [4, 1, 3, 2], [4, 1, 2, 3]]
MuPAD Combinat, an open source algebraic combinatorics package