[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

combinat::permutations::inversions -- inversions, Lehmer code and reduced words of permutations

Introduction

Functions related to inversions of permutations.

Details

Method inversions: list of the inversions of a permutation

Method inversionsNumber: number of inversions of a permutation

Method sign: sign of a permutation

Method code: Lehmer code of a permutation

Method fromCode: standard permutation from its code

Method reducedWord: Reduced word of a standard permutation

Method reducedWords: List of reduced words of a standard permutation

Method fromReducedWord: Standard permutation from a (reduced) word

Example 1

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
        

Example 2

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]
        

Example 3

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]
        

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package