Dom::PermutationGroup

Dom::PermutationGroup(n, generatorsoptions) creates a domain for the group of permutations of

generated by generators.

The domain element Dom::PermutationGroup(n)(l) represents the bijective mapping of the first

positive integers that maps the integer

to l[i], for

The product

of permutations is defined to be the mapping that assigns, to every integer i between

and

, the integer a1(...ak(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

and

This method computes a cycle representation of a. A cycle representation is a list

; 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

and

appears in exactly one of the orbits.

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

is the identity.

This method returns the sign of the permutation a. The sign of a permutation is defined to be

if its number of inversions is even, and

otherwise.

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

through

occurs exactly once.

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

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

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

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

It has elements:

C4::size;

C4::allElements();

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

This group belongs to the following categories:

C4::allCategories()

We can construct a permutation of C4 by providing the images of , , 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:

C4([[1,2],[3,4]])

We now consider the action of C4 on lists of length , 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])

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):

S4::allElements()

Then, the alternating group :

A4 := Dom::AlternatingGroup(4):

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

S3 := Dom::SymmetricGroup(3):

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

S3A4::set

And finally the symmetric group acting on pairs of :

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

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

G4::size;

G4::card;

G4::set

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

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

s({1, 2})

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

Given an alphabet , one can consider the weighted graphs where each edge takes one of the weights . 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 , one obtain the total number of simple graphs on nodes:

expand(P([1, 1]))

whereas with the alphabet , one get the generating series of those simple graphs on 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 . 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 on the alphabet is obtained by encoding as and substituting by in this formula:

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

$ term in poly2list(P))

math