# Finite Permutation Groups¶

class sage.categories.finite_permutation_groups.FinitePermutationGroups(base_category)

The category of finite permutation groups, i.e. groups concretely represented as groups of permutations acting on a finite set.

It is currently assumed that any finite permutation group comes endowed with a distinguished finite set of generators (method group_generators); this is the case for all the existing implementations in Sage.

EXAMPLES:

sage: C = PermutationGroups().Finite(); C
Category of finite enumerated permutation groups
sage: C.super_categories()
[Category of permutation groups,
Category of finite groups,
Category of finite finitely generated semigroups]

sage: C.example()
Dihedral group of order 6 as a permutation group

class ElementMethods

Bases: object

class ParentMethods

Bases: object

cycle_index(parent=None)

Return the cycle index of self.

INPUT:

• self - a permutation group $$G$$
• parent – a free module with basis indexed by partitions, or behave as such, with a term and sum method (default: the symmetric functions over the rational field in the $$p$$ basis)

The cycle index of a permutation group $$G$$ (Wikipedia article Cycle_index) is a gadget counting the elements of $$G$$ by cycle type, averaged over the group:

$P = \frac{1}{|G|} \sum_{g\in G} p_{ \operatorname{cycle\ type}(g) }$

EXAMPLES:

Among the permutations of the symmetric group $$S_4$$, there is the identity, 6 cycles of length 2, 3 products of two cycles of length 2, 8 cycles of length 3, and 6 cycles of length 4:

sage: S4 = SymmetricGroup(4)
sage: P = S4.cycle_index()
sage: 24 * P
p[1, 1, 1, 1] + 6*p[2, 1, 1] + 3*p[2, 2] + 8*p[3, 1] + 6*p[4]


If $$l = (l_1,\dots,l_k)$$ is a partition, |G| P[l] is the number of elements of $$G$$ with cycles of length $$(p_1,\dots,p_k)$$:

sage: 24 * P[ Partition([3,1]) ]
8


The cycle index plays an important role in the enumeration of objects modulo the action of a group (Pólya enumeration), via the use of symmetric functions and plethysms. It is therefore encoded as a symmetric function, expressed in the powersum basis:

sage: P.parent()
Symmetric Functions over Rational Field in the powersum basis


This symmetric function can have some nice properties; for example, for the symmetric group $$S_n$$, we get the complete symmetric function $$h_n$$:

sage: S = SymmetricFunctions(QQ); h = S.h()
sage: h( P )
h[4]


Todo

Add some simple examples of Pólya enumeration, once it will be easy to expand symmetric functions on any alphabet.

Here are the cycle indices of some permutation groups:

sage: 6 * CyclicPermutationGroup(6).cycle_index()
p[1, 1, 1, 1, 1, 1] + p[2, 2, 2] + 2*p[3, 3] + 2*p[6]

