Counting colorful objects: part 1

Suppose you have a set of objects and some classes of equivalence defined by symmetries. The Cauchy-Froebenius-Burnside Lemma gives a method of counting the classes of equivalence. If the original objects are made up of parts, each part having a color from a set then a simple version of Polya's enumeration theorem gives even a more precise method of counting the classes of equivalence.

(NOTE: I'll use only the name Burnside for the Lemma, although he's the only one who didn't have much to do with finding it. I'm also ignorant about what the whole Polya enumeration theorem says: I'll talk here only about a very simple case. See this for a few mathematical definitions -- not needed to read on.)

Let's make precise some terms used in the first paragraph. I'll denote the set of objects by A. Symmetries are functions s:A->A that form a group. In other words id is a symmetry, a composition of two symmetries is a symmetry and and each symmetry has an inverse symmetry (possibly itself). Let's say there are S symmetries; infinite cases are not of particular interest for the programmer. We can draw a directed graph with this. Its nodes are objects and there is an edge from x to y if and only if for some symmetry s(x)=y. You can check that from the symmetry group definition given above it follows that the graph can be partitioned into classes such that for each two objects in the same class there is an edge between them and there is no edge between different classes. Please take a moment to see that this is true.

Fixpoints are loops in this graph. Burnside essentially says that in each class there are exactly S loops, although the number of objects can be any divisor of S. So if we denote the number of classes by C, then counting all fixpoints yields CS. Counting fixpoints is usually done by counting fixpoints of one symmetry, then fixpoints of another symmetry, etc. For example, the number of fixpoints due to id is |A|. After we add up all this we get CS and then we get C dividing by the number of symmetries.

But why S fixpoints in each class? We'll prove this in two steps. First: The number of edges from x to y is a constant when x ranges over all members of the class. There is a symmetry s such that s(x)=y. Now observe that:

{s0, ..., sS-1} = {ss0, ..., ssS-1}

All the elements on the right hand side are distinct: s has an inverse. This means that the number of edges from x to y equals the number of y's loops: you get from x to y by following s(x) and then one of y's loops. Since symmetries are inversable we can also say that the number of edges is constant when x is fixed and y varies. The first statement says something about incoming edges in an object, while this second statement says something about outgoing edges of an object.

We can now see that for a certain class the number of edges from x to y is a constant. This is true event when x=y. Let's denote this constant by L. Since there are S outgoing edges from each object the number of objects in the class must be S/L; and each object has L loops therefore there are S loops in the class.

Let's see a very simple example. This actually came up in a TopCoder problem (but unfortunately I was unable to find it because I can't remember its name, and I remember the statement only vaguely). Consider some people that you line-up. Two line-ups are considered different if and only if the height profile is different. Moreover height profiles that can be obtained from one-another by reflexion are considered not different. In this problem there are two symmetries: id and reflexion. For some reason (I really can't remember the statement :( ) it was easy to find the number of fixpoints for each: a and b. So the answer is (a+b)/2. In this simple case one can reason in another way. If you don't care about reflexion then there are a configurations. But since there are b symmetric configurations it means we have counted the non-symmetric a-b ones twice. Hence the answer is b+(a-b)/2. This concludes the Burnside part. Polya's next.

Very often the objects we want to count have structure: they are made of parts and each part can be colored. Formally we can write A=KP, where K is the set of colors (the letter C is already taken by the word "class") and P is the set of parts. Thus each object can be written as (k0, ..., kP-1). For such objects every symmetry can be written as a permutation of the parts.

Let's see another very simple example. We may want to count in how many ways we can color a bracelet with six sectors in black and white (using exactly one color for each sector). Then we will probably want to consider rotations as symmetries: 123450, 234501, 345012, and so on. In cycle notation these are: (501234), (513)(402), (52)(41)(20). How many fixpoints do these symmetries have? Well, there are two for the first one: all white and all black; there are 4 for the second symmetry; there are 8 for the third. It is not hard to see that in general there are |K|h, where h is the number of cycles in the permutation representation of the symmetry. That doesn't mean it is obvious :)

The next posts in this series will contain some programs that actually count something using these ideas.