# 6.3: Pólya-Redfield Counting

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

Suppose we are interested in a more detailed inventory of the colorings of an object, namely, instead of the total number of colorings we seek the number of colorings with a given number of each color.

Example \(\PageIndex{1}\)

How many distinct ways are there to color the vertices of a regular pentagon modulo \(D_5\) so that one vertex is red, two are blue, and two are green?

We can approach this as before, that is, the answer is

$${1\over|D_5|}\sum_{\sigma\in D_5}|\fix(\sigma)|,$$

where \(\fix(\sigma)\) now means the colorings with one red, two blues, and two greens that are fixed by \(\sigma\). No longer can we use the simple expression of corollary 6.2.8.

The identity permutation fixes all colorings, so we need to know how many colorings of the pentagon use one red, two blues, and two greens. This is an easy counting problem: the number is \({5\choose2}{3\choose2}=30\).

If \(\sigma\) is a non-trivial rotation, \(|\fix(\sigma)|=0\), since the only colorings fixed by a rotation have all vertices the same color.

If \(\sigma\) is a reflection, the single vertex fixed by \(\sigma\) must be red, and then the remaining 2-cycles are colored blue and green in one of two ways, so \(|\fix(\sigma)|=2\).

Thus, the number of distinct colorings is $${1\over10}(30+0+0+0+0+2+2+2+2+2)=4.$$

What we seek is a way to streamline this process, since in general the computations of \(|\fix(\sigma)|\) can be tedious. We begin by recasting the formula of corollary 6.2.8.

Definition: type of a permutation

The *type of a permutation* \(\sigma\in S_n\) is \(\tau(\sigma)=(\tau_1(\sigma),\tau_2(\sigma),\ldots,\tau_n(\sigma))\), where \(\tau_i(\sigma)\) is the number of \(i\)-cycles in the cycle form of \(\sigma\).

