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 all

Basic Examples  (2)

Cycle index monomial of a permutation:

Cycle index polynomial for the alternating group on five points:

Scope  (4)

Cycle index monomial of permutations:

Specify the size of the domain of action:

Cycle index polynomial of permutation groups:

Specify the size of the domain of action:

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:

Now the counts are different:

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:

Wolfram Research (2012), CycleIndexPolynomial, Wolfram Language function, https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html.

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

BibTeX

@misc{reference.wolfram_2023_cycleindexpolynomial, author="Wolfram Research", title="{CycleIndexPolynomial}", year="2012", howpublished="\url{https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html}", note=[Accessed: 19-March-2024 ]}

BibLaTeX

@online{reference.wolfram_2023_cycleindexpolynomial, organization={Wolfram Research}, title={CycleIndexPolynomial}, year={2012}, url={https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html}, note=[Accessed: 19-March-2024 ]}