Burnside’s Lemma and Polya Enumeration Theorem (1)

[ Note: this article assumes you know some rudimentary theory of group actions. ]

Let’s consider the following combinatorial problem.

Problem. ABC is a given equilateral triangle. We wish to colour each of the three vertices A, B and C by one out of n possible colours. Furthermore, two colourings are considered identical if we can obtain one from the other by rotating or reflecting the triangle. How many distinct colourings are there?

For example, all the following colourings are considered identical.

Note that the symmetries comprise of three rotations in the top row and three reflections in the bottom row. More generally, the group of symmetries of a regular n-gon comprises of n rotations – including the identity rotation – as well as n reflections; this is called the dihedral group of order n.

For our case, the dihedral group D₃ is isomorphic to the full symmetric group S₃. Relabeling the vertices A, B and C as 1, 2 and 3, the six symmetries above are respectively given by 1, (1, 3, 2), (1, 2, 3), (2, 3), (1, 3) and (1, 2).

Without symmetries, we clearly have $n^3$ colourings since each vertex can take n colours independently. Letting X denote the set of these colourings, the group S₃ acts on X by permuting the vertices. Our objective is now to compute $|S_3\backslash X|$ , the number of orbits under this group action. To that end, the following result is phenomenally useful.

Burnside’s Lemma. Let G be a finite group acting on a finite set X. Then:

$|G\backslash X| = \frac 1 {|G|}\sum_{g\in G} |X^g|$ ,

where $X^g=\{x \in X: gx = x\}$ is the set of all elements of X fixed by g.

Proof.

Consider the set $S = \{(g,x)\in G\times X: gx = x\}$ . We’ll compute |S| in two ways. Summing over g, we get $|S| = \sum_{g\in G} X^g$ , the RHS.

Summing over x, we get $|S| = \sum_{x\in X} |G_x|$ , where $G_x$ is the isotropy group of x and $|G_x| = |G|/|Gx|$ , where Gx is the orbit of x. Hence,

$|S| = \sum_{x\in X}\frac{|G|}{|Gx|} = |G|\sum_{x\in X} \frac 1 {|Gx|} = |G|\times |G\backslash X|$ ,

where the last equality follows from the fact that since each element x contributes 1/(orbit size) to the sum, the grand total is just the number of orbits. Matching the two expressions, we’re done. ♦

Solution to Our Problem.

To compute $|S_3\backslash X|$ , let’s compute $|X^g|$ for each element $g\in S_3$ :

g=e : all colourings are fixed, so $|X^g| = |X| = n^3$ ;
g=(1, 2): a colouring lies in X^g if and only if vertices 1 and 2 have the same colour, this gives $|X^g| = n^2$ ;
g=(2, 3), (1, 3): similarly, $|X^g| = n^2$ ;
g=(1, 2, 3), (1, 3, 2): a colouring lies in X^g if and only if all vertices have the same colour; thus $|X^g| = n$ .

Hence, Burnside’s lemma tells us the answer to our problem is:

$\frac 1 6 (n^3 + 3n^2 + 2n) = \frac {n(n+1)(n+2)}6.$ ♦

Exercise.

Find the number of colourings of the vertices of a square ABCD by n colours, where two colourings are identical if they can be obtained from each other by rotation or reflection. What about a regular pentagon ABCDE? Or a solid tetrahedron ABCD? Or a solid tetrahedron excluding reflections?

Answer (highlight to read)

For square: n(n+1)(n²+n+2)/8.
For pentagon: n(n²+1)(n²+4)/10.
For tetrahedron with reflections: n(n+1)(n+2)(n+3)/24.
For tetrahedron without reflections: n²(n²+11)/12.

Polya Enumeration Theorem

A large class of problems can be classified under the case of “colouring problems“. Namely, suppose finite group G acts on a finite set of points X. If Y denotes a finite set of colours, the set of colourings is denoted by $S = Y^X$ , which is the set of all functions X→Y. The action of G on X extends to an action on S as follows:

If $g\in G$ and $f:X\to Y$ is a colouring, then the action is given by the composition

$g\cdot f = f\circ g^{-1}:X\to Y$ .

[ The inverse is necessary so that $(g_1g_2)\cdot f = g_1\cdot(g_2\cdot f)$ . ]

