Dom::PermutationGroup – permutation group
Dom::PermutationGroup(n, generatorsoptions) creates a domain for the group of permutations of generated by generators.
Creating the Type
Dom::PermutationGroup(n)
Parameters:
n: |
positive integer |
generators: |
list of permutations of |
Details:
A permutation of elements is a bijective mapping of the set onto itself.
With functional composition as the operation, the permutations of elements form a group of order . The domain Dom::PermutationGroup(n, generatorsoptions) represents the particular subgroup generated by the provided generators.
Creating Elements
Dom::PermutationGroup(n)(l)
Parameters:
l: |
list or array consisting of the first integers in some order. |
Superdomain
Categories
Axioms
Axioms
Related Domains:
combinat::permutations, Dom::DihedralGroup, Dom::SymmetricGroup
Details:
The domain element Dom::PermutationGroup(n)(l) represents the bijective mapping of the first positive integers that maps the integer to l[i], for .
Entries
"one" |
the identical mapping of the set to itself. |
Mathematical Methods
_mult – product of permutations
(Dom::PermutationGroup(n))::_mult(dom , ...)
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 function _mult.
_invert – inverse of a permutation
(Dom::PermutationGroup(n))::_invert(dom a)
This method computes a permutation b such that 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 and .
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 ; 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.
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 is the identity.
inversions – number of inversions
(Dom::PermutationGroup(n))::inversions(dom a)
This method computes the number of all pairs of integers for which but .
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 if its number of inversions is even, and otherwise.
random – random permutation
(Dom::PermutationGroup(n))::random()
This method returns a random element of the permutation group.
Access Methods
allElements – elements of the group
(Dom::PermutationGroup(n))::allElements()
This method returns the list of the elements of the group.
size – size of the group
(Dom::PermutationGroup(n))::size()
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 through 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.
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();
4
[[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))