OrbitInventory

Pólya's enumeration theorem. The inventory of the colorings a group acts on, up to the group, from a cycle index $Z$ and the weights of the colors, each $x_i$ becoming the power sum $p_i = \sum_j w_j^i$. A single number $k$ for the weights gives the count of $k$-colorings.

✓ checked against that system · ! checked, with disagreements (hover a chip)CombinatoricaOrbitInventory

OrbitInventory(ci, {x1, x2, ...}, {w1, w2, ...})the cycle index ci, in the variables x_i, with each x_i replaced by $w_1^i + w_2^i + \cdots$, expanded. The coefficient of $w_1^{a_1} w_2^{a_2} \cdots$ counts the colorings using color $j$ exactly $a_j$ times, up to the group

OrbitInventory(ci, {x1, x2, ...}, k)the cycle index ci with every x_i replaced by k, the number of colorings with $k$ colors up to the group

Typed signatures

Type	Package	Applies
(number, list, list | number) -> number	groupalgebra	always

Domain: Permutations

Details

• Combinatorica's name and argument order, OrbitInventory[ci, x, w], with the one difference that the second argument is the list of variables the cycle index is written in (what CycleIndexPolynomial was given), since ours has no indexed variable $x[i]$
• With a list of weights the answer is the expanded polynomial; with one number $k$ it is the cycle index at $x_i = k$, which is the same as $k$ weights of $1$. Either way it is Pólya's theorem: the cycle index of the group, with $x_i \to \sum_j w_j^i$
• The variables must be distinct symbols and the weights a nonempty list or a number, else the call stays unevaluated. A weight may share a name with a variable: the substitution is simultaneous
• Defined in Epsil as a substitution into the cycle index (the variables renamed apart, then replaced by the power sums and expanded); there is no kernel
• Every example here was checked against Combinatorica's OrbitInventory[CycleIndex[group, x], x, w] and Sage's cycle_index() with the same substitution. The oracle lane takes no free symbols, so the records hold no scan rows
• The count of necklaces and bracelets is KNecklaces and KBracelets, whose own counts agree with this one: two colors give OEIS A000031 under $C_n$ and A000029 under $D_n$. A group with no named head, like the rotations of a cube, goes through PermutationGroup

Plot

argument p2 of type list has no control

Examples

Basic #

Square necklaces in red and blue: the coefficient of $r^a b^{4-a}$ counts those with $a$ red beads (the two with two red beads are the neighbors and the opposite pair)

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(4), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}\bigr\rbrack, \bigl\lbrack r, b\bigr\rbrack)$Out$b^4+{{r}}^4+{{r}}b^3+b{{r}}^3+2b^2{{r}}^2$

One number for the weights counts the colorings: 2-colored necklaces of 4 beads, the inventory above at $r = b = 1$

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(4), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}\bigr\rbrack, 2)$Out$6$

Scope #

Three colors on a triangle: the two orientations of a necklace using all three colors are the same up to rotation, hence the 2

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(3), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}\bigr\rbrack, \bigl\lbrack r, g, b\bigr\rbrack)$Out$b^3+g^3+{{r}}^3+gb^2+{{r}}b^2+bg^2+{{r}}g^2+b{{r}}^2+g{{r}}^2+2bg{{r}}$

Reflections merge some necklaces: with three red beads of six, $D_6$ has 3 bracelets where $C_6$ has 4

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{DihedralGroup}(6), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}\bigr\rbrack, \bigl\lbrack r, b\bigr\rbrack)$Out$b^6+{{r}}^6+{{r}}b^5+b{{r}}^5+3{{r}}^4b^2+3b^4{{r}}^2+3b^3{{r}}^3$

The weights may share names with the variables: $\tfrac12(p_1^2 + p_2)$ with $p_1 = x_1 + x_2$ and $p_2 = x_1^2 + x_2^2$

live ↗