Burnside’s lemma then tells us that $|G\backslash S| = \frac 1{|G|} \sum_{g\in G}|S^g|$ . But $|S^g|$ is not hard to compute: if we express the action of g on X as a permutation, and c(g) denotes its number of cycles (or orbits), then $|S^g| = |Y|^{c(g)}$ since the points in each cycle must share the same colour. This gives:

$|G\backslash S| = \frac 1{|G|} \sum_{g\in G} n^{c(g)}$ , where n = |Y|.

In summary…

Polya Enumeration Theorem A. For a finite group G acting on a finite set X, the number of colourings X→Y up to symmetry (two colourings are identical if they can be obtained from each other via G-action) is given by:

$\frac 1{|G|} \sum_{g\in G} |Y|^{c(g)}$ ,

which is a polynomial in |Y|.

For example, in the case where X = {1, 2, 3} in our first problem. Then:

c(e) = 3;
c((1,2)) = c((2,3)) = c((1,3)) = 2;
c((1,2,3)) = c((1,3,2)) = 1.

And we obtain $\frac 1 6 (n^3 + 3n^2 + 2n)$ as above. Let’s consider more examples.

Example 1

On a 2k × 2k chessboard, each square is coloured with one out of n possible colours. Two colourings are identical if they can be obtained from each other by reflecting or rotating the chessboard. Find the number of colourings.

Solution

Let’s consider the 8 symmetries of the square:

The grey area shows the orbit representatives when we let each symmetry act on the 4n² squares. From the above diagram and Polya enumeration theorem, we get:

number of unique colourings = $\frac 1 8 (1\times n^{4k^2} + 2\times n^{k^2} + 3\times n^{2k^2} + 2\times n^{k(2k+1)})$ .

Notice that when k=1, this simplifies to $\frac 1 8(n^4 + 2n^3 + 3n^2 + 2n)$ which is precisely the number of ways to colour the four vertices of a square with n colours, up to rotational/reflection symmetry. ♦

Example 2

Consider a 3 × 3 chessboard. We wish to colour each of its 9 squares with one out of n colours. Two colourings are identical if we can obtain one from the other by first permuting the rows and then permuting the columns. How many unique colourings are there?

Solution

First note that we have G=S₃ acting on the set of 9 squares in two distinct ways. If S denotes the set of columns and T denotes the set of rows, then the whole board is simply S × T, with G × G acting on it component wise.

For each $(g, h)\in G\times G$ , consider the number of orbits c((g, h)). This only depends on the conjugancy classes of g and h. For example:

g=(1, 2), h=(1, 3): the orbits of (g, h) are given by {(1, 1), (2, 3)}, {(1, 2), (2, 2)}, {(1, 3), (2, 1)}, {(3, 1), (3, 3)}, and {(3, 2)};
g=(1, 2, 3), h=(1, 2, 3): the orbits of (g, h) are {(1, 1), (2, 2), (3, 3)}, {(1, 2), (2, 3), (3, 1)} and {(1, 3), (2, 1), (3, 2)}.

This gives us the following table:

so the solution is $\frac 1 {36} (n^9 + 6n^6 + 9n^5+8n^3 + 12n^2)$ . ♦

Stirling Numbers of the First Kind

Suppose the full symmetric group G = S(X) acts on X, and |X|=k, |Y|=n. Recall that Polya theorem gives the number of colourings as a polynomial in n (depending on k):

$\frac 1 {k!}\sum_{g\in S_k} n^{c(g)},$

where the coefficient of $n^c$ is the number of elements $g\in S_k$ with exactly c orbits.

On the other hand, we can simplify the expression by elementary combinatorics! Indeed, since we can permute the elements of X freely, the colouring is uniquely determined by the number of occurrences of each colour. To put it explicitly, denote the colours by 1, 2, …, n. Then we can permute the elements of X so that the colours occur in increasing order: (1, 1, …, 1, 2, 2, …, 2, 3, 3,… ).

Hence each colouring corresponds to a solution to the linear Diophantine equation:

$x_1 + x_2 + x_3 + \ldots + x_n = k$ ,

where each $x_i\ge 0$ is the number of occurrences of colour i. Elementary combinatorics then tell us the number of solutions is:

${n+k-1\choose k} = \frac 1 {k!} (n+k-1)(n+k-2)\ldots(n+1)n$ .

Equating the two expressions, we obtain:

Theorem. The number of elements of $g\in S_k$ with exactly c orbits is given by the coefficient of $x^c$ in the polynomial:

$x(x+1)(x+2)\ldots (x+k-1)$ .

This number is denoted by $\left[\begin{matrix}k\\c\end{matrix}\right]$ and is called a Stirling number of the first type.

For example, for k=5, we get:

$x(x+1)(x+2)(x+3)(x+4) = x^5 + 10x^4 + 35x^3 + 50x^2 + 24x,$

so there are 35 elements of $S_5$ with exactly 3 cycles (or orbits). These are of the form:

(a)(b)(c, d, e) : C(5, 3) × 2 = 20;
(a)(b, c)(d, e) : C(5, 2) × C(3, 2) / 2 = 15.

Exercises

Find the number of ways of colouring the 8 vertices of a cube with n colours, where two colourings are identical if one can be obtained from the other via rotation. [ Hint: there are 24 rotations of a cube. ]
Repeat example 1 above for a (2k+1) × (2k+1) chessboard, with n colours.
Find the number of ways to place k chairs around a table if there are n types of chairs available (each type of unlimited quantity). Two placings are identical if they can be obtained from each other via a rotation.
On a 8 × 8 chessboard, each square is coloured black or white such that every row and every column have an even number of black squares. Two colourings are identical if they can be obtained from each other by reflecting / rotating the square. Find the number of unique colourings.
Prove the following identities involving Stirling numbers of the first kind.
1. $\left[\begin{matrix}n+1\\k\end{matrix}\right] = n\left[\begin{matrix}n\\k\end{matrix}\right] + \left[\begin{matrix}n\\k-1\end{matrix}\right]$
2. $\left[\begin{matrix}n\\n-2\end{matrix}\right] = \frac 1 4(3n-1){n\choose 3}$
3. $\left[\begin{matrix}n\\2\end{matrix}\right] = (n-1)! (1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 {n-1})$ .

Answers (Highlight to Read)

Consider the rotations of a cube through an axis, with the corresponding terms in Polya formula:
- identity: c = 8;
- axis passes through a face (90 deg): c = 2 for 3×2 = 6 cases;
- axis passes through a face (180 deg): c = 4 for 3 cases;
- axis passes through an edge: c = 4 for 6 cases;
- axis passes through a vertex: c = 4 for 4×2 = 8 cases.
- Thus, answer = (n⁸ + 17n⁴ + 6n²)/24.
The terms in Polya formula:
- rotation of 90 deg: c = k² + k + 1;
- rotation of 180 deg: c = 2k² + 2k + 1;
- reflection about horizontal/vertical axis (2×): c = (k+1)(2k+1);
- reflection about diagonal (2×): c = (k+1)(2k+1).
- Thus, answer = (n^(4k² +4k + 1) + 2n^(k² + k + 1) + n^(2k² + 2k + 1) + 4n^((k+1)(2k+1)))/8.
For each rotation of t steps, t = 0, …, k-1, we have c(t) = gcd(t, k), where gcd(0, k) = k. On the other hand, for each d|k, there are exactly φ(k/d) numbers whose gcd with k is exactly d, where φ is the Euler totient function. Thus, the final sum is (1/k) ∑_d|k φ(k/d)n^d. Note that when k is prime, we get (n^k + (k-1)n)/k, so Fermat’s Little Theorem occurs as a corollary.
We can’t use Polya theorem directly, so let’s revert to Burnside’s lemma. The full set of colourings, excluding symmetry, is 2⁴⁹, by considering linear algebra over Z/2.
- Symmetry under ±90 deg rotation: we pick the top-left 4×4 square as a set of representatives. However, we have 3 linear relations (a priori 4, but 1 is superfluous), so total number = 2¹³.
- Symmetry under 180 deg rotation: pick the top-half 4×8 rectangle as a set of representatives. With 7 linear relations (a priori 8, but 1 is superfluous), this gives 2²⁵.
- Symmetry under reflection about horizontal axis: pick top half rectangle as representatives. With 4 linear relations, this gives 2²⁸. Same with vertical.
- Symmetry under reflection about diagonal axis: pick the 36 squares on or above the main diagonal. With 8 linear relations, this gives 2²⁸.
- Final answer = (2⁴⁹ + 2 × 2¹³ + 2²⁵ + 4 × 2²⁸)/8.

Leave a comment Cancel reply

Recent Posts

Archives

Categories

Meta

Pages