Quite frequently Algebra conspires with Combinatorics to produce useful results.
In this post the intention is to discuss algebraic results such as Orbit-Stabilizer Theorem, Burnside’s Lemma and Pólya’s Enumeration Theorem to answer combinatorial questions such as:
- “How many essentially different ways are there of colouring the faces of a cube in n colours?”
- “How many different k-colour necklaces can be constructed using n beads?”
- “How many isomers exist of a particular chemical compound molecule?”
These are all questions that depend on enumerating configurations (or patterns) under some notion of equivalence, e.g rotational symmetry. For example rotating or flipping a coloured necklace doesn’t produce a new necklace, even though the colour of the bead at the same position may have changed as a result of the operation.
Therefore a more generalized treatment is required from more elementary combinatorics questions such as “How many ways can you (statically) colour n distinguishable beads in k colours?”
As a brief note before continuing, this post may ask a little bit more of the reader than is usually the case in this blog.
In particular I will assume some basic familiarity with Groups and Group Actions.
Let’s start by reviewing two fundamental results about group actions, namely the Orbit-Stabilizer theorem and the Burnside Lemma.
Here is how you can think about this result:
Suppose is the set of faces of a cube.
You can act on these faces using rigid rotations i.e rotations that leave the cube in the same position but with faces permuted.
Such rotations form a group .
Now if you decide to fix one face, then there are rotations that won’t send the face elsewhere. For example if you fix the bottom face then you can twirl the cube times at around a vertical axis while keeping the bottom face in its place. Any other rigid rotation will move the bottom face somewhere else. In other words the stabilizer of the bottom face has order under the action of . The orbit of the bottom face has size since there are faces on the cube and you can send the bottom face to any other face using rigid rotations.
The orbit stabilizer theorem tells us that the order of the rotation group must be .
It actually turns out the rotation group of the cube is isomorphic to the symmetric group but we will come back to this later.
As we will see, counting the number of distinct orbits of under will be instrumental in answering the type of questions posed in the beginning. The next result called Burnside’s Lemma will help us do just that.
This lemma tells us that the number of orbits under an action is the same as the average number of elements fixed by the action. The motivation for counting orbits is quite clear in the context of cube colouring. If there are two colourings belonging to the same orbit then we should only count the colourings once because they are sitting on the same cube and can therefore be rotated to one another. The number of orbits thus represent the number of different colourings under rotational symmetry.
Let’s look at the problem of counting cube colourations more closely now that we have Burnside’s lemma at our disposal, which reduces the problem to finding the number of colourings fixed under a particular rotation.
Burnside’s Lemma can help us understand in how many ways we can freely colour the faces of a cube, or the beads of a necklace. What if we want to impose some restrictions on the colourings? Say we want to know how many ways we can colour a 6-bead necklace in 3 Red, 2 Black and 1 White bead?
By pushing the Burnside Lemma a bit further we can answer this too. This is where Pólya pattern inventories come in.
Let’s make two important definitions before we proceed:
For example if then
The Pólya Enumeration Theorem (which we are about to prove) gives us a way of computing the coefficients of the pattern inventory with respect to a group.
For example if we would like to calculate the number of inequivalent 5 Red, 4 Green, 1 Blue – colourings of 10 objects under symmetries of G we are interested in the coefficient in the inventory .
Now we can finally exploit the machinery we have developed to complete some nice applications.
Pólya counting theory also has applications in chemistry (among several other areas).
Chemists frequently use the enumeration formula to calculate the number of different isomers of a compound molecule.
Here is a simple taste of such an application.
Naphthalene is an organic compound mainly used in pesticides to keep insects away but has also got other niche applications such as for pyrotechnical special effects where it is used for simulated explosions and black smoke. Naphthalene has ten carbon atoms arranged in a double hexagon, binding eight hydrogen atoms (see below).
This concludes our discussion of this topic.
Below are some exercises for you to try.