[Previous] [Next] [Contents]

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

## `combinat::permutations::cycles` -- cycle decomposition of standard permutations

#### Introduction

Functions related to cycle decomposition of standard permutations.

#### Details

- A cycle p:=(c1,c2,...,ck) of length k is the permutation such that p(c1):=c2, p(c2):=c3, ..., p(ck):=c1, and p(i):=i for i∈{c1,...,ck}. Such a cycle is represented in MuPAD by a list `[c1,...,ck]`. This representation is unique if, for example, `c1` is chosen to be minimal.

- A cycle of length 1 is equal to the identity permutation and is called trivial.

- Two disjoint cycles commute.

- Any standard permutation p can be written as a product of disjoint cycles. This is called the cycle decomposition of p. It is unique up to the order of the cycles, and up to the first element of the cycles.

#### Method cycles: cycle decomposition of a standard permutation

- `cycles(standard permutation p)`

- Returns the cycle decomposition of `p`. This is the list of the non-trivial cycles of `p`. Each cycle is represented by the list `[i, p[i], p[p[i]], ...]` of its elements starting from the smallest one. The cycles themselves are sorted increasingly w.r.t. their first element.

#### Method cycleType: cycle type of a standard permutation

- `cycleType(standard permutation p)`

- Returns the cycle type of the permutation `p`, as a partition. This is the decreasing list of the lengths of the cycles of `p`.

#### Method fromCycles: standard permutation from its cycle decomposition

- `fromCycles(list of list of integers cycleList <, integer n>)`

- Returns the standard permutation of minimal size that has the given cycle list. Note that this minimal size corresponds to the greatest element in `cycleList`.
- Trivial cycles of length `1` may be omitted if the greatest element of the permutation is not in a cycle of length `1`.
- The argument `n`, when provided, specifies the size of the returned permutation.

#### Method fixedPoints: list of the fixed points of a standard permutation

- `fixedPoints(standard permutation p)`

- Returns the list of the fixed points of `p`.

#### Method fixedPointsNumber: number of fixed points of a standard permutation

- `fixedPointsNumber(standard permutation p)`

- Returns the number of fixed points of `p`.

#### Example 1

The cycles of a permutation can be computed with:

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

                                [[1, 3], [2, 5, 4]]

You can recover the initial permutation by two different ways, forgetting or not the cycle of length 1:

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

                         [3, 5, 1, 4, 2], [3, 5, 1, 4, 2]

You can generate the list of permutations with a given cycle type, which is a conjugacy class of the symmetric group, and then check that their number corresponds to the usual formula:

    >> select(combinat::permutations::list(4),
         z-> combinat::permutations::cycleType(z)=[2,2]);
       nops(%), 4!/(2^2*2!);

                    [[2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1]]

                                       3, 3

#### Example 2

To compute the list or the number of fixed points of a permutation, you can use:

    >> combinat::permutations::fixedPoints([6, 7, 3, 8, 5, 9, 2, 1, 4]);
       combinat::permutations::fixedPointsNumber([6, 7, 3, 8, 5, 9, 2, 1, 4]);

                                      [3, 5]

                                         2

It can be used to quickly get an estimation of the number of permutations without fixed points, using the following main block inside a loop, and check the hats paradox:

    >> combinat::permutations::fixedPoints(combinat::permutations::random(20));

                                       [13]

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package