combinat::permutations::inversions
--
inversions, Lehmer code and reduced words of permutations
Functions related to inversions of permutations.
{i,j}
.<
.
inversions(permutation p)
p
.
inversionsNumber(permutation p)
p
.
sign(permutation p)
p
.
code(permutation p)
p
.
fromCode(Lehmer code c <, non-negative integer n>)
c
, appending the minimum necessary number of zeroes to it so that
it becomes a Lehmer code.n
, when provided, specifies the size of the
returned permutation.
reducedWord(permutation p)
p
.
reducedWords(permutation p)
p
.
fromReducedWord(reduced word w <, non-negative integer n>)
w
. Note that this word
does not need to be reduced.n
, when provided, specifies the size of the
returned permutation.The number of inversions of a permutation, also called its length, can be computed with:
>> combinat::permutations::inversionsNumber([1, 2, 6, 4, 7, 3, 5])
6
Here is the list of the 6 inversions of the previous permutation:
>> combinat::permutations::inversions([1, 2, 6, 4, 7, 3, 5])
[{3, 4}, {3, 6}, {3, 7}, {4, 6}, {5, 6}, {5, 7}]
Note that this also works for non-standard permutations, as
long as the elements can be ordered with <
:
>> combinat::permutations::inversionsNumber([1, 3, 2, 1, 2, 1]);
combinat::permutations::inversions([1, 3, 2, 1, 2, 1]);
combinat::permutations::inversions(["c", "b", "a"])
7 [{2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 6}, {5, 6}] [{1, 2}, {1, 3}, {2, 3}]
The sign of any transposition is -1:
>> combinat::permutations::sign([4, 2, 3, 1, 5])
-1
Furthermore, the sign defines a multiplicative morphism from the symmetric group into {-1,1}. We check this for the symmetric group of order 4:
>> bool(_and(combinat::permutations::sign(combinat::permutations::_mult(p,q))
= combinat::permutations::sign(p)*combinat::permutations::sign(q)
$ p in combinat::permutations(4)
$ q in combinat::permutations(4)))
TRUE
The code provides a bijection between permutations of
[$1..n]
and lists c
of length n
such that c[i]<=n-i
:
>> for p in combinat::permutations(3) do
code := combinat::permutations::code(p);
p2 := combinat::permutations::fromCode(code);
print(p, code, p2);
end_for
[1, 2, 3], [0, 0, 0], [1, 2, 3] [1, 3, 2], [0, 1, 0], [1, 3, 2] [2, 1, 3], [1, 0, 0], [2, 1, 3] [2, 3, 1], [1, 1, 0], [2, 3, 1] [3, 1, 2], [2, 0, 0], [3, 1, 2] [3, 2, 1], [2, 1, 0], [3, 2, 1]
If w is a non standard permutation, then decoding the code of w yields the standardized of w:
>> w := [2, 3, 1, 2, 2, 4, 5, 1]:
code := combinat::permutations::code(w);
combinat::words::standard(w), combinat::permutations::fromCode(code)
[2, 4, 0, 1, 1, 1, 1, 0] [3, 6, 1, 4, 5, 7, 8, 2], [3, 6, 1, 4, 5, 7, 8, 2]
The permutation corresponding to a given product of elementary transpositions can be computed with:
>> combinat::permutations::fromReducedWord([3,2,3,1,2,3,1]);
[3, 4, 2, 1]
The word we entered previously is not reduced. Indeed, all
reduced words of a given permutation have the same length, equal to
the number of inversions of [3, 4, 2, 1]
. It is not the case of the
product we studied before.
>> map(combinat::permutations::reducedWords([3,4,2,1]),nops);
nops([3,2,3,1,2,3,1]);
[5, 5, 5, 5, 5] 7
If you have an action of the symmetric group on a set, defined by the action of the elementary transpositions, you can compute a reduced decomposition of a given permutation with:
>> combinat::permutations::reducedWord([3,5,4,6,2,1]);
[2, 1, 4, 3, 2, 4, 3, 5, 4, 5]
MuPAD Combinat, an open source algebraic combinatorics package