Orbit-Stabilizer, Burnside and Pólya

RotatingCube

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.

 

Here is how you can think about this result:
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:

CubeRotationSymmetry

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:

CubeFaceNumbering

Then we can obtain the following table by examining the cycle decomposition of the face permutations.

FixedColouringsCube

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.

NecklaceGIF3

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

NecklaceReflectionalAxesEven

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:

NecklaceReflectionalAxesOdd

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

Naphthalene-img

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!)

3235398

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)

Napthol-1-2

 
This concludes our discussion of this topic.
Below are some exercises for you to try.
 
 
 

Exercise 1 (Dice -Easy)

Dice2

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 )

Tetrahedron

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

 

Exercise 3 (Triphenylamine – Intermediate )

TriphenylamineAndSkeleton

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)

Advertisements
This entry was posted in Algebra, Combinatorics, Uncategorized and tagged , , , , , , , , , , , . Bookmark the permalink.

2 Responses to Orbit-Stabilizer, Burnside and Pólya

  1. Pingback: Fantasy Team Superdry Toyota

  2. Pingback: How To Prove Somethin’ | Mathematical Mélange

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s