• If $\sigma \in S_n$ let $cyc(\sigma)$ be the integer partition of $n$ giving cycle lengths.
• For example, if $\sigma = (1 2)(3)(4 5 6)(7 8)$, then $cyc(\sigma) = 3 + 2 + 2 + 1 \sim (3, 2, 2, 1)$.
• Recall that an integer partition $\lambda$ of $n$ is a tuple $\lambda[:]$ such that $\sum_i \lambda[i] = n$and $\lambda$ is non-increasing.
• The cycle index polynomial for a group $G \subseteq S_n$ is $Z(G) \equiv 1/|G| \sum_{g \in G} P[cyc(g)]$where $P[\cdot]$ is the power sum symmetric polynomial for the cycle-type partition $cyc(g)$.
• Recall the definition of power sum symmetric polynomial. First, for a natural number $k \in \mathbb N$, we define $P[k](\vec x) \equiv x_1^k + x_2^k + \dots + x_n^k$.
• Next, for a partition $\lambda$, we define $P[\lambda](\vec x)$ to be the product over the parts of the partition: $P[\lambda_1](\vec x) \cdot P[\lambda_2](\vec x) \cdot \dots \cdot P[\lambda_l](\vec x)$.

§ Cycle index polynomial of dihedral group

• For example, consider the dihedral group $D_4$ acting on a square with vertices $a, b, c, d$:
• More formally, the dihedral group $D_4$ acts on the set of labelled squares $X$.

a bd c

• 1. For the identity $e$, the cycle is $(a)(b)(c)(d)$. The cycle partition is $(1, 1, 1, 1)$.
• 2. For the rotation $r$, the cycle is $(a b c d)$. The cycle partition is $(4)$.
• 3. For the rotation $r^2$, the cycle is $(a c)(b d)$. The cycle partition is $(2, 2)$.
• 4. For the rotation $r^3$, the cycle is $(a c b d)$. The partition is $(4)$.
• 5. For the horizontal swap $h$, the cycle is $(a d)(b c)$. The cycle partition is $(2, 2)$.
• 6. For the vertical swap $v$, the cycle is $(a b)(c d)$. The cycle partition is $(2, 2)$.
• 7. For the diagonal a-c swap $ac$, the cycle is $(b d)(a)(c)$. The cycle partition is $(2, 1, 1)$.
• 8. For the diagonal b-d swap $bd$, the cycle is $(a b)(c)(d)$. The cycle partitionis $(2, 1, 1)$.

• The cycle index polynomial is $Z(D_4, X) \equiv 1/|D_4|(P[(1, 1, 1, 1)] + 2P[2, 1, 1] + 3P[2, 2] + P[4])$.

• $P[1, 1, 1, 1] = p_1^4 = (x_1 + x_2 + x_3 + \dots + x_n)^4$, where $p_1$ is a power sum symmetric polynomial .
• $P[2, 1, 1] = p_2 p_1 p_1 = (x_1^2 + x_2^2 + \dots+ x_n^2)\cdot (x_1^1 + x_2^1 + \dots + x+n)^2$.
• ...and so on.