[Previous] [Next] [Contents]

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

## `combinat::permutations::descents` -- descents of permutations

#### Introduction

Functions related to descents of permutations.

#### Details

- A descent of a permutation p=(p1,p2,...,pn) is an integer i such that and pi>pi+1.
- Let des=(d1,d2,...,dk) be the increasing list of the descents of a permutation p. Let I=(d1,d2-d1,d3-d2,...,dk-dk-1) be its corresponding composition. We say that I is the ribbon shape of p, or, equivalently that p has I as ribbon shape.

#### Method descents: list of the descents of a permutation

- `descents(permutation p <, FinalDescent>)`

- Returns the list of the descents of the permutation `p`, that is, the list of integers i such that `p[i]>p[i+1]`.
- With the option FinalDescent, the last position of a non empty permutation is also considered as a descent.

#### Method descentsNumber: number of descents of a permutation

- `descentsNumber(permutation p <, FinalDescent>)`

- Returns the number of descents of the permutation `p`.
- With the option FinalDescent, the last position of a non empty permutation is also considered as a descent.

#### Method majorIndex: major index of a permutation

- `majorIndex(permutation p <, FinalDescent>)`

- Returns the major index of the permutation `p`, that is the sum of the descents of `p`.
- With the option FinalDescent, the last position of a non empty permutation is also considered as a descent.

#### Method descentPolynomial: descent polynomial of a permutation

- `descentPolynomial(permutation p, variable z)`

- Returns the descent polynomial of the permutation `p` in the variable `z`. It is the product of the monomials `z[p[1]]z[p[2]]...z[p[i]]` for all descents `i` of the permutation `p`.
- Note that the the last position of a non empty permutation is never considered as a descent.

#### Method descentsToMin: smallest permutation having a given descent set

- `descentsToMin(list or set s <, integer n>)`

- Returns the standard permutation of minimal size and smallest one with respect to the number of inversions that has the given descent set. Note that this minimal size corresponds to the greatest element in `s`.
- The argument `n`, when provided, specifies the size of the returned permutation.

#### Method descentsToMax: greatest permutation having a given descent set

- `descentsToMax(list or set s <, integer n>)`

- Returns the standard permutation of minimal size and greatest one with respect to the number of inversions that has the given descent set. Note that this minimal size corresponds to the greatest element in `s`.
- The argument `n`, when provided, specifies the size of the returned permutation.

#### Method descentsCompositionToMin: smallest permutation having a given ribbon shape

- `descentsCompositionToMin(composition s)`

- Returns the standard permutation of minimal size and smallest one with respect to the number of inversions that has the ribbon shape `s`. Note that this minimal size corresponds to the sum of the entries of `s`.

#### Method descentsCompositionToMax: greatest permutation having a given ribbon shape

- `descentsCompositionToMax(composition s)`

- Returns the standard permutation of minimal size and greatest one with respect to the number of inversions that has the ribbon shape `s`. Note that this minimal size corresponds to the sum of the entries of `s`.

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

- `fromDescents(list or set s <, integer n>)`

- Returns the list of standard permutations of minimal size having the descent set `s`. Note that this minimal size corresponds to the greatest element in `s`.
- The argument `n`, when provided, specifies the size of the returned permutation.

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

- `fromDescentsComposition(composition s)`

- Returns the list of standard permutations of minimal size that have the ribbon shape `s`. Note that this minimal size corresponds to the sum of the entries of `s`.

#### 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