15 Poĺya Counting

Theorem 15.1

For each coloring \(\mathbf{c}\), the stabilizer \(G(\mathbf{c})\) of \(\mathbf{c}\) is a permutation group. Moreover, for any permutations \(f\) and \(g\) in \(G, g * \mathbf{c}=f * \mathbf{c}\) if and only if \(f^{-1} \circ g\) is in \(G(\mathbf{c})\).

Corollary 15.2

Let \(\mathbf{c}\) be a coloring in \(\mathcal{C}\). The number

\[ \mid \{ f * \mathbf{c}: f \text{ in } G\} \mid \]

of different colorings that are equivalent to \(\mathbf{c}\) equals the number

\[ \frac{|G|}{|G(\mathbf{c})|} \]

obtained by dividing the number of permutations in \(G\) by the number of permutations in the stabilizer of \(\mathbf{c}\).

Theorem 15.3

Let \(G\) be a group of permutations of \(X\) and let \(\mathcal{C}\) be a set of colorings of \(X\) such that \(f * \mathbf{c}\) is in \(\mathcal{C}\) for all \(f\) in \(G\) and all \(\mathbf{c}\) in \(\mathcal{C}\). Then the number \(N(G, \mathcal{C})\) of nonequivalent colorings in \(\mathcal{C}\) is given by

\begin{equation} \label{14.7} N(G, \mathcal{C})=\frac{1}{|G|} \sum _{f \in G}|\mathcal{C}(f)| \end{equation}

In words, the number of nonequivalent colorings in \(\mathcal{C}\) equals the average of the number of colorings fixed by the permutations in \(G\).

Theorem 15.4

Let \(f\) be a permutation of a set \(X\). Suppose we have \(k\) colors available with which to color the elements of \(X\). Let \(\mathcal{C}\) be the set of all colorings of \(X\). Then the number of colorings that are fixed by \(f\) satisfies

\[ |\mathcal{C}(f)|=k^{\# (f)} \]

Theorem 15.5

Let \(X\) be a set of \(n\) elements, and suppose we have a set of \(k\) colors available with which to color the elements of \(X\). Let \(\mathcal{C}\) be the set of all \(k^n\) colorings of \(X\). Let \(G\) be a group of permutations of \(X\). Then the number of nonequivalent colorings is the number

\[ N(G, \mathcal{C})=P_G(k, k, \ldots , k) \]

obtained by substituting \(z_i=k,(i=1,2, \ldots , n)\) into the cycle index of \(G\).

Theorem 15.6

Let \(X\) be a set of elements and let \(G\) be a group of permutations of \(X\). Let \(\left\{ u_1, u_2, \ldots , u_k\right\} \) be a set of \(k\) colors, and let \(\mathcal{C}\) be a set of all colorings of \(X\). Then the generating function for the number of nonequivalent colorings of \(\mathcal{C}\) according to the number of colors of each kind is the expression

\begin{equation} \label{14.20} P_G\left(u_1+\cdots +u_k, u_1^2+\cdots +u_k^2, \ldots , u_1^n+\cdots +u_k^n\right) \end{equation}

obtained from the cycle index \(P_G\left(z_1, z_2, \ldots , z_n\right)\) by making the substitutions

\[ z_j=u_1^j+\cdots +u_k^j \quad (j=1,2, \ldots , n) \]

In other words, the coefficient of

\[ u_1^{p_1} u_2^{p_2} \cdots u_k^{p_k} \]

in (14.20) equals the number of nonequivalent colorings in \(\mathcal{C}\) with \(p_1\) elements of \(X\) colored \(u_1, p_2\) elements colored \(u_2, \ldots , p_k\) elements colored \(u_k\).