Cycle index

We will identify the complete graph K₃ with an equilateral triangle in the Euclidean plane. This permits us to use geometric language to describe the permutations involved as symmetries of the equilateral triangle. Every permutation in the group S₃ of vertex permutations (S₃ in its natural action, given above) induces an edge permutation. These are the permutations:

• The identity: No vertices are permuted, and no edges; the contribution is ${\displaystyle a_{1}^{3}.}$
• Three reflections in an axis passing through a vertex and the midpoint of the opposite edge: These fix one edge (the one not incident on the vertex) and exchange the remaining two; the contribution is ${\displaystyle 3a_{1}a_{2}.}$
• Two rotations, one clockwise, the other counterclockwise: These create a cycle of three edges; the contribution is ${\displaystyle 2a_{3}.}$

The cycle index of the group G of edge permutations induced by vertex permutations from S₃ is

${\displaystyle Z(G)={\frac {1}{6}}\left(a_{1}^{3}+3a_{1}a_{2}+2a_{3}\right).}$

It happens that the complete graph K₃ is isomorphic to its own line graph (vertex-edge dual) and hence the edge permutation group induced by the vertex permutation group is the same as the vertex permutation group, namely S₃ and the cycle index is Z(S₃). This is not the case for complete graphs on more than three vertices, since these have strictly more edges (${\displaystyle {\binom {n}{2}}}$) than vertices (n).

This is entirely analogous to the three-vertex case. These are the vertex permutations (S₄ in its natural action) and the edge permutations (S₄ acting on unordered pairs) that they induce:

• The identity: This permutation maps all vertices (and hence, edges) to themselves and the contribution is ${\displaystyle a_{1}^{6}.}$
• Six permutations that exchange two vertices: These permutations preserve the edge that connects the two vertices as well as the edge that connects the two vertices not exchanged. The remaining edges form two two-cycles and the contribution is ${\displaystyle 6a_{1}^{2}a_{2}^{2}.}$
• Eight permutations that fix one vertex and produce a three-cycle for the three vertices not fixed: These permutations create two three-cycles of edges, one containing those not incident on the vertex, and another one containing those incident on the vertex; the contribution is ${\displaystyle 8a_{3}^{2}.}$
• Three permutations that exchange two vertex pairs at the same time: These permutations preserve the two edges that connect the two pairs. The remaining edges form two two-cycles and the contribution is ${\displaystyle 3a_{1}^{2}a_{2}^{2}.}$
• Six permutations that cycle the vertices in a four-cycle: These permutations create a four-cycle of edges (those that lie on the cycle) and exchange the remaining two edges; the contribution is ${\displaystyle 6a_{2}a_{4}.}$

We may visualize the types of permutations geometrically as symmetries of a regular tetrahedron. This yields the following description of the permutation types.

• The identity.
• Reflection in the plane that contains one edge and the midpoint of the edge opposing it.
• Rotation by 120 degrees about the axis passing through a vertex and the midpoint of the opposite face.
• Rotation by 180 degrees about the axis connecting the midpoints of two opposite edges.
• Six rotoreflections by 90 degrees.

The cycle index of the edge permutation group G of K₄ is:

${\displaystyle Z(G)={\frac {1}{24}}\left(a_{1}^{6}+9a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}a_{4}\right).}$

Cube with colored faces

Consider an ordinary cube in three-space and its group of symmetries (automorphisms), call it C. It permutes the six faces of the cube. (We could also consider edge permutations or vertex permutations.) There are twenty-four automorphisms.

• The identity:

There is one such permutation and its contribution is ${\displaystyle a_{1}^{6}.}$

• Six 90-degree face rotations:

We rotate about the axis passing through the centers of the face and the face opposing it. This will fix the face and the face opposing it and create a four-cycle of the faces parallel to the axis of rotation. The contribution is ${\displaystyle 6a_{1}^{2}a_{4}.}$

• Three 180-degree face rotations:

We rotate about the same axis as in the previous case, but now there is no four cycle of the faces parallel to the axis, but rather two two-cycles. The contribution is ${\displaystyle 3a_{1}^{2}a_{2}^{2}.}$

• Eight 120-degree vertex rotations:

This time we rotate about the axis passing through two opposite vertices (the endpoints of a main diagonal). This creates two three-cycles of faces (the faces incident on the same vertex form a cycle). The contribution is ${\displaystyle 8a_{3}^{2}.}$

• Six 180-degree edge rotations:

These edge rotations rotate about the axis that passes through the midpoints of opposite edges not incident on the same face and parallel to each other and exchanges the two faces that are incident on the first edge, the two faces incident on the second edge, and the two faces that share two vertices but no edge with the two edges, i.e. there are three two-cycles and the contribution is ${\displaystyle 6a_{2}^{3}.}$

The conclusion is that the cycle index of the group C is

${\displaystyle Z(C)={\frac {1}{24}}\left(a_{1}^{6}+6a_{1}^{2}a_{4}+3a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}^{3}\right).}$

