1 Sets 2 Functions 3 Introduction to counting 4 Counting with bijections 5 Generating functions 6 Theory of generating functions (Milan Novaković) 7 Burnside's lemma 8 Polya's theorem

# Polya's Theorem

We will now consider a class of problems that can not be solved with an immediate application of Burnside’s lemma. Let us take a look at the following example.

Example 1. Each face of a cube is painted in one of the following five colors: red, green, blue, yellow, or white. Determine the number of cubes that can be generated this way, if the color red has to be used exactly two times. Cubes are considered distinct if they cannot be obtained from each other using rotations.

## Pattern inventory

In order to solve Example 1, we need to take a step back, and gain a deeper insight into the mechanics of Burnside’s lemma. We start by considering the following easy problem in which we are able to list all possible configurations.

Example 2.

Find the number of distinct squares that can be obtained by painting each edge of a given square in either red or green. Squares are considered distinct if they cannot be obtained from each other using rotations or reflections.

We will solve this problem by listing down all possible paintings: $(R, R, R, R), \;\;\; (G, G, G, G),\;\;\; (R, G, G, G),\;\;\; (G, R, R, R),\;\;\; (R, R, G, G),\;\;\; (R, G, R, G). \;\;\;\;\;\;\;\quad\quad\quad(1)$ Assume that $$R$$ and $$G$$ are variables instead of colors. From the listing above we can make the following polynomial: $R\cdot R\cdot R\cdot R+G\cdot G\cdot G\cdot G+ R\cdot G\cdot G\cdot G+ G\cdot R\cdot R\cdot R+R\cdot R\cdot G\cdot G+R\cdot G\cdot R\cdot G.$ We’ll do something that looks naive on the first sight - we will try to simplify the previous polynomial. We obtain: $P(R, G)=R^4+G^4+R\cdot G^3+G\cdot R^3+2R^2G^2.$ The polynomial above is called the pattern inventory for the coloring of the square in 2 colors. The pattern inventory is less informative than the listing in formula (1). Having a polynomial, however, provides us with certain benefits. For example, P(1,1)=6. This means that a particular value of this polynomial tells us exactly the number of equivalence classes.

Polya’s theorem provides an algebraic way to obtain the pattern inventory, and using it we can answer the question posed in Example 1.

We are ready for the formal definition:

Definition

Let $$S\subseteq C^l$$ be a set of colorings, where $$C=\{C_1,C_2,\dots, C_k\}$$ is a set of colors. Let $$T\subseteq S$$ be the subset of all colorings using the colors from the set $$C$$. The pattern inventory of the set $$T$$ is defined as: $P_T(C_1,\dots, C_k)=\sum_{(s_1,\dots,s_l)\in T} s_1\cdot s_2\cdots s_l.$

Notice that the expression on the right-hand side is a polynomial in $$C_1$$, ..., $$C_k$$ because each of the variables $$s_1$$, ..., $$s_l$$ belongs to $$C$$.

## Cycle polynomial

Let us consider the set of permutations corresponding to rotations and reflections of the square: $$G=\{e, \rho_1,\dots, \rho_7\}$$ where

$e=(1)(2)(3)(4),\; \rho_1=(1234),\; \rho_2=(13)(24),\; \rho_3=(1432),$ $\rho_4=(12)(34),\;\; \rho_5=(14)(23),\;\; \rho_6=(1)(24)(3),\;\; \rho_7=(13)(2)(4).$

All that we need to know about these permutations $$e$$, $$\rho_1$$, ..., $$\rho_7$$ is the following:

$$e$$ has 4 cycles of length 1;
$$\rho_1$$ has 1 cycle of length 4;
$$\rho_2$$ has 2 cycles of length 2;
$$\rho_3$$ has 1 cycle of length 4;
$$\rho_4$$ has 2 cycles of length 2;
$$\rho_5$$ has 2 cycles of length 2;
$$\rho_6$$ has 2 cycles of length 1, and 1 cycle of length 2;
$$\rho_7$$ has 2 cycles of length 1, and 1 cycle of length 2;

We will encode the previous sentences using monomials $$\tau_e$$, $$\tau_{\rho_1}$$, ..., $$\tau_{\rho_7}$$ in variables $$X_1$$, $$X_2$$, ..., $$X_n$$. The definition will follow shortly, but this new notation is easier to understand from an example:

$$\tau_e(X_1, X_2, X_3,X_4)=X_1^4$$;
$$\tau_{\rho_1}(X_1,X_2,X_3,X_4)=X_4$$;
$$\tau_{\rho_2}(X_1,X_2,X_3,X_4)=X_2^2$$;
$$\tau_{\rho_3}(X_1,X_2,X_3,X_4)=X_4$$;
$$\tau_{\rho_4}(X_1,X_2,X_3,X_4)=X_2^2$$;
$$\tau_{\rho_5}(X_1,X_2,X_3,X_4)=X_2^2$$;
$$\tau_{\rho_6}(X_1,X_2,X_3,X_4)=X_1^2X_2$$;
$$\tau_{\rho_7}(X_1,X_2,X_3,X_4)=X_1^2X_2$$;

