CycleIndexPolynomial
CycleIndexPolynomial[perm,{x1,…,xn}]
constructs the cycle index monomial of the permutation perm in the variables xi.
CycleIndexPolynomial[group,{x1,…,xn}]
constructs the cycle index polynomial of group in the variables xi.
Details
- The cycle index polynomial of a permutation group gives useful information to solve enumeration problems related to the action of that group on a set of objects. It is a fundamental object in Pólya theory.
- CycleIndexPolynomial[perm,{x1,…,xk}] returns a monic monomial x1a1x2a2 … xkak for a permutation perm whose cyclic structure contains a1 1-cycles, a2 2-cycles, etc.
- CycleIndexPolynomial[group,{x1,…,xk}] returns a polynomial in which the coefficient of the monomial x1a1x2a2 … xkak gives the number of group elements whose cyclic structure contains a1 1-cycles, a2 2-cycles, etc., divided by the order of the group. It is the average of the cycle index monomials of its elements.
- For a permutation or group p, CycleIndexPolynomial[p,vars,n] denotes that p acts on a domain of n points, where n must be equal to or larger than PermutationMax[p].
- For a permutation or group p, CycleIndexPolynomial[p,vars] is equivalent to CycleIndexPolynomial[p,vars,PermutationMax[p]].
- Variables corresponding to cycle lengths not present in the elements of the group are ignored.
- If the elements of the group contain cycle lengths beyond the number of variables provided, then the result effectively uses a value 1 for those missing variables.
- The length of the cycles of a permutation or a permutation group is always bounded above by the length of their support, as given by PermutationLength. Hence, this is a safe estimate for the number of variables to include as the second argument of CycleIndexPolynomial.
Examples
open allclose allBasic Examples (2)
Scope (4)
Applications (1)
Cycle index polynomials are essential in Pólya's theory of counting. The classical example is counting how many necklaces can be formed with beads of different colors:
Suppose there is a necklace with 10 beads, invariant under cyclic rotations:
Suppose that there are beads of three colors, denoted by r, g, b:
For instance, there are 252 necklaces with three r beads, five g beads and two b beads:
This can be checked by actual construction of the necklaces:
If the necklace is considered to also be invariant under reflections along a diameter, then the symmetry group is dihedral:
Properties & Relations (4)
The identity permutation has degree zero and hence does not move any point:
If it acts on a set with four points, then the cycle index polynomial reflects the existence of four singletons:
Each point not moved contributes a multiplication by the first variable:
Missing variables are effectively replaced by 1:
The cycle index polynomial of a direct product of groups is the product of the cycle index polynomial of the groups:
Text
Wolfram Research (2012), CycleIndexPolynomial, Wolfram Language function, https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html.
CMS
Wolfram Language. 2012. "CycleIndexPolynomial." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html.
APA
Wolfram Language. (2012). CycleIndexPolynomial. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html