This group contains one permutation that fixes every element (this must be a natural action).

${\displaystyle Z(E_{n})=a_{1}^{n}.}$

A cyclic group, C_n is the group of rotations of a regular n-gon, that is, n elements equally spaced around a circle. This group has φ(d) elements of order d for each divisor d of n, where φ(d) is the Euler φ-function, giving the number of natural numbers less than d which are relatively prime to d. In the regular representation of C_n, a permutation of order d has n/d cycles of length d, thus:[12]

${\displaystyle Z(C_{n})={\frac {1}{n}}\sum _{d|n}\varphi (d)a_{d}^{n/d}.}$

The dihedral group is like the cyclic group, but also includes reflections. In its natural action,

${\displaystyle Z(D_{n})={\frac {1}{2}}Z(C_{n})+{\begin{cases}{\frac {1}{2}}a_{1}a_{2}^{(n-1)/2},&n{\mbox{ odd, }}\\{\frac {1}{4}}\left(a_{1}^{2}a_{2}^{(n-2)/2}+a_{2}^{n/2}\right),&n{\mbox{ even.}}\end{cases}}}$

The cycle index of the alternating group in its natural action as a permutation group is

${\displaystyle Z(A_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}{\frac {1+(-1)^{j_{2}+j_{4}+\cdots }}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k=1}^{n}a_{k}^{j_{k}}.}$

The numerator is 2 for the even permutations, and 0 for the odd permutations. The 2 is needed because ${\displaystyle {\frac {1}{|A_{n}|}}={\frac {2}{n!}}}$.

The cycle index of the symmetric group S_n in its natural action is given by the formula:

${\displaystyle Z(S_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}{\frac {1}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k=1}^{n}a_{k}^{j_{k}}}$

that can be also stated in terms of complete Bell polynomials:

${\displaystyle Z(S_{n})={\frac {B_{n}(0!\,a_{1},1!\,a_{2},\dots ,(n-1)!\,a_{n})}{n!}}.}$

This formula is obtained by counting how many times a given permutation shape can occur. There are three steps: first partition the set of n labels into subsets, where there are ${\displaystyle j_{k}}$ subsets of size k. Every such subset generates ${\displaystyle k!/k}$ cycles of length k. But we do not distinguish between cycles of the same size, i.e. they are permuted by ${\displaystyle S_{j_{k}}}$. This yields

${\displaystyle {\frac {n!}{\prod _{k=1}^{n}(k!)^{j_{k}}}}\prod _{k=1}^{n}\left({\frac {k!}{k}}\right)^{j_{k}}\prod _{k=1}^{n}{\frac {1}{j_{k}!}}={\frac {n!}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}.}$

The formula may be further simplified if we sum up cycle indices over every ${\displaystyle n}$, while using an extra variable ${\displaystyle y}$ to keep track of the total size of the cycles:

${\displaystyle \sum \limits _{n\geq 1}y^{n}Z(S_{n})=\sum \limits _{n\geq 1}\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}\prod _{k=1}^{n}{\frac {a_{k}^{j_{k}}y^{kj_{k}}}{k^{j_{k}}j_{k}!}}=\prod \limits _{k\geq 1}\sum \limits _{j_{k}\geq 0}{\frac {(a_{k}y^{k})^{j_{k}}}{k^{j_{k}}j_{k}!}}=\prod \limits _{k\geq 1}\exp \left({\frac {a_{k}y^{k}}{k}}\right),}$

thus giving a simplified form for the cycle index of ${\displaystyle S_{n}}$:

${\displaystyle {\begin{aligned}Z(S_{n})&=[y^{n}]\prod \limits _{k\geq 1}\exp \left({\frac {a_{k}y^{k}}{k}}\right)\\&=[y^{n}]\exp \left(\sum \limits _{k\geq 1}{\frac {a_{k}y^{k}}{k}}\right).\end{aligned}}}$

There is a useful recursive formula for the cycle index of the symmetric group. Set ${\displaystyle Z(S_{0})=1}$ and consider the size l of the cycle that contains n, where ${\displaystyle {\begin{matrix}1\leq l\leq n.\end{matrix}}}$ There are ${\displaystyle {\begin{matrix}{n-1 \choose l-1}\end{matrix}}}$ ways to choose the remaining ${\displaystyle l-1}$ elements of the cycle and every such choice generates ${\displaystyle {\begin{matrix}{\frac {l!}{l}}=(l-1)!\end{matrix}}}$ different cycles.

This yields the recurrence

${\displaystyle Z(S_{n})={\frac {1}{n!}}\sum _{g\in S_{n}}\prod _{k=1}^{n}a_{k}^{j_{k}(g)}={\frac {1}{n!}}\sum _{l=1}^{n}{n-1 \choose l-1}\;(l-1)!\;a_{l}\;(n-l)!\;Z(S_{n-l})}$

or

${\displaystyle Z(S_{n})={\frac {1}{n}}\sum _{l=1}^{n}a_{l}\;Z(S_{n-l}).}$