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 1a 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.

Theorem 2(de Bruijn): Let be an invariant weight,

*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

**Theorem 5**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

- Find
- 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.

Friend, this is a fantastic blog. I cannot believe that I haven’t run into it before. The only comment I’d offer is I wish you’d ‘categorize’ them. I have been following your alg. comb. lecture series, but I wish I could just go to a category labeled ‘Algebraic Combinatorics’ for easy access–but this is a very minor detail!

Just out of curiousity, what part of probability are you working in?

Best,

Alex Youcis

Dear Alex,

Thank you for your interest in my blog. You are the first one to make a comment on the mathematical content. I will follow your advice to categorize the material from now on as well as back issues. In fact all the algebraic combinatorics lectures are taken from my advisor Persi Diaconis’ course. I am working in markov chain mixing, random matrix theory, as well as discrete probability models with symmetry.

Friend,

That is shocking that I am the first one to comment. This is a legitimate blog with interesting topics etc. Keep up the good work!

As for your areas of research I must admit that while I know what a Markov chain is I have no idea what Markov chain mixing is. Also, I am only tangentially aware of random matrix theory after hearing about Montgomery’s result concerning the distrbution of the zeta zeros.

Best,

Alex

Also, how do you hyperlink back to a previous equation? For example, in your Berry-Esseen post you hyperlinked (1) and it, when clicked, brough the screen back to equation (1).

you can label the equations using \label{} and refer back to it using \eqref{} just as in usual latex. The easiest way is to use latex2wp, a free python script that converts latex files into wordpress latex format. I actually wrote a blog entry a while ago on how to make latex2wp into an executable file for windows system. You can search for that. Random matrix theory has connections to lots of other discrete models, due to its representation theoretic significance. A personal hero of mine is Kurt Johansson, who did lots of hardcore analytic stuff in related areas.