[Previous] [Next] [Contents]

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

combinat::permutations::descents -- descents of permutations

Introduction

Functions related to descents of permutations.

Details

Method descents: list of the descents of a permutation

Method descentsNumber: number of descents of a permutation

Method majorIndex: major index of a permutation

Method descentPolynomial: descent polynomial of a permutation

Method descentsToMin: smallest permutation having a given descent set

Method descentsToMax: greatest permutation having a given descent set

Method descentsCompositionToMin: smallest permutation having a given ribbon shape

Method descentsCompositionToMax: greatest permutation having a given ribbon shape

Method fromDescents: list of standard permutations with a given descent set

Method fromDescentsComposition: list of standard permutations having a given ribbon shape

Example 1

The descents of a permutation are computed as:

>> combinat::permutations::descents([2, 1, 6, 4, 7, 3, 5])
     
                                 [1, 3, 5]
        

The sum of the descents is called the major index:

>> combinat::permutations::majorIndex([2, 1, 6, 4, 7, 3, 5])
     
                                     9
        

It is the total degree of the descent polynomial, that is always a monomial on permutations:

>> combinat::permutations::descentPolynomial([2, 1, 6, 4, 7, 3, 5],z)
     
                            2     3          2
                        z[1]  z[2]  z[4] z[6]  z[7]
        

Example 2

To compute the smallest element of a descent class, you can use:

>> combinat::permutations::descentsToMin([2, 1, 5, 9], 12)
     
                  [3, 2, 1, 4, 6, 5, 7, 8, 10, 9, 11, 12]
        

To get the same result using ribbon shapes, one can write:

>> combinat::permutations::descentsCompositionToMin([1, 1, 3, 4, 3])
     
                  [3, 2, 1, 4, 6, 5, 7, 8, 10, 9, 11, 12]
        

To compute the greatest element of a descent class, you can use:

>> combinat::permutations::descentsToMax([2, 1, 5, 9], 12)
     
                  [12, 11, 8, 9, 10, 4, 5, 6, 7, 1, 2, 3]
        

To get the same result using ribbon shapes, one can write:

>> combinat::permutations::descentsCompositionToMax([1, 1, 3, 4, 3])
     
                  [12, 11, 8, 9, 10, 4, 5, 6, 7, 1, 2, 3]
        

Example 3

To compute the list of permutations that have a given descent set, you can use:

>> combinat::permutations::fromDescents([3, 5, 1])
     
      [[2, 1, 4, 3, 5], [2, 1, 5, 3, 4], [3, 1, 4, 2, 5],
      
         [3, 1, 5, 2, 4], [3, 2, 4, 1, 5], [3, 2, 5, 1, 4],
      
         [4, 1, 3, 2, 5], [4, 1, 5, 2, 3], [4, 2, 3, 1, 5],
      
         [4, 2, 5, 1, 3], [4, 3, 5, 1, 2], [5, 1, 3, 2, 4],
      
         [5, 1, 4, 2, 3], [5, 2, 3, 1, 4], [5, 2, 4, 1, 3],
      
         [5, 3, 4, 1, 2]]
        

To get the same result using ribbon shapes, one can write:

>> combinat::permutations::fromDescentsComposition([1, 2, 2])
     
      [[2, 1, 4, 3, 5], [2, 1, 5, 3, 4], [3, 1, 4, 2, 5],
      
         [3, 1, 5, 2, 4], [3, 2, 4, 1, 5], [3, 2, 5, 1, 4],
      
         [4, 1, 3, 2, 5], [4, 1, 5, 2, 3], [4, 2, 3, 1, 5],
      
         [4, 2, 5, 1, 3], [4, 3, 5, 1, 2], [5, 1, 3, 2, 4],
      
         [5, 1, 4, 2, 3], [5, 2, 3, 1, 4], [5, 2, 4, 1, 3],
      
         [5, 3, 4, 1, 2]]
        

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package