CycleIndexPolynomial
constructs the cycle index monomial of the permutation perm in the variables xi.
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)Summary of the most common use cases
Scope (4)Survey of the scope of standard use cases
Cycle index monomial of permutations:
https://wolfram.com/xid/0jz8ojdxrq7a0y-3sn98a
https://wolfram.com/xid/0jz8ojdxrq7a0y-3234t8
Specify the size of the domain of action:
https://wolfram.com/xid/0jz8ojdxrq7a0y-o9vsk
https://wolfram.com/xid/0jz8ojdxrq7a0y-cf1ayg
Cycle index polynomial of permutation groups:
https://wolfram.com/xid/0jz8ojdxrq7a0y-hptgx1
https://wolfram.com/xid/0jz8ojdxrq7a0y-f716l0
Specify the size of the domain of action:
https://wolfram.com/xid/0jz8ojdxrq7a0y-ngbkab
https://wolfram.com/xid/0jz8ojdxrq7a0y-m24enu
Applications (1)Sample problems that can be solved with this function
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:
https://wolfram.com/xid/0jz8ojdxrq7a0y-5wsjfl
Suppose that there are beads of three colors, denoted by r, g, b:
https://wolfram.com/xid/0jz8ojdxrq7a0y-2o0n3b
For instance, there are 252 necklaces with three r beads, five g beads and two b beads:
https://wolfram.com/xid/0jz8ojdxrq7a0y-2z1kpx
This can be checked by actual construction of the necklaces:
https://wolfram.com/xid/0jz8ojdxrq7a0y-hu2095
If the necklace is considered to also be invariant under reflections along a diameter, then the symmetry group is dihedral:
https://wolfram.com/xid/0jz8ojdxrq7a0y-dh18h3
https://wolfram.com/xid/0jz8ojdxrq7a0y-d8sgu6
https://wolfram.com/xid/0jz8ojdxrq7a0y-htwuqd
Properties & Relations (4)Properties of the function, and connections to other functions
The identity permutation has degree zero and hence does not move any point:
https://wolfram.com/xid/0jz8ojdxrq7a0y-5midt5
If it acts on a set with four points, then the cycle index polynomial reflects the existence of four singletons:
https://wolfram.com/xid/0jz8ojdxrq7a0y-bsow25
Each point not moved contributes a multiplication by the first variable:
https://wolfram.com/xid/0jz8ojdxrq7a0y-hrwx94
https://wolfram.com/xid/0jz8ojdxrq7a0y-byvk3b
https://wolfram.com/xid/0jz8ojdxrq7a0y-16prvz
Missing variables are effectively replaced by 1:
https://wolfram.com/xid/0jz8ojdxrq7a0y-uwnhb3
https://wolfram.com/xid/0jz8ojdxrq7a0y-j06ehp
https://wolfram.com/xid/0jz8ojdxrq7a0y-ysylh
https://wolfram.com/xid/0jz8ojdxrq7a0y-gszbe6
The cycle index polynomial of a direct product of groups is the product of the cycle index polynomial of the groups:
https://wolfram.com/xid/0jz8ojdxrq7a0y-zqfw4m
https://wolfram.com/xid/0jz8ojdxrq7a0y-8qcxec
https://wolfram.com/xid/0jz8ojdxrq7a0y-v5awsw
https://wolfram.com/xid/0jz8ojdxrq7a0y-0ea5ko
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.
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.
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
Wolfram Language. (2012). CycleIndexPolynomial. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html
BibTeX
@misc{reference.wolfram_2024_cycleindexpolynomial, author="Wolfram Research", title="{CycleIndexPolynomial}", year="2012", howpublished="\url{https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html}", note=[Accessed: 11-January-2025
]}
BibLaTeX
@online{reference.wolfram_2024_cycleindexpolynomial, organization={Wolfram Research}, title={CycleIndexPolynomial}, year={2012}, url={https://reference.wolfram.com/language/ref/CycleIndexPolynomial.html}, note=[Accessed: 11-January-2025
]}