Note that \(\sum_{i=1}^n \tau_i(\sigma)=\#\sigma\). Now instead of the simple

$${1\over|G|}\sum_{\sigma\in G} k^{\#\sigma}$$

let us write

$${1\over|G|}\sum_{\sigma\in G} x_1^{\tau_1(\sigma)}x_2^{\tau_2(\sigma)} \cdots x_n^{\tau_n(\sigma)}.$$

If we substitute \(x_i=k\) for every \(i\), we get the original form of the sum, but the new version carries more information about each \(\sigma\).

Suppose we want to know the number of colorings fixed by some \(\sigma\) that use \(i\) reds and \(j\) blues, where of course \(i+j=n\). Using ideas familiar from generating functions, consider the following expression:

$$(r+b)^{\tau_1(\sigma)}(r^2+b^2)^{\tau_2(\sigma)} \cdots (r^n+b^n)^{\tau_n(\sigma)}.$$

If we multiply out, we get a sum of terms of the form \(r^pb^q\), each representing some particular way of coloring the vertices of cycles red and blue so that the total number of red vertices is \(p\) and the number of blue vertices is \(q\), and moreover this coloring will be fixed by \(\sigma\). When we collect like terms, the coefficient of \(r^ib^j\) is the number of colorings fixed by \(\sigma\) that use \(i\) reds and \(j\) blues. This means that the coefficient of \(r^ib^j\) in

$$\sum_{\sigma\in G} (r+b)^{\tau_1(\sigma)}(r^2+b^2)^{\tau_2(\sigma)} \cdots (r^n+b^n)^{\tau_n(\sigma)}$$

is

$$\sum_{\sigma\in G} |\fix(\sigma)|$$

where \(\fix(\sigma)\) is the set of colorings using \(i\) reds and \(j\) blues that are fixed by \(\sigma\). Finally, then, the number of distinct colorings using \(i\) reds and \(j\) blues is this coefficient divided by \(|G|\). This means that by multiplying out

$${1\over |G|}\sum_{\sigma\in G}(r+b)^{\tau_1(\sigma)}(r^2+b^2)^{\tau_2(\sigma)} \cdots (r^n+b^n)^{\tau_n(\sigma)}$$

and collecting like terms, we get a list of the number of distinct colorings using any combination of reds and blues, each the coefficient of a different term; we call this the **inventory** of colorings. If we substitute \(r=1\) and \(b=1\), we get the sum of the coefficients, namely, the total number of distinct colorings with two colors.

Definition: cycle index

The *cycle index *of \(G\) is $$P_G={1\over |G|}\sum_{\sigma\in G}\prod_{i=1}^n x_i^{\tau_i(\sigma)}.$$

Example \(\PageIndex{2}\)

Consider again example 6.2.6, in which we found the number of colorings of a square with two colors. The cycle index of \(D_4\) is $${1\over8}( x_1^4+x_4^1+x_2^2+x_4^1+x_2^2+x_2^2+x_1^2x_2+x_1^2x_2 ) ={1\over8}x_1^4 + {1\over4}x_1^2x_2 + {3\over8}x_2^2 + {1\over4}x_4.$$ Substituting as above gives $${1\over8}(r+b)^4 + {1\over4}(r+b)^2(r^2+b^2) + {3\over8}(r^2+b^2)^2 + {1\over4}(r^4+b^4) =r^4 + r^3b + 2r^2b^2 + rb^3 + b^4.$$ Thus there is one all red coloring, one with three reds and one blue, and so on, as shown in figure 6.2.4.

There is nothing special about the use of two colors. If we want to use three colors, we substitute \(r^i+b^i+g^i\) for \(x_i\) in the cycle index, and for \(k\) colors we substitute something like \(c_1^i+c_2^i+c_3^i+\cdots+c_k^i\).

Example \(\PageIndex{3}\)

Let's do the number of 3-colorings of the square. Since we already have the cycle index, we need only substitute \(x_i=r^i+b^i+g^i\) and expand. We get $$\eqalign{ {1\over8}(r+b+g)^4 &+ {1\over4}(r+b+g)^2(r^2+b^2+g^2) + {3\over8}(r^2+b^2+g^2)^2 + {1\over4}(r^4+b^4+g^4)\cr ={}&b^4 + b^3g + b^3r + 2b^2g^2 + 2b^2gr + 2b^2r^2 + bg^3 + 2bg^2r + 2bgr^2 +\cr &br^3 + g^4 + g^3r + 2g^2r^2 + gr^3 + r^4.\cr }$$ So, for example, there are two squares with two blue vertices, one green, and one red, from the \(b^2gr\) term.

Example \(\PageIndex{4}\)

Consider again example 6.2.7, in which we counted the number of four-vertex graphs. Following that example, we get $$P_G={1\over 24}(x_1^6+6x_2x_4+8x_3^2+3x_1^2x_2^2+6x_1^2x_2^2),$$ and substituting for the variables \(x_i\) gives

$$r^6 + r^5b + 2r^4b^2 + 3r^3b^3 + 2r^2b^4 + rb^5 + b^6.$$

Recall that the "colors'' of the edges in this example are "included'' and "excluded''. If we set \(b=1\) and \(r=i\) (for "included'') we get

$$i^6 + i^5 + 2i^4 + 3i^3 + 2i^2 + i + 1,$$

interpreted as one graph with 6 edges, one with 5, two with 4, three with 3, two with 2, one with 1, and one with zero edges, since \(1=i^0\).

It is possible, though a bit difficult, to see that for \(n\) vertices the cycle index is

$$ P_G=\sum_{\bf j}\prod_{k=1}^n{1\over k^{j_k} j_k!} \prod_{k=1}^{\lfloor n/2\rfloor}(x_{k} x_{2k}^{k-1})^{j_{2k}} \!\!\prod_{k=1}^{\lfloor (n-1)/2\rfloor}\!\!x_{2k+1}^{kj_{2k+1}} \prod_{k=1}^{\lfloor n/2\rfloor} x_k^{kC(j_k,2)} \!\!\!\!\prod_{1\le r< s\le n-1}\!\!\!\!\!\!\!\! x_{\lcm(r,s)}^{\gcd(r,s)j_rj_s}, $$

where the sums are over all partitions \({\bf j}=(j_1,j_2,\ldots,j_n)\) of \(n\), that is, over all \(\bf j\) such that \(j_1+2j_2+3j_3+\cdots+nj_n=n\), and \(C(m,2)={m\choose2}\). This is where the formula 6.2.1 comes from, substituting \(x_i=2\) for all \(i\).

With this formula and a computer it is easy to compute the inventory of \(n\)-vertex graphs when \(n\) is not too large. When \(n=5\), the inventory is

$$ i^{10} + i^9 + 2i^8 + 4i^7 + 6i^6 + 6i^5 + 6i^4 + 4i^3 + 2i^2 + i+1. $$