Polya Theory

In the following degree 45 polynomial the coefficient of x^m is the number of nonisomorphic graphs with 10 vertices and m edges . For example, the polynomial tells us that there are 1251389 nonisomorphic graphs with 10 vertices and 24 edges. The Polya Theorem tells us how to quickly calculate this polynomial using the cycle index of an appropriately constructed permutation group.

How many distinct necklaces do we have with 20 beads drawn from a large supply of beads of three colors? This is a classical problem that is typically used to illustrate the power of Polya theorem. We first calculate the cycle index of the Dihedral group of order 20 and then substitute appropriate "weights" that are functions of the colors r, b, and g for the variable in the polynomial. The result is a polynomial in r, b, g that represents an inventory of distinct necklaces whose beads are colored r, b, or g. Two necklaces are distinct if one cannot be obtained from the other by a rotation or a flip or a combination of the two operations. For example, the polynomial tells us that there are 221110 necklaces with 20 beads 4 of which are colored b, 12 are colored g, and 4 are colored r.