Pólya Enumeration

Pólya Counting enables you to count the equivalence classes of group acting on a set. For example, you might want to find the number of ways to color the corners of a square red or blue, respective of symmetry. The permutation group of symmetries is the dihedral group $D_4$. Pólya Counting gives the generating function $$P_{D_4}(r+b,r^2+b^2,r^3+b^3,r^4+b^4) =  r^4 +r^3b + 2r^2b^2 + rb^3 + b^4$$ where the coefficient in front of $r^pb^q$ tells you the number of nonequivalent colorings given that $p$ corners are colored red and $q$ are colored blue. Thus, the total number is of colorings is 6.

This method can be easily applied to PE 281: Pizza Toppings. It can also be used to count the number of non-isomorphic graphs. [code]

I've Tex'd up some notes for my own reference that are accessible in the link below. The proof is only outlined so it is a bit terse but the example problems should be enough to show how the method is used. Polya Counting Notes


_________________________________________________________________________________