sage: 60 * AlternatingGroup(5).cycle_index()
p[1, 1, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 24*p[5]

sage: for G in TransitiveGroups(5):               # long time
....:     G.cardinality() * G.cycle_index()
p[1, 1, 1, 1, 1] + 4*p[5]
p[1, 1, 1, 1, 1] + 5*p[2, 2, 1] + 4*p[5]
p[1, 1, 1, 1, 1] + 5*p[2, 2, 1] + 10*p[4, 1] + 4*p[5]
p[1, 1, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 24*p[5]
p[1, 1, 1, 1, 1] + 10*p[2, 1, 1, 1] + 15*p[2, 2, 1] + 20*p[3, 1, 1] + 20*p[3, 2] + 30*p[4, 1] + 24*p[5]


Permutation groups with arbitrary domains are supported (see trac ticket #22765):

sage: G = PermutationGroup([['b','c','a']], domain=['a','b','c'])
sage: G.cycle_index()
1/3*p[1, 1, 1] + 2/3*p[3]


One may specify another parent for the result:

sage: F = CombinatorialFreeModule(QQ, Partitions())
sage: P = CyclicPermutationGroup(6).cycle_index(parent = F)
sage: 6 * P
B[[1, 1, 1, 1, 1, 1]] + B[[2, 2, 2]] + 2*B[[3, 3]] + 2*B[[6]]
sage: P.parent() is F
True


This parent should be a module with basis indexed by partitions:

sage: CyclicPermutationGroup(6).cycle_index(parent = QQ)
Traceback (most recent call last):
...
ValueError: parent should be a module with basis indexed by partitions


REFERENCES:

AUTHORS:

• Nicolas Borie and Nicolas M. Thiéry
profile(n, using_polya=True)

Return the value in n of the profile of the group self.

Optional argument using_polya allows to change the default method.

INPUT:

• n – a nonnegative integer
• using_polya (optional) – a boolean: if True (default), the computation uses Pólya enumeration (and all values of the profile are cached, so this should be the method used in case several of them are needed); if False, uses the GAP interface to compute the orbit.

OUTPUT:

• A nonnegative integer that is the number of orbits of n-subsets under the action induced by self on the subsets of its domain (i.e. the value of the profile of self in n)

EXAMPLES:

sage: C6 = CyclicPermutationGroup(6)
sage: C6.profile(2)
3
sage: C6.profile(3)
4
sage: D8 = DihedralGroup(8)
sage: D8.profile(4, using_polya=False)
8

profile_polynomial(variable='z')

Return the (finite) generating series of the (finite) profile of the group.

The profile of a permutation group G is the counting function that maps each nonnegative integer n onto the number of orbits of the action induced by G on the n-subsets of its domain. If f is the profile of G, f(n) is thus the number of orbits of n-subsets of G.

INPUT:

• variable – a variable, or variable name as a string (default: $$'z'$$)

OUTPUT:

• A polynomial in variable with nonnegative integer coefficients. By default, a polynomial in z over ZZ.

EXAMPLES:

sage: C8 = CyclicPermutationGroup(8)
sage: C8.profile_series()
z^8 + z^7 + 4*z^6 + 7*z^5 + 10*z^4 + 7*z^3 + 4*z^2 + z + 1
sage: D8 = DihedralGroup(8)
sage: poly_D8 = D8.profile_series()
sage: poly_D8
z^8 + z^7 + 4*z^6 + 5*z^5 + 8*z^4 + 5*z^3 + 4*z^2 + z + 1
sage: poly_D8.parent()
Univariate Polynomial Ring in z over Rational Field
sage: D8.profile_series(variable='y')
y^8 + y^7 + 4*y^6 + 5*y^5 + 8*y^4 + 5*y^3 + 4*y^2 + y + 1
sage: u = var('u')
sage: D8.profile_series(u).parent()
Symbolic Ring

profile_series(variable='z')

Return the (finite) generating series of the (finite) profile of the group.

The profile of a permutation group G is the counting function that maps each nonnegative integer n onto the number of orbits of the action induced by G on the n-subsets of its domain. If f is the profile of G, f(n) is thus the number of orbits of n-subsets of G.

INPUT:

• variable – a variable, or variable name as a string (default: $$'z'$$)

OUTPUT:

• A polynomial in variable with nonnegative integer coefficients. By default, a polynomial in z over ZZ.

EXAMPLES:

sage: C8 = CyclicPermutationGroup(8)
sage: C8.profile_series()
z^8 + z^7 + 4*z^6 + 7*z^5 + 10*z^4 + 7*z^3 + 4*z^2 + z + 1
sage: D8 = DihedralGroup(8)
sage: poly_D8 = D8.profile_series()
sage: poly_D8
z^8 + z^7 + 4*z^6 + 5*z^5 + 8*z^4 + 5*z^3 + 4*z^2 + z + 1
sage: poly_D8.parent()
Univariate Polynomial Ring in z over Rational Field
sage: D8.profile_series(variable='y')
y^8 + y^7 + 4*y^6 + 5*y^5 + 8*y^4 + 5*y^3 + 4*y^2 + y + 1
sage: u = var('u')
sage: D8.profile_series(u).parent()
Symbolic Ring

example()

Returns an example of finite permutation group, as per Category.example().

EXAMPLES:

sage: G = FinitePermutationGroups().example(); G
Dihedral group of order 6 as a permutation group

extra_super_categories()

Any permutation group is assumed to be endowed with a finite set of generators.