Definition

Let G be a group of permutations on the set of $$n$$ elements. For each permutation $$\sigma\in G$$ consider the sequence $$b_1$$, $$b_2$$, $$b_3$$, ..., $$b_n$$ where $$b_i$$ is the number of cycles of length $$i$$. We define the cycle monomial as $\tau_{\sigma}(X_1,X_2,\dots, X_n)=X_1^{b_1}\cdot X_2^{b_2}\cdots X_n^{b_n}.$

Definition

Let $$G$$ be a group of permutations on the set of $$n$$ elements. We define the cycle polynomial of the group $$G$$ as $P_G(X_1,X_2,\dots, X_n)=\sum_{\sigma\in G} \tau_{\sigma}(X_1,X_2,\dots, X_n).$

## Polya's theorem

Theorem 3.

Assume that $$C=\{C_1, \dots, C_k\}$$ is the set of colors and $$S=C^n$$ the set of all colorings. Assume that $$G$$ is a group whose elements are permutations of $$\{1, 2, \dots, n\}$$. Let $$\sim$$ be the equivalence relation generated by $$G$$ on $$S$$. Then the pattern inventory corresponding to the set $$E$$ of representatives of the equivalence classes of $$S$$ satisfies: $P(C_1,\dots, C_k)=\frac1{|G|}P_G\left((C_1+\cdots+C_k),\left(C_1^2+\cdots+C_k^2\right), \left(C_1^3+\cdots+C_k^3\right),\cdots, \left(C_1^n+\cdots+C_k^n\right)\right).$

## Solution to Example 1

Let us consider the group $$G=\{e, \rho_1, \dots, \rho_{23}\}$$ of rotations of the cube. The cycle notation for each of the permutations is given below:

$$e$$=(1)(2)(3)(4)(5)(6), $$\rho_1$$=(1234)(5)(6), $$\rho_2$$=(13)(24)(5)(6), $$\rho_3$$=(1432)(5)(6), $$\rho_4$$=(1635)(2)(4), $$\rho_5$$=(13)(2)(4)(56), _br_ $$\rho_6$$=(1536)(2)(4), $$\rho_7$$=(1)(2645)(3), $$\rho_8$$=(1)(24)(3)(56), $$\rho_9$$=(1)(2546)(3), $$\rho_{10}$$=(154)(236), $$\rho_{11}$$=(145)(263), _br_ $$\rho_{12}$$=(125)(346), $$\rho_{13}$$=(152)(364), $$\rho_{14}$$=(164)(235), $$\rho_{15}$$=(146)(253), $$\rho_{16}$$=(126)(345), $$\rho_{17}$$=(162)(354), _br_ $$\rho_{18}$$=(15)(24)(36), $$\rho_{19}$$=(13)(25)(46), $$\rho_{20}$$=(16)(24)(35), $$\rho_{21}$$=(13)(26)(45), $$\rho_{22}$$=(14)(23)(56), $$\rho_{23}$$=(12)(34)(56).

From this list we will form the cycle polynomial. We will need only monomials $$X_1$$, $$X_2$$, $$X_3$$, $$X_4$$ because the longest cycles we have are of order 4. If we keep the terms $$X_5$$, $$X_6$$, ... they will all have zero exponents, so we’ll regret for keeping them. $P_G(X_1, X_2,X_3,X_4)=X_1^6+6X_1^2X_4+3X_1^2X_2^2+8X_3^2+6X_2^3.$ According to the Polya’s theorem the pattern inventory for the set $$E$$ of representatives from each equivalence class is: $P(R,G,B,Y,W)=\frac1{24}\Big((R+G+B+Y+W)^6$ $+6(R+G+B+Y+W)^2(R^4+G^4+B^4+Y^4+W^4)$ $+3(R+G+B+Y+W)^2(R^2+G^2+B^2+Y^2+W^2)^2+8(R^3+G^3+B^3+Y^3+W^3)^2$ $+ 6(R^2+G^2+B^2+Y^2+W^2)^3\Big).$ We are interested in the number of terms containing at least two letters $$R$$. This is the same as the coefficient $$a_2$$ of $$R^2$$ in the expansion of the polynomial $$P(R,1,1,1,1)=a_0+a_1R+a_2R^2+\cdots$$. Notice that $P(R,1,1,1,1)=\frac1{24}\Big((R+4)^6+6(R+4)^2(R^4+4)+3(R+4)^2(R^2+4)^2+8(R^3+4)^2+ 6(R^2+4)^3\Big).$ The coefficient of $$R^2$$ in $$(R+4)^6$$ is equal to $$4^4\cdot \binom64$$. Similarly, the coefficient of $$R^2$$ in $$(R+4)^2(R^4+2)$$ is $$4\cdot R^2$$, and so on. The coefficient of $$R^2$$ in $$P(R,1,1,1,1)$$ is exactly

$\frac1{24}\Big(\binom64\cdot 4^4+6\cdot 4+3\cdot (16+16\cdot 8) +8\cdot 0 + 6\cdot 3\cdot 16\Big)=191.$