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.
Let be a group acting on a set .
For let and let .
Then there is a bijection .
In particular .
Define via .
To check well-definedness suppose .
Then so .
Thus is well-defined.
Clearly is a surjection.
If then .
Thus which shows is also an injection.
Hence is a bijection and so i.e and the statement follows.
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.
Let be a finite group acting on a set .
For every define .
Then .
To prove this we use the classical counting argument of “counting the same thing in two ways”.
The natural thing to count is the set of all fixed pairs, namely .
On one hand by iterating over the elements of we get .
On the other hand by iterating over elements of we get .
Clearly every element of belongs to exactly one orbit (in fact Orbit membership is an equivalence relation on ). Therefore where are the distinct orbits in under .
Moreover by Orbit-Stabilizer theorem we know that .
Thus
.
Hence .
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.
How many essentially different n-coloured cubes are there?
We are set to count the number of orbits under the action of the 24 different rigid rotations (which we are about to enumerate). To use the Burnside Lemma we need to find the number of fixed colourings of each of the 24 rotations.
Fortunately these rotations belong to 3 classes:
If you are interested in viewing an animated depiction of the (13 total) rotation axes I found this excellent video on YouTube.
Suppose now we number the faces as below:
Then we can obtain the following table by examining the cycle decomposition of the face permutations.
Burnside’s Lemma now gives
For example there are ways of colouring the faces of a cube in Red and Black.
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:
Let G be a group of symmetries (permutations) acting on objects.
Let and suppose is a product of disjoint cycles of length for .
For such define the monomial where are indeterminates.
The Cycle Index of G is then defined via
where .
For example if then
Thus .
Let G be a group of symmetries (permutations) acting on objects.
Let be non-negative integers satisfying
and let represent the number of inequivalent colourings such that colour appears times.
Then the (Pólya) Pattern Inventory with respect to G is defined by
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 .
Let G be a group of symmetries (permutations) acting on a set of n objects and
let denote the cycle index of G.
Then the pattern inventory for G using colours is given by
.
The following proof of the theorem is due to Richard P. Stanley.
Let be a vector of non-negative integers summing to .
Let denote the set of colourings of the objects where colour appears times.
If fixes a particular colouring then every object permuted by one of its cycles (in its disjoint cycle decomposition) must have the same colour.
For example if I permute the faces of a cube according to (i.e 90 degree rotation around an vertical axis) then faces must all have the same colour, otherwise the colouring is not fixed under the rotational symmetry.
Therefore is the coefficient of in
[To see this, note that if contains an r-cycle then every monomial term in the pattern inventory coming from should have a colour with exponent at least so the product should generate all such monomials for arbitrary colours , hence the factor ]
Let where .
Running over all permissable vectors we get
.
Running both sides over all and dividing by we get
where the next to last equality follows from Burnside’s Lemma (or rather a weighted version of it)
and so the result follows.
Now we can finally exploit the machinery we have developed to complete some nice applications.
Compute the pattern inventory for the number of n-bead, k-colour necklaces.
How many 6-bead necklaces may be constructed using 3-Red, 2-Green and 1-Blue beads?
We must first figure out the group of symmetries for a necklace.
I mentioned earlier that the symmetries of a necklace are expressed via rotations and flips and indeed all coloured necklaces obtained from such symmetries should be viewed the same.
If we let denote a clockwise rotation and denote a flip (i.e reflection) about the y-axis then one can show (geometrically or algebraically) that the full symmetry group is given abstractly by the presentation .
This group has a name, it is called the Dihedral Group of size 2n (often denoted ).
As a permutation group it is generated by and with obvious adjustment for n odd.
You can check that these two generators satisfy the relators of the group presentation.
Moreover it can be checked that any element of can be expressed in the form where by using repeated applications of the relation on a general element.
To apply Pólya Eumeration Theorem we need to compute the cycle index of .
To compute this index we need to understand the cycle structure of an arbitrary permutation in .
We can split the investigation into two pieces:
- 1. Rotations with flip (i.e permutations )
- 2. Simple rotations (i.e permutations )
In 1 the symmetries are really realized as simple flips over a different symmetry axis (see picture below).
As you can see from the picture there are two kinds of axes, those which go through opposite edges and those which go through opposite beads. There are equally many of both types when n is even ( of both).
In the case where the symmetry axis goes through a pair of opposite edges, a flip entails swapping pairs of beads on the necklace i.e we are dealing with a product of disjoint transpositions.
In the other case where the symmetry axis goes through a pair of opposite beads then we are also swapping pairs of beads, except for the beads lying on the axis which are fixed by the reflection.
The cycle index monomial for n even is therefore given by
in the former case and
in the latter.
If n is odd the symmetry axes go through opposite edge and bead as depicted below:
Thus there is only one type of reflectional symmetry swapping pairs of beads while fixing the bead crossed by the symmetry axis.
The cycle index monomial for n odd is therefore given by
In summary the full cycle index for the permutations belonging under 1 is given by
We have left to classify permutations under 2.
Here we are really asked to compute the cycle index of the cyclic group of order (i.e the subgroup generated by alone).
Consider an element where and let us examine its disjoint cycle decomposition.
Suppose the shortest cycle in has length and let be a number moved by this cycle.
Let be a number moved by a different cycle.
We want to show that the cycle to which belongs have length also.
Clearly since is a cycle permutation such that .
Now .
Therefore belongs to a cycle of of length dividing .
But was assumed to be minimal and therefore the cycle to which belongs must have length as well.
We have thus shown that all cycles in the cycle decomposition of have same length.
Hence if has order then must be a product of disjoint -cycles.
Let (this is the so called Euler Totient Function)
The number of elements of order in is given by .
(Explicitly these are given by where )
Conversely by Langrange’s Theorem the order of every element in must divide .
Hence the cycle index of is given by
.
Hence the cycle index of is given by
By Pólya Enumeration Theorem the pattern inventory for is given by
Restricting to the special case where we may use Wolfram Alpha to expand:
From the pattern inventory expansion we can read off the number of colourings possible for a 6 bead necklace using 3 Red, 2 Green and 1 Blue beads (see bold term).
Hence there are 6 such necklaces.
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).
Naphthol is obtained from Naphthalene by replacing one of the Hydrogen atoms with a hydroxyl group (OH).
How many different isomers of Naphthol exists?
One easily verifies that the double hexagon has two axes of reflective symmetry and also that the product of the reflections represent a 180 degree rotation in the plane. This gives 4 distinct permutations which we can list explicitly given the numbering below:
(sorry for the sloppy animation!)
As an abstract group the symmetries have presentation .
acts on the 1 Hydroxyl and 7 Hydrogen bindings (in this context the different bindings and their multiplicity represent our “colour weight”).
We can now compute the cycle index of as follows
.
Therefore with representing Hydrogen and representing a Hydroxyl group we get
Thus there are two isomers of Naphthol (called 1-Naphthol and 2-Naphthol respectively)
This concludes our discussion of this topic.
Below are some exercises for you to try.
How many different 6-sided dice can you build if each number in must appear on exactly two faces?
(Hint: Look carefully at Problem 1 where we effectively calculated the cycle index of the symmetries of a cube – use it )
How many different ways are there of colouring the faces of a Tetrahedron in 3 colours under rotational symmetry?
Triphenylamine is a molecule with 3 carbon rings attached to a central nitrogen atom and 15 hydrogen atoms binding remaining free carbons.
How many isomers can be obtained by replacing 6 Hydrogen atoms with 6 Hydroxyl (OH) groups?
(Tip: You may want to use Wolfram Alpha to expand the pattern inventory)
Pingback: Fantasy Team Superdry Toyota
Pingback: How To Prove Somethin’ | Mathematical Mélange