From: Ray <ray17@stupid.com>
Subject: Re: Colouring a cube
Date: Fri, 04 Feb 2000 20:17:47 -0500
Newsgroups: sci.math
Summary: Using Burnside's Lemma to count symmetric patterns

This is a simple application of Burnside's Lemma.
What are the isometries of the cube?
Well, there's the identity (e).
There's a 90 rotation about a face (r90).
There's a 180 rotation about a face (r180).
There's a 120 rotation about the axis through two two opposite corners
(r120)
There's a 180 rotation about the axis through the midpoints of two
opposite edges (f).

Now, how many ways are there of coloring the cube with n colors, distint
up to one of those isometries?
for e, n^6, since each side can be any color.
for r90, n^3, since two opposite faces can be anything, and the others
have to be the same color.
for r180, n^4, since each pair of opposite faces must be the same color.
for r120, n^2.
for f, n^3.

Now, there's 1 e, 6 r90s (3 pairs of faces, two directions), 3 r180s, 8
r120s (4 pairs of corners, two dirs), and 6 fs.

Burnside's lemma tells us that there are:
1*n^6 + 6*n^3 + 3*n^4 + 8*n^2 + 6*n^3       n^6 + 3n^4 + 12n^3 + 8n^2
-------------------------------------  =    -------------------------
         (1 + 6 + 3 + 8 + 6)                           24

ways of coloring the faces of a cube with n colors.
(it also tells us that for all natural n, n^6+3n^4+12n^3+8n^2 is always
divisible by 24.)
For n=2, we get 10.


Here's another application of Burnside's lemma:
Consider p (prime) beads on a closed string.  How many ways are there of
coloring those beads with a colors?
Well, the identity gives a contribution of a^p.
We can rotate by 1,2. . .,p-1, each giving a ways of coloring the
necklace, so that contributes (p-1)*a.
We can flip the necklace in any of p places, each giving a^((p+1)/2)
ways of coloring, so that contributes p*a^((p+1)/2).
So the total number of ways is
a^p + (p-1)*a + p*a^((p+1)/2)
-----------------------------
             2p

Since this is always an integer, p divides the numberator, and hence,
for all a and primes p, p | (a^p - a), which is Fermat's little theorem.


Joseph wrote:
> 
> Here's a problem:
> 
> Each face of a cube is to be painted either black or white.
> How many ways are there to do this?
> N.B. If the cube can be turned about in some way so as to
> go from one pattern to another, then these are not distinguishable patterns.
> 
> My answer was ten, but I amn't very sure about it.
> 
> Comments, solutions will be appreciated.