[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

- An inversion of a permutation p:=(p1,p2,...,pn) is a pair of positions {i,j} such that i<j and pi>pj. It is represented in MuPAD as a set of two positive integers `{i,j}`.

- The sign of a permutation p is -1 if p has an odd number of inversions, and 1 otherwise.

- The Lehmer code of a permutation is the list (c1,c2,...,cn) such that ci=|{j>i, pi<pj}. Note that ci≤n-i.

- A standard permutation is completely determined by its Lehmer code, and it follows that the Lehmer code provides a bijection between standard permutations of n and words (c1,...,cn) such that ci≤n-i. If w is a non standard permutation, then decoding the Lehmer code of w yields the standardized of w.

- Extending a permutation with fixed points at its end is equivalent to appending zeroes at the end of its Lehmer code. So, the code behaves well with respect to the natural embedding between symmetric groups of different order.

- The functions described here only work for permutations whose elements can be ordered by `<`.

- Let si denote the elementary transposition (i, i+1). A word for the permutation σ is a list (i1, ..., il) such that σ is equal to the product si1si2...sil. A word is said to be reduced if it is of minimal length among all the words for the same permutation. The length of a reduced word for σ is equal to the number of inversions of σ. In MuPAD words are represented by lists of positive integers.

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

- `inversions(permutation p)`

- Returns the list of the inversions of the permutation `p`.

#### Method inversionsNumber: number of inversions of a permutation

- `inversionsNumber(permutation p)`

- Returns the number of inversions of the permutation `p`.

#### Method sign: sign of a permutation

- `sign(permutation p)`

- Returns the sign of the permutation `p`.

#### Method code: Lehmer code of a permutation

- `code(permutation p)`

- Returns the Lehmer code of the permutation `p`.

#### Method fromCode: standard permutation from its code

- `fromCode(Lehmer code c <, non-negative integer n>)`

- Recovers the standard permutation of minimal size from the sequence `c`, appending the minimum necessary number of zeroes to it so that it becomes a Lehmer code.
- The argument `n`, when provided, specifies the size of the returned permutation.

#### Method reducedWord: Reduced word of a standard permutation

- `reducedWord(permutation p)`

- Returns a reduced word of the permutation `p`.

#### Method reducedWords: List of reduced words of a standard permutation

- `reducedWords(permutation p)`

- Returns the list of all reduced words of the permutation `p`.

#### Method fromReducedWord: Standard permutation from a (reduced) word

- `fromReducedWord(reduced word w <, non-negative integer n>)`

- Returns the standard permutation of minimal size that is the product of the elementary transpositions represented by `w`. Note that this word does not need to be reduced.
- The argument `n`, when provided, specifies the size of the returned permutation.

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