combinat::permutations::cycles
--
cycle decomposition of standard permutations
Functions related to cycle decomposition of standard permutations.
[c1,...,ck]
. This representation is unique if, for
example, c1
is chosen to be minimal.
cycles(standard permutation p)
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.
cycleType(standard permutation p)
p
, as a
partition. This is the decreasing list of the lengths of the
cycles of p
.
fromCycles(list of list of integers cycleList <, integer n>)
cycleList
.1
may be omitted if the greatest element
of the permutation is not in a cycle of length 1
.n
, when provided, specifies the size of the
returned permutation.
fixedPoints(standard permutation p)
p
.
fixedPointsNumber(standard permutation p)
p
.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
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]
MuPAD Combinat, an open source algebraic combinatorics package