## Polya’s Theorem## IntroductionBefore reading this section, make sure you are familiar with Burnside’s lemma. 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.
## Pattern inventoryIn 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.
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 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: 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 polynomialLet 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;
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 \);
## Polya’s theorem |

2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |