Orbit-Stabilizer, Burnside and Pólya

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.

Orbit-Stabilizer Theorem:

Let $G$ be a group acting on a set $\Omega$.

For $x \in \Omega$ let $Orb(x) := \{ gx : g \in G \}$ and let $Stab_G(x) := \{ g \in G : gx = x \}$.

Then there is a bijection $\phi: G/Stab_G(x) \rightarrow Orb(x)$.

In particular $|G| = |Orb(x)||Stab_G(x)|$.

Proof:

Define $\phi: G/Stab_G(x) \rightarrow Orb(x)$ via $\phi(gStab_G(x)) = gx$.

To check well-definedness suppose $g_1Stab_G(x) = g_2Stab_G(x)$.

Then $g_2^{-1}g_1 \in Stab_G(x)$ so $\phi(g_1Stab_G(x)) = g_1x = g_2(g_2^{-1}g_1)x = g_2x = \phi(g_2Stab_G(x))$.

Thus $\phi$ is well-defined.

Clearly $\phi$ is a surjection.

If $\phi(g_1Stab_G(x)) = \phi(g_1Stab_G(x))$ then $g_1x = g_2x \Longrightarrow g_2^{-1}g_1x = x \Longrightarrow g_2^{-1}g_1 \in Stab_G(x)$.

Thus $g_1Stab_G(x) = g_2Stab_G(x)$ which shows $\phi$ is also an injection.

Hence $\phi$ is a bijection and so $[G:Stab_G(x)] = |Orb(x)|$ i.e $|G|/|Stab_G(x)| = |Orb(x)|$ and the statement follows.

Suppose $\Omega$ is the set of $6$ 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 $G$.
Now if you decide to fix one face, then there are $4$ rotations that won’t send the face elsewhere. For example if you fix the bottom face then you can twirl the cube $4$ times at $90^{\circ}$ 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 $4$ under the action of $G$. The orbit of the bottom face has size $6$ since there are $6$ 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 $G$ must be $6.4=24$.
It actually turns out the rotation group of the cube is isomorphic to the symmetric group $S_4$ but we will come back to this later.

As we will see, counting the number of distinct orbits of $\Omega$ under $G$ 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.

Burnside’s Lemma:

Let $G$ be a finite group acting on a set $\Omega$.

For every $g \in G$ define $Fix_{\Omega}(g) := \{ x \in \Omega : gx = x \}$.

Then $\#Orbits = \frac{1}{|G|} \sum_{g \in G} |Fix_{ \Omega }(g)|$.

Proof:

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 $S = \{(g,x) \in G \times \Omega : gx = x\}$.

On one hand by iterating over the elements of $G$ we get $|S| = \sum_{g \in G} |Fix_{ \Omega }(g)|$.
On the other hand by iterating over elements of $\Omega$ we get $|S| = \sum_{x \in \Omega} |Stab_{ G }(x)|$.

Clearly every element of $\Omega$ belongs to exactly one orbit (in fact Orbit membership is an equivalence relation on $\Omega$). Therefore $\Omega = \bigsqcup_{i = 1}^{n} \Omega_i$ where $\Omega_1,...,\Omega_n$ are the distinct orbits in $\Omega$ under $G$.

Moreover by Orbit-Stabilizer theorem we know that $|Stab_{ G }(x)|= \frac{|G|}{|Orb(x)|}\;\;\forall x \in \Omega$.

Thus
$|S| = \sum_{x \in \Omega} |Stab_{ G }(x)| = \sum_{i=1}^n \sum_{x \in \Omega_i} |Stab_{ G }(x)| = \sum_{i=1}^n \sum_{x \in \Omega_i} \frac{|G|}{|Orb(x)|} = \sum_{i=1}^n \sum_{x \in \Omega_i} \frac{|G|}{|\Omega_i|} = \sum_{i=1}^n |G| = n.|G|$.

Hence $n = \frac{1}{|G|} \sum_{g \in G} |Fix_{ \Omega }(g)|$.

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.

Problem 1 (Cube Colourings)

How many essentially different n-coloured cubes are there?

Solution

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

$\#Orbits = \frac{1}{24}( n^6 + 6n^3 + 3n^4 + 8n^2 + 6n^3)$

For example there are $\frac{1}{24}( 2^6 + 6.2^3 + 3.2^4 + 8.2^2 + 6.2^3 ) = \frac{1}{24}(240) = 10$ 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:

Definition (Cycle Index)

Let G be a group of symmetries (permutations) acting on $n$ objects.

Let $\sigma \in G$ and suppose $\sigma$ is a product of $k$ disjoint cycles of length $l_i$ for $1 \leq i \leq k$.

For such $\sigma$ define the monomial $M_{\sigma}(x_1,...,x_n) := \prod\limits_{i=0}^k x_{l_i}$ where $x_{l_1},...,x_{l_k}$ are indeterminates.

The Cycle Index of G is then defined via

\begin{aligned} C_G({\bf x}) := \frac{1}{|G|} \sum\limits_{\sigma \in G} M_{\sigma}({\bf x}) \end{aligned} where ${\bf x} = (x_1,...,x_n)$.

For example if $G = S_3$ then
$M_{(1)(2)(3)} = x_1^3$
$M_{(1\;2)(3)} = M_{(1\;3)(2)} = M_{(2\;3)(1)} = x_2x_1$
$M_{(1\;2\;3)} = M_{(1\;3\;2)} = x_3$
Thus $C_G = \frac{1}{6}( x_1^3 + 3x_2x_1 + 2x_3 )$.

Definition (Pattern Inventory)

Let G be a group of symmetries (permutations) acting on $n$ objects.

Let ${\bf v} = (n_1,...,n_k)$ be non-negative integers satisfying $n_1+...+n_k = n$
and let $a_{\bf v}$ represent the number of inequivalent colourings such that colour $y_i$ appears $n_i$ times.

Then the (Pólya) Pattern Inventory with respect to G is defined by

\begin{aligned} P_G(y_1,...,y_k) := \sum \limits_{{\bf v}} a_{\bf v}y_1^{n_1}...y_k^{n_k} \end{aligned}

The Pólya Enumeration Theorem (which we are about to prove) gives us a way of computing the coefficients $a_{\bf v}$ 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 $R^5G^4B$ coefficient $a_{(5,4,1)}$ in the inventory \begin{aligned} P_G(R,G,B) = \sum \limits_{i+j+k = 10} a_{(i,j,k)}R^{i}G^{j}B^{k} \end{aligned}.

Pólya Enumeration Theorem

Let G be a group of symmetries (permutations) acting on a set of n objects and
let $C_G$ denote the cycle index of G.

Then the pattern inventory for G using colours $y_1,...,y_k$ is given by

\begin{aligned} P_G(y_1,...,y_k) = C_G(\sum \limits_{i=1}^k y_i, \sum \limits_{i=1}^k y_i^2, ..., \sum \limits_{i=1}^k y_i^n ) \end{aligned}.

Proof

The following proof of the theorem is due to Richard P. Stanley.

Let ${\bf v} = (n_1,...,n_k)$ be a vector of non-negative integers summing to $n$.

Let $\Omega_{{\bf v}}$ denote the set of colourings of the $n$ objects where colour $y_i$ appears $n_i$ times.

If $\sigma \in G$ 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 $(1\;2\;3\;4)$ (i.e 90 degree rotation around an vertical axis) then faces $1,2,3,4$ must all have the same colour, otherwise the colouring is not fixed under the rotational symmetry.

Therefore $|Fix_{\Omega_{{\bf v}}}(\sigma)|$ is the coefficient of $y_1^{n_1}...y_k^{n_k}$ in $M_{\sigma}( \sum \limits_{i=1}^k y_i,\sum \limits_{i=1}^k y_i^2, ..., \sum \limits_{i=1}^k y_i^n )$

[To see this, note that if $\sigma$ contains an r-cycle then every monomial term in the pattern inventory coming from $\sigma$ should have a colour $y_i$ with exponent at least $r$ so the product $M_{\sigma}$ should generate all such monomials for arbitrary colours $y_i$, hence the factor $\sum \limits_{i=1}^k y_i^r$]

Let $y_{{\bf v}} := y_1^{n_1}...y_k^{n_k}$ where ${\bf v} = (n_1,...,n_k)$.

Running over all permissable vectors ${\bf v}$ we get

$\sum \limits_{{\bf v}} |Fix_{\Omega_{{\bf v}}}(\sigma)| y_{{\bf v}} = M_{\sigma}(\sum \limits_{i=1}^k y_i,\sum \limits_{i=1}^k y_i^2, ..., \sum \limits_{i=1}^k y_i^n)$.

Running both sides over all $\sigma \in G$ and dividing by $|G|$ we get

$LHS = \frac{1}{|G|} \sum \limits_{\sigma \in G} \sum \limits_{{\bf v}} |Fix_{\Omega_{{\bf v}}}(\sigma)| y_{{\bf v}} = \sum \limits_{{\bf v}} (\frac{1}{|G|} \sum \limits_{\sigma \in G} |Fix_{\Omega_{{\bf v}}}(\sigma)|)y_{{\bf v}} =$

$= \sum \limits_{{\bf v}} a_{\bf v}y_{{\bf v}} = P_G( y_1^{n_1},...,y_k^{n_k} )$
where the next to last equality follows from Burnside’s Lemma (or rather a weighted version of it)

$RHS = \frac{1}{|G|} \sum \limits_{\sigma \in G} M_{\sigma}(\sum \limits_{i=1}^k y_i,\sum \limits_{i=1}^k y_i^2, ..., \sum \limits_{i=1}^k y_i^n) = C_G(\sum \limits_{i=1}^k y_i, \sum \limits_{i=1}^k y_i^2, ..., \sum \limits_{i=1}^k y_i^n )$

$LHS = RHS$ and so the result follows.

Now we can finally exploit the machinery we have developed to complete some nice applications.

Problem 2 (Necklaces)

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?

Solution

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 $\sigma$ denote a $\frac{2\pi}{n}$ clockwise rotation and $\tau$ 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 $\langle \sigma,\tau| \sigma^n = 1, \tau^2=1, \tau \sigma \tau^{-1} = \sigma^{-1}\rangle$.

This group has a name, it is called the Dihedral Group of size 2n (often denoted $D_{2n}$).
As a permutation group it is generated by $\sigma = (1\;2\;...\;n)$ and $\tau = (1\;n)(2\;n-1)...(\frac{n}{2}\;(\frac{n}{2}+1))$ 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 $D_{2n}$ can be expressed in the form $\sigma^i \tau^j$ where $0 \leq i < n, 0 \leq j \leq 1$ by using repeated applications of the relation $\tau \sigma \tau^{-1} = \sigma^{-1}$ on a general element.

To apply Pólya Eumeration Theorem we need to compute the cycle index of $D_{2n}$.
To compute this index we need to understand the cycle structure of an arbitrary permutation in $D_{2n}$.

We can split the investigation into two pieces:

1. Rotations with flip (i.e permutations $\sigma^i \tau,\;\; 0 \leq i < n$)
2. Simple rotations (i.e permutations $\sigma^i,\;\; 0 \leq i < n$)

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 ($\frac{n}{2}$ 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 $\frac{n}{2}$ 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
$M_{\sigma^i \tau} = x_2^{\frac{n}{2}}$ in the former case and
$M_{\sigma^i \tau} = x_1^2x_2^{\frac{n-2}{2}}$ 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
$M_{\sigma^i \tau} = x_1x_2^{\frac{n-1}{2}}$

In summary the full cycle index for the permutations belonging under 1 is given by

$\frac{1}{|D_{2n}|} \sum \limits_{\sigma^i \tau \in D_{2n} \setminus \langle \sigma \rangle} M_{\sigma^i \tau}({\bf x}) = \begin{cases} \frac{1}{2n} (\frac{n}{2} x_2^{\frac{n}{2}} + \frac{n}{2} x_1^2x_2^{\frac{n-2}{2}}) & if\;\; n\; even \\ \\ \frac{1}{2n} (n x_1x_2^{\frac{n-1}{2}}) & if \;\;n\; odd \end{cases}$

We have left to classify permutations under 2.
Here we are really asked to compute the cycle index of the cyclic group of order $n$ (i.e the subgroup generated by $\sigma$ alone).

Consider an element $\sigma^i$ where $0 \leq i < n$ and let us examine its disjoint cycle decomposition.
Suppose the shortest cycle in $\sigma^i$ has length $m$ and let $x$ be a number moved by this cycle.
Let $y \neq x$ be a number moved by a different cycle.
We want to show that the cycle to which $y$ belongs have length $m$ also.

Clearly since $\sigma$ is a cycle permutation $\exists r \in \mathbb{N}$ such that $\sigma^r(x) = y$.
Now $(\sigma^{i})^m(y) = \sigma^{im}(\sigma^r(x)) = \sigma^r \sigma^{im}(x) = \sigma^r(x) = y$.
Therefore $y$ belongs to a cycle of $\sigma^i$ of length dividing $m$.
But $m$ was assumed to be minimal and therefore the cycle to which $y$ belongs must have length $m$ as well.

We have thus shown that all cycles in the cycle decomposition of $\sigma^i$ have same length.
Hence if $\sigma^i$ has order $d$ then $\sigma^i$ must be a product of $\frac{n}{d}$ disjoint $d$-cycles.

Let $\phi(d) := |\{ k \in \{1,...,d\} | gcd(k,d) = 1 \}|$ (this is the so called Euler Totient Function)

The number of elements of order $d$ in $\langle \sigma \rangle$ is given by $\phi(d)$.
(Explicitly these are given by $\sigma^{\frac{kn}{d}}$ where $gcd(k,d) = 1$)

Conversely by Langrange’s Theorem the order of every element in $\langle \sigma \rangle$ must divide $n$.

Hence the cycle index of $\langle \sigma \rangle$ is given by

$\frac{1}{|D_{2n}|} \sum \limits_{d|n} \phi(d) x_d^{\frac{n}{d}}$.

Hence the cycle index of $D_{2n}$ is given by

$C_{D_{2n}}({\bf x}) = \begin{cases} \frac{1}{2n} \left(\sum \limits_{d|n} \phi(d) x_d^{\frac{n}{d}} + \frac{n}{2} x_2^{\frac{n}{2}} + \frac{n}{2} x_1^2x_2^{\frac{n-2}{2}} \right) & if\;\; n\; even \\ \\ \frac{1}{2n} \left(\sum \limits_{d|n} \phi(d) x_d^{\frac{n}{d}} + n x_1x_2^{\frac{n-1}{2}}\right) & if \;\;n\; odd \end{cases}$

By Pólya Enumeration Theorem the pattern inventory for $D_{2n}$ is given by

$P_{D_{2n}}({\bf y}) = C_{D_{2n}} ( \sum \limits_{i=1}^k y_i,\sum \limits_{i=1}^k y_i^2, ..., \sum \limits_{i=1}^k y_i^{n} )$

Restricting to the special case where $n=6$ we may use Wolfram Alpha to expand:
$P_{D_{12}}((R,G,B)) =$
$C_{D_{12}}(R+G+B, R^2+G^2+B^2, R^3+G^3+B^3, ..., R^{6}+G^{6}+B^{6})=$
$\frac{1}{12} [ \phi(1)(R+G+B)^6 + \phi(2)(R^2+G^2+B^2)^3 + \phi(3)(R^3+G^3+B^3)^2 +$
$\phi(6)(R^6+G^6+B^6) + 3(R^2+G^2+B^2)^3 + 3(R+G+B)^2(R^2+G^2+B^2)^2 ] =$

$= B^6+B^5 G+B^5 R+3 B^4 G^2+3 B^4 G R+3 B^4 R^2+3 B^3 G^3+6 B^3 G^2 R+6 B^3 G R^2+3 B^3 R^3+3 B^2 G^4+6 B^2 G^3 R+11 B^2 G^2 R^2+6 B^2 G R^3+3 B^2 R^4+B G^5+3 B G^4 R+6 B G^3 R^2+ {\bf 6 B G^2 R^3} +3 B G R^4+B R^5+G^6+G^5 R+3 G^4 R^2+3 G^3 R^3+3 G^2 R^4+G R^5+R^6$

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 $\left( C_{10}H_8 \right)$ 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).

Problem 3 (Naphthol)

Naphthol is obtained from Naphthalene by replacing one of the Hydrogen atoms with a hydroxyl group (OH).

How many different isomers of Naphthol exists?

Solution

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:

$\iota = (1)(2)(3)(4)(5)(6)(7)(8)$
$x = (1\;4)(5\;8)(6\;7)(2\;3)$
$y = (1\;8)(2\;7)(3\;6)(4\;5)$
$xy = (1\;5)(2\;6)(3\;7)(4\;8)$

(sorry for the sloppy animation!)

As an abstract group the symmetries have presentation $G = \langle x,y\;|\;x^2=1,y^2=1,xy=yx \rangle \cong C_2 \times C_2$.
$C_2 \times C_2$ 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 $C_2 \times C_2$ as follows

$C_{C_2 \times C_2}({\bf x}) = \frac{1}{4}(x_1^8 + 3x_2^4)$.

Therefore with $A$ representing Hydrogen and $B$ representing a Hydroxyl group we get

$P_{C_2 \times C_2}(A,B) = \frac{1}{4}C_{C_2 \times C_2}( A+B, A^2+B^2,...,A^8+B^8 ) =$
$\frac{1}{4}((A+B)^8 + 3(A^2+B^2)^4) =$
$= A^8+{\bf 2 A^7 B} +10 A^6 B^2+14 A^5 B^3+22 A^4 B^4+14 A^3 B^5+10 A^2 B^6+2 A B^7+B^8$

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.

Exercise 1 (Dice -Easy)

How many different 6-sided dice can you build if each number in $\{ 4,5,6 \}$ 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 )

Exercise 2 (Tetrahedron – Intermediate )

How many different ways are there of colouring the faces of a Tetrahedron in 3 colours under rotational symmetry?

Exercise 3 (Triphenylamine – Intermediate )

Triphenylamine $(C_6H_5)_3N$ 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)