In$\mathrm{OrbitInventory}(\frac{\mathrm{x1}^2+\mathrm{x2}}{2}, \bigl\lbrack\mathrm{x1}, \mathrm{x2}\bigr\rbrack, \bigl\lbrack\mathrm{x1}, \mathrm{x2}\bigr\rbrack)$Out$\mathrm{x1}^2+\mathrm{x2}^2+\mathrm{x1}\mathrm{x2}$

Applications #

Faces of a cube painted with two colors, up to its 24 rotations (a quarter turn about each of two axes generates them)

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{PermutationGroup}(\bigl\lbrack\mathrm{Cycles}(\bigl\lbrack\bigl\lbrack3, 6, 4, 5\bigr\rbrack\bigr\rbrack), \mathrm{Cycles}(\bigl\lbrack\bigl\lbrack1, 3, 2, 4\bigr\rbrack\bigr\rbrack)\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}\bigr\rbrack, 2)$Out$10$

The 10 colorings by number of red faces: one each for 0, 1, 5 and 6 red faces, two each for 2, 3 and 4

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{PermutationGroup}(\bigl\lbrack\mathrm{Cycles}(\bigl\lbrack\bigl\lbrack3, 6, 4, 5\bigr\rbrack\bigr\rbrack), \mathrm{Cycles}(\bigl\lbrack\bigl\lbrack1, 3, 2, 4\bigr\rbrack\bigr\rbrack)\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}\bigr\rbrack, \bigl\lbrack r, b\bigr\rbrack)$Out$b^6+{{r}}^6+{{r}}b^5+b{{r}}^5+2{{r}}^4b^2+2b^4{{r}}^2+2b^3{{r}}^3$

Pólya's count is the necklace count of KNecklaces

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(6), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}\bigr\rbrack, 3)=\mathrm{Count}(\mathrm{KNecklaces}(6, 3))$Out$\mathrm{True}$

With the reflections, the bracelet count of KBracelets

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{DihedralGroup}(7), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}, \mathrm{x7}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}, \mathrm{x7}\bigr\rbrack, 4)=\mathrm{Count}(\mathrm{KBracelets}(7, 4))$Out$\mathrm{True}$

Properties #

Binary necklaces of length 8, OEIS A000031

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(8), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}, \mathrm{x7}, \mathrm{x8}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}, \mathrm{x7}, \mathrm{x8}\bigr\rbrack, 2)$Out$36$

Binary bracelets of length 8, OEIS A000029

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{DihedralGroup}(8), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}, \mathrm{x7}, \mathrm{x8}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}, \mathrm{x6}, \mathrm{x7}, \mathrm{x8}\bigr\rbrack, 2)$Out$30$

Weights of 1 count colorings: three colors on a pentagon, the same as the number $3$ for the weights

live ↗

In$\mathrm{OrbitInventory}(\mathrm{CycleIndexPolynomial}(\mathrm{CyclicGroup}(5), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}\bigr\rbrack), \bigl\lbrack\mathrm{x1}, \mathrm{x2}, \mathrm{x3}, \mathrm{x4}, \mathrm{x5}\bigr\rbrack, \bigl\lbrack1, 1, 1\bigr\rbrack)$Out$51$

About

Examples	12
Checked against	Wolfram Language 10 agreeCombinatorica 8 agree2 unevaluatedSageMath 10 agree
Crosswalk	Combinatorica ×2SageMath

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

our cycle index is in the variables listed, Combinatorica's in x[i], so the template renames them first.

mappedsagepackages/oracle/src/mappings.ts

Sage has no OrbitInventory; its cycle_index() with each x_i replaced by the power sum of the weights (or the number of colors) is the definition.

mappedwolframpackages/oracle/src/mappings.ts

Wolfram has no OrbitInventory (it is Combinatorica's); this is Pólya's substitution of the power sums of the weights, or of the number of colors, into the cycle index. ReplaceAll with a rule list is simultaneous, as ours is.

See also: CycleIndexPolynomial, KNecklaces, KBracelets, PermutationGroup