DMAT_L15

The cycle index polynomial

Let $G⩽\text{Sym}(X)$ act on $X$, $|X|=n$. Recall that the number of $r$-colorings of $X$ fixed by $g\in G$ is given by $r^{c(g)}$, where $c(g)$ is the number of cycles in the cycle representation of $g$. Now, let $c_i(g)$ denote the number of cycles of length $i$ in the cycle representation of $g$. Note that ${\sum }_{i=1}^{n}i{c}_i(g)=n$.

Associate which each $g\in G$ the monomial $z(g;s_1,s_2,\dots ,s_n)\equiv s_1^{c_1(g)}{s}_2^{c_2(g)}\dots s_n^{c_n(g)}$ in indeterminates $s_1,\dots ,s_n$. The cycle index polynomial of $G$ is defined to be

$$Z(G;s_1,s_2,s_3,\dots ,s_n)\equiv \frac{1}{|G|}\sum _{g\in G}z(g;s_1,s_2,\dots ,s_n)=\frac{1}{|G|}\sum _{g\in G}{s}_1^{c_1(g)}{s}_2^{c_2(g)}\dots s_n^{c_n(g)}.$$

For the cube 2-coloring example from the previous lecture, the cycle index polynomial is

$$\frac{1}{24}(s_1^6+3s_1^2{s}_2^2+6s_1^2{s}_4+6s_2^3+8s_3^2).$$

If we wanted to count the number of non-equivalent $r$-colorings of the cube, that would be

$$\frac{1}{24}(r^6+3r^4+6r^3+6r^3+8r^2).$$

An example: Orbits of k-subsets and k-tuples

Let $G\le \text{Sym}(X)$, act on $X$, $|X|=n$. $G$ has an induced action on the set of all k-subsets of $X$. Let the number of orbits in this action be $f_k$. By convention, $f_0=1$. $f_1$ is the number of orbits in action of $G$ on $X$. We will show that the ordinary generating function for $f_k$ can be obtained from the cycle index polynomial.

Theorem 1(Proposition).

$$\sum _{k=0}^n{f}_k{t}^k=Z(G;1+t,1+t^2,\dots ,1+t^n).$$

Proof
From Burnside’s Lemma,

$$f_k=\frac{1}{|G|}\sum _{g\in G}{\text{fix}}_k(g).,$$

where ${\text{fix}}_k(g)$ is the number of elements in $\left(\genfrac{}{}{0ex}{}{X}{k}\right)$ that $g$ fixes. Let the generating function of $f_k$ be $f$.

$$\begin{array}{rl}f(t)& =\frac{1}{|G|}\sum _{k=0}^n\sum _{g\in G}{\text{fix}}_k(g)t^k\\ & =\frac{1}{|G|}\sum _{g\in G}\sum _{k=0}^n{\text{fix}}_k(g)t^k\end{array}$$

Note that $A\subseteq X$, $|A|=k$ is fixed by $g$ iff $A$ is a union of cycles of $g$. So, the generating function of ${\text{fix}}_k(g)$ is given by

$$\begin{array}{rl}\sum _{k=0}^n{\text{fix}}_k(g)t^k& =\prod _{i=1}^n\left(\sum _{a_i=0}^{c_i(g)}\left(\genfrac{}{}{0ex}{}{c_i(g)}{a_i}\right)t^{i{a}_i}\right)\\ & =\prod _{i=1}^n(1+t^i{)}^{c_i(g)}\\ & =z(g;1+t,1+t^2,\dots ,1+t^n)\end{array}$$

Thus, $f(t)=Z(G;1+t,1+t^2,\dots ,1+t^n)$.

$G$ also has an induced action on the set of all $k$-tuples of distinct elements of $X$, for each $1\le k\le n$. Let $F_k$ be the number of orbits of $G$ in this action. By convention, $F_0=1$. Note that $F_1=f_1$. The exponential generating function of $F_k$ can be calculated from the cycle index of $G$.

Theorem 2(Proposition).

$$\sum _{k=0}^n\frac{F_k}{k!}{t}^k=Z(G;1+t,1,\dots ,1).$$

Proof
A $k$-tuple is fixed iff all of its points are fixed. If we denote the number of $k$-tuples fixed by $g\in G$ by ${\text{Fix}}_k(G)$, we have

$${\text{Fix}}_k(g)=\left(\genfrac{}{}{0ex}{}{c_1(g)}{k}\right)k!.$$

Let $F(t)$ be the exponential generating function of $F_k$. Again, we have

$$\begin{array}{rl}F(t)& =\frac{1}{|G|}\sum _{k=0}^n\sum _{g\in G}{\text{Fix}}_k(g)\frac{t^k}{k!}\\ & =\frac{1}{|G|}\sum _{g\in G}\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{c_1(g)}{k}\right)t^k\\ & =\frac{1}{|G|}\sum _{g\in G}(1+t{)}^{c_1(g)}\\ & =Z(G;1+t,1,\dots ,1).\end{array}$$

---

Cycle index theorem

