Dom::PermutationGroup – permutation group

Dom::PermutationGroup(n, generatorsoptions) creates a domain for the group of permutations of math generated by generators.

→ Examples

Creating the Type




positive integer


list of permutations of math


Creating Elements




list or array consisting of the first math integers in some order.









Related Domains:

combinat::permutations, Dom::DihedralGroup, Dom::SymmetricGroup


The domain element Dom::PermutationGroup(n)(l) represents the bijective mapping of the first math positive integers that maps the integer math to l[i], for math.



the identical mapping of the set math to itself.

Mathematical Methods

_mult – product of permutations

(Dom::PermutationGroup(n))::_mult(dom math, ...)

The product math of permutations is defined to be the mapping that assigns, to every integer i between math and math, the integer a1(...ak(i)).

This method overloads the function _mult.

_invert – inverse of a permutation

(Dom::PermutationGroup(n))::_invert(dom a)

This method computes a permutation b such that math is the identity mapping.

This method overloads the function _invert.

func_call – function value of a permutation at a point

(Dom::PermutationGroup(n))::func_call(dom a, integer i)

This method overloads the round brackets (...), i.e. it may be called in the form a(i).

It computes the function value of a at i, i.e., the integer that i is mapped to by the permutation a; i must be an integer between math and math.

cycles – cycle representation of a permutation

(Dom::PermutationGroup(n))::cycles(dom a)

This method computes a cycle representation of a. A cycle representation is a list math; each of the orbits is a list of integers of the form [i, a(i), a(a(i)), Symbol:hellip] with just as many elements such that i does not occur in it for a second time; and each integer between math and math appears in exactly one of the orbits.

order – order of a permutation

(Dom::PermutationGroup(n))::order(dom a)

The order of a is defined to be the least positive integer k for which math is the identity.

inversions – number of inversions

(Dom::PermutationGroup(n))::inversions(dom a)

This method computes the number of all pairs math of integers for which math but math.

sign – sign of a permutation

(Dom::PermutationGroup(n))::sign(dom a)

This method returns the sign of the permutation a. The sign of a permutation is defined to be math if its number of inversions is even, and math otherwise.

random – random permutation


This method returns a random element of the permutation group.

Access Methods

allElements – elements of the group


This method returns the list of the elements of the group.

size – size of the group


This method returns the size of the group.

Conversion Methods

convert – conversion of an object into a permutation

(Dom::PermutationGroup(n))::convert(any x)

This method tries to convert x into a permutation. This is only possible if x is a list or an array in which each of the integers math through math occurs exactly once.

convert_to – conversion of a permutation into another type

(Dom::PermutationGroup(n))::convert_to(dom a, any T)

Tries to convert a into type T. Currently, only a conversion into a list of type DOM_LIST is possible.

expr – convert a permutation into a list

(Dom::PermutationGroup(n))::expr(dom a)

This method returns a list such that generating a permutation from that list would result in a.

Example 1:

We construct the cyclic group of order math, generated by the cycle math.:

C4 := Dom::PermutationGroup(4, [[[1,2,3,4]]])


It has math elements:





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


This group belongs to the following categories:



We can construct a permutation of C4 by providing the images of math, math, etc.:

p := C4([2,1,4,3]);

p(1), p(2), p(3), p(4);



Alternatively, the permutation can be constructed from its disjoint cycle representation:



We now consider the action of C4 on lists of length math, a permutation of C4 acting naturally on such a list by permutation of the positions:

p([a, b, c, d])


Now, here is the orbit of the list [2,3,2,1] w.r.t. this action of C4:

C4::orbit([2, 3, 2, 1])


A canonical representative for this orbit can be chosen by taking the lexicographically maximal element:

C4::canonic([2, 3, 2, 1])


Example 2:

We now construct several classical permutation groups and show some more advanced computations with them. Let us start by Her Majesty the symmetric group acting of 1,2,3,4, and list all its elements:

n := 4:

S4 := Dom::SymmetricGroup(n):



Then, the alternating group math:

A4 := Dom::AlternatingGroup(4):


This is the direct product of math and math acting naturally on the Cartesian product math:

S3   := Dom::SymmetricGroup(3):

S3A4 := Dom::PermutationGroupDirectProduct([S3, A4]):



And finally the symmetric group math acting on pairs of math:

G4 := Dom::PermutationGroupOnSets(S4,2):

It is of size math, and acts on the set of the math pairs of elements of math:







Let math be the permutation induced on pairs of math by the permutation [4,3,2,1]

s := G4::induced(S4([4, 3, 2, 1]));

s({1, 2})



math acts on integer vectors of length math. Each such list corresponds to a non oriented multigraph on math nodes, and each list of math and math corresponds to a simple non oriented graph

Given an alphabet math, one can consider the weighted graphs where each edge takes one of the weights math. The weight of such a graph is the product of the weights of its edges.

By evaluating the cycle indicator polynomial on the alphabet, one get the sum of the weights of all the considered graphs. In particular, by taking the alphabet math, one obtain the total number of simple graphs on math nodes:

expand(P([1, 1]))


whereas with the alphabet math, one get the generating series of those simple graphs on math nodes by number of edges:

expand(P([1, t]))


If one is instead interested in counting multigraphs (graphs with multiple edges) by number of edges, the cycle indicator polynomial can be evaluated on the infinite alphabet math. Infinite alphabets are not yet directly supported by MuPAD-Combinat; however this can easily be emulated by hand since the evaluation of the symmetric powersum math on the alphabet math is obtained by encoding math as math and substituting math by math in this formula:

_plus(_mult(op(term, 1), 1/(1 - q^k) $ k in op(term, 2))

      $ term in poly2list(P))