We are given a domain , a finite set , and a group acting on , acting on . Let and , i.e., acts on , and splits it into orbits. Visually it’s easiest to represent as coloring schemes of balls. In this case is the set of colors, and is the set of balls. If the balls are arranged in some graph with symmetry, then could be the symmetry group. being either the full symmetry group or the trivial group makes sense, but others are possible.
Definition 1 a weight , some algebra, e.g. , extends to a weight on by
We say is an invariant weight if for for any , and .
An orbit of on is called a pattern.
Proof: An easy application of not-Burnside’s theorem, which states
Lemma 3 (Sunnyside) Suppose is a finite set, acts on , is the set of points fixed by , and is the symmetries fixing . Suppose also that splits into orbits . Then
Proof: (of Sunnyside) Let .
Continuing with De Bruijn, we fix in the range of . Let . Then ‘s partition . Also acts on . Then acts on . By not-Burnside’s theorem,
where denotes the elements in fixed by . Multiply both sides by and sum over the range of gives (2).
Specializing De Bruijn’s result to , i.e., all colors are distinct, we get Polya’s theorem.
Now let , , and and as usual . Then we have
Fixing , and write as a product of cycles, with in the permutation representation of on (in other words can be thought of as a subgroup of ). We also denote , i.e., the support of .
Let be such that , i.e., is constant on the ‘s (we abuse as ). Consider the algebraic manipulation
The forgoing computation leads to
Theorem 4 (Polya) Say , and let , where number of cycles in of length . Then
In particular, the total number of patterns equal .
Examples: Let be , with ,
If we have two colors, then , and (recall ). And indeed there are 6 ways of coloring up to symmetry with two colors.
Example 2: Want 2 red and 2 blue: then we set and . And we need
. Indeed there are only two ways of distinct colorings in this situation, namely BRBR or BBRR.
More generally, given , the coefficient of is the number of colorings with color .
2. Cycle Indices
- , .
- the dihedral group: then for n odd
and for even
- : we get the familiar
- If acts on for , and , then acts on , and .
- Wreath product: Suppose is an index set, is a set, acts on , and acts on coordinate-wise. Also let be the wreath product of and under the above action. Then
Literature: James and Kerber. Rep. Theory of symmetrici groups.
A. Kerber: Group acting on sets.
R. Read: Polya’s theory of enumerations.
- Alas, computing the cycle indices is -P complete even for , a result of Jenaum-Golberg. Computational Polya Theory. This immediately implies that the Ising model partition function is -P complete to compute, for dimension .
More generally, for De Bruijn stuff i.e. nontrivial , we need to do
- associate for each ,
- for each , and , compute . Set . If , set .
- then the number of -patterns (i.e., orbits under action), invariant under , with color i, is .
- The total number of patterns is then
As a small application of Polya theory, we can do graph enumeration on a fixed number of vertices, up to permutation of the vertices:
, consists of distinct pairs , and , , or . See paper by P. Hanlon and R. W. Robinson.