CycleIndexPolynomial

The cycle index $Z(G) = \frac{1}{|G|}\sum_{g \in G} \prod_i x_i^{c_i(g)}$ of a permutation group, with $c_i(g)$ the number of $i$-cycles of $g$ and $x_i$ the $i$th variable. Evaluated at $x_i = k$ it counts the colorings with $k$ colors up to the group (Pólya).

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageCycleIndexPolynomial✓↗

CycleIndexPolynomial(group, {x1, x2, ...})the cycle index of group in the variables x1, x2, ..., x_i marking the cycles of length $i$

Typed signatures

Type	Package	Applies
(expression<AlternatingGroup> | expression<CyclicGroup> | expression<DihedralGroup> | expression<GroupDirectProduct> | expression<PermutationGroup> | expression<SymmetricGroup> | indexed_collection, list) -> number	groupalgebra	always

Domain: Permutations

Details

• The groups act as Wolfram's do: CyclicGroup and DihedralGroup on the $n$ vertices of an $n$-gon (rotations, and with the reflections), SymmetricGroup and AlternatingGroup on $n$ points, a PermutationGroup on the points it moves. $D_1$ swaps two points and $D_2$ is the Klein four-group on four points
• Those four are summed by closed formulas, not by listing their elements (the symmetric and alternating groups run over the partitions of $n$, up to $n = 35$); a PermutationGroup is listed
• The variable list must reach the group's degree, or the call stays unevaluated (Wolfram answers with a polynomial in the wrong variables); extra variables are ignored
• Pólya's count: setting every $x_i$ to $k$ gives the colorings with $k$ colors up to the group. For $C_n$ that is the necklace count of KNecklaces, for $D_n$ the bracelet count of KBracelets

Examples

Basic #

The rotations of a square: the identity, two quarter turns (one 4-cycle each) and a half turn (two 2-cycles)

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(4), \bigl\lbrack a, b, c, d\bigr\rbrack)$Out$\frac{a^4}{4}+\frac{b^2}{4}+\frac{d}{2}$

The identity, three transpositions and two 3-cycles

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{SymmetricGroup}(3), \bigl\lbrack a, b, c\bigr\rbrack)$Out$\frac{a^3}{6}+\frac{ab}{2}+\frac{c}{3}$

Scope #

The symmetries of a square, rotations and reflections

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{DihedralGroup}(4), \bigl\lbrack a, b, c, d\bigr\rbrack)$Out$\frac{a^4}{8}+\frac{ba^2}{4}+\frac{3b^2}{8}+\frac{d}{4}$

The even permutations of four points

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{AlternatingGroup}(4), \bigl\lbrack a, b, c, d\bigr\rbrack)$Out$\frac{a^4}{12}+\frac{b^2}{4}+\frac{2ac}{3}$

A group given by generators acts on the points it moves

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{PermutationGroup}(\bigl\lbrack\mathrm{Cycles}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack\bigr\rbrack)\bigr\rbrack), \bigl\lbrack a, b\bigr\rbrack)$Out$\frac{a^2}{2}+\frac{b}{2}$

$D_2$ is the Klein four-group on four points, not the symmetries of a 2-gon

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{DihedralGroup}(2), \bigl\lbrack a, b, c, d\bigr\rbrack)$Out$\frac{a^4}{4}+\frac{ba^2}{2}+\frac{b^2}{4}$

Applications #

Pólya's necklace count is the cycle index of $C_n$ at $x_i = k$

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(6), \bigl\lbrack3, 3, 3, 3, 3, 3\bigr\rbrack)=\mathrm{Count}(\mathrm{KNecklaces}(6, 3))$Out$\mathrm{True}$

Adding the reflections counts the bracelets: the cycle index of $D_n$ at $x_i = k$

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{DihedralGroup}(7), \bigl\lbrack4, 4, 4, 4, 4, 4, 4\bigr\rbrack)=\mathrm{Count}(\mathrm{KBracelets}(7, 4))$Out$\mathrm{True}$

Properties #

Every variable set to $3$ counts the 3-colored necklaces of 4 beads (Pólya)

live ↗

In$\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(4), \bigl\lbrack3, 3, 3, 3\bigr\rbrack)$Out$24$

About

Examples	9
Checked against	Wolfram Language 7 agreeCombinatorica 5 agree1 differ1 unevaluatedSageMath 7 agree
Crosswalk	Wolfram LanguageCombinatoricaSageMath

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

Combinatorica's groups are lists of permutations, which core CycleIndexPolynomial does not take; its CycleIndex is in x[i], renamed to the variable list here. Covered for the groups Combinatorica builds (a list of one-line permutations), not a PermutationGroup of Cycles, which its GroupElements rejects.

mappedsagepackages/oracle/src/mappings.ts

Sage's cycle_index() is in its power-sum basis, one p_i per i-cycle, renamed to the variable list here. Its group is on the points up to its degree, ours on the points it moves, so a variable list shorter than the degree is no answer there.

See also: GroupOrder, GroupElements, PermutationGroup, CyclicGroup, DihedralGroup, KNecklaces, KBracelets