Generalizing the previous example, consider a collection $\Phi$ of figures ${\varphi }_1,{\varphi }_2,\dots$, each of which has a non-negative integral weight $w({\varphi }_i)$. The set of figures needn’t be finite, but there must be finitely many figures of a given weight. Let $a_n$ be the number of figures ${\varphi }_i$ of weight $n$. Let $a(t)\equiv {\sum }_{n\ge 0}{a}_n{t}^n$. This is called the figure generating series.

Let $G\le \text{Sym}(X)$, and let $G$ act on $X$. $X$ is finite, and $|X|=k$. We want to count the number of ways of associating a figure with each point of $X$, with two such configurations being considered as identical if they are in the same orbit (think of the figures as colors; we want to count the number of non-equivalent colorings). Consider functions $f:X\to \Phi$. Define the weight of $f$ by

$$w(f)\equiv \sum _{x\in X}w(f(x)).$$

For $\pi \in G$, define $f^{\pi }(x)\equiv f(x^{{\pi }^{-1}})$. Note that $\mathrm{Im}f=\mathrm{Im}{f}^{\pi }$. Thus, $w(f^{\pi })=w(f)$, so the action of $G$ does not change the weights of functions. Let $b_n$ be the number of orbits in the action of $G$ on functions of weight $n$. Define $b(t)\equiv {\sum }_{n\ge 0}{b}_n{t}^n$. This is called the function generating series.

Theorem 3(Cycle index theorem).

$$b(t)=Z(G;a(t),a(t^2),\dots ,a(t^k)).$$

Consider the previous example. We want the generating function for $f_k$. Let $\Phi =\{0,1\}$, $w(0)=0$, $w(1)=1$. $a(t)=1+t$. Now, a function $f:X\to \Phi$ is nothing but a characteristic function of a subset $Y$ of $X$. Also, note that $f^{\pi }$ is the characteristic function of $Y^{\pi }$ for any $\pi \in G$. So, counting the number of orbits in the action of $G$ on the collection of all $k$-subsets of $X$ is equivalent to counting the number of orbits in the action of $G$ on functions $f:X\to \Phi$ of weight $k$. So, $f_k=b_k$, and the result follows.

This also easily solves the cube 2-coloring problem from the previous lecture: If we let $X=\{F,B,L,R,U,D\}$, $\Phi =\{{\mathbf{c}}_1,{\mathbf{c}}_2\}$ and $w({\mathbf{c}}_1)=0$, $w({\mathbf{c}}_2)=1$, the functions $f:X\to \Phi$ are the colorings. Here, the weight of a coloring represents how many faces it colors with ${\mathbf{c}}_2$ (or ${\mathbf{c}}_1$). What we want is the total number of orbits $b_0+b_1+\cdots +b_6$, that is, $b(1)$.

$$\begin{array}{rl}b(t)& =Z(G;1+t,1+t^2,\dots ,1+t^6)\\ & \\ ⟹b(1)& =Z(G;2,\dots ,2)\\ & =\frac{1}{24}\sum _{g\in G}{2}^{c_1(g)+\cdots +c_6(g)},\end{array}$$

and the result follows.

Observe that since we are only interested in the total number of orbits in this case, we can set the weights to completely avoid the finer details: set $w({\mathbf{c}}_1)=w({\mathbf{c}}_2)=0$, which makes $a(t)=2$. So, $b(t)=Z(G;2,\dots ,2)$, a constant function. But, aside from mildly easing the computation, the weights are completely extraneous in this example. To illustrate this, let $w({\mathbf{c}}_1)={\alpha }_1$, $w({\mathbf{c}}_2)={\alpha }_2$ for any positive integers ${\alpha }_1$ and ${\alpha }_2$. The figure generating series becomes $a(t)=t^{{\alpha }_1}+t^{{\alpha }_2}$. $b(t)=Z(G;t^{{\alpha }_1}+t^{{\alpha }_2},\dots ,t^{6{\alpha }_1}+t^{6{\alpha }_2})$. However, $b(1)$ is still $Z(G;2,\dots ,2)$.

Proof

!

Let $\Phi ,{\Phi }^{\prime }$ be two sets of figures, with $a(t)$ and $a^{\prime }(t)$ being the respective figure generating series.

$\Phi \times {\Phi }^{\prime }=\{(\varphi ,{\varphi }^{\prime })|\varphi \in \Phi ,{\varphi }^{\prime }\in {\Phi }^{\prime }\}$
$w(\varphi ,{\varphi }^{\prime })$=$w(\varphi )+w({\varphi }^{\prime })$

figure generating series for the pairs $\Phi \times {\Phi }^{\prime }$ is $a(t)a^{\prime }(t)$.

!

All functions from $X\to \Phi$ as figures. What is the figure generating series? $a(t{)}^{|X|}$.

!

The figure generating series for functions fixed by an element $g\in G$: $a(t{)}^{c_1(g)}a(t^2{)}^{c_2(g)}\dots a(t^n{)}^{c_n(g)}$.