Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Pólya Enumeration Theorem"

(FUCK)
 
 
Line 1: Line 1:
−
IJIJM
+
The '''Pólya Enumeration Theorem''' is a useful generalization of [https://artofproblemsolving.com/wiki/index.php/Burnside%27s_Lemma Burnside's Lemma] in [https://artofproblemsolving.com/wiki/index.php/Group_theory Group Theory]. Published first by J. Howard Redfield in 1927 and then independently discovered by George Pólya in 1937, the theorem is also commonly used in [https://artofproblemsolving.com/wiki/index.php/Combinatorics combinatorics] problems. 
 +
 
 +
== Background ==
 +
Let <math>G</math> be a finite group acting on some finite set <math>\mathcal{X}</math> with <math>|\mathcal{X}|=N</math>.  To each partition <math>N=\sum n_j</math> of <math>N</math> we may attach the monomial
 +
<cmath>\prod_j t_{n_j}</cmath>
 +
in the variables <math>t_1,t_2,t_3,...,t_N</math>.  The '''cycle type''' of an element <math>g\in G</math> is the partition of <math>N</math> given by the cycle size of the orbits of <math>g</math> acting on <math>\mathcal{X}</math>, which we will denote as <math>z_g(t_1,..., t_N)</math>.  Furthermore, we define the '''cycle index''' for the pair <math>(G,\mathcal{X})</math> of <math>G</math> acting on <math>\mathcal{X}</math> as the [https://artofproblemsolving.com/wiki/index.php/Generating_function generating function]
 +
<cmath>Z(t_1,t_2,...,t_N)=\frac{1}{|G|}\sum_{g\in G} z_g(t_1,t_2,...,t_N)</cmath>
 +
== The Theorem ==
 +
Let <math>G</math> act on <math>\mathcal{X}</math> with the cycle index <math>Z(t_1,t_2,...,t_N)</math> where <math>|\mathcal{X}|=N</math>.  The generating function for the number of ways to paint <math>\mathcal{X}</math> in colors <math>a_1,a_2,...,a_n</math> up to <math>G</math> symmetry is given by evaluating <math>Z(t_1,t_2,...,t_N)</math> at the values
 +
<cmath>t_k=a_{1}^k+a_{2}^k+...+a_{n}^k.</cmath>

Latest revision as of 18:51, 24 November 2021

The Pólya Enumeration Theorem is a useful generalization of Burnside's Lemma in Group Theory. Published first by J. Howard Redfield in 1927 and then independently discovered by George Pólya in 1937, the theorem is also commonly used in combinatorics problems.

Background

Let $G$ be a finite group acting on some finite set $\mathcal{X}$ with $|\mathcal{X}|=N$. To each partition $N=\sum n_j$ of $N$ we may attach the monomial \[\prod_j t_{n_j}\] in the variables $t_1,t_2,t_3,...,t_N$. The cycle type of an element $g\in G$ is the partition of $N$ given by the cycle size of the orbits of $g$ acting on $\mathcal{X}$, which we will denote as $z_g(t_1,..., t_N)$. Furthermore, we define the cycle index for the pair $(G,\mathcal{X})$ of $G$ acting on $\mathcal{X}$ as the generating function \[Z(t_1,t_2,...,t_N)=\frac{1}{|G|}\sum_{g\in G} z_g(t_1,t_2,...,t_N)\]

The Theorem

Let $G$ act on $\mathcal{X}$ with the cycle index $Z(t_1,t_2,...,t_N)$ where $|\mathcal{X}|=N$. The generating function for the number of ways to paint $\mathcal{X}$ in colors $a_1,a_2,...,a_n$ up to $G$ symmetry is given by evaluating $Z(t_1,t_2,...,t_N)$ at the values \[t_k=a_{1}^k+a_{2}^k+...+a_{n}^k.\]

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Pólya_Enumeration_Theorem&oldid=166257"