Newsgroups: rec.puzzles
From: haoyuep@aol.com (Dan Hoey)
Date: 16 Nov 2001 13:40:17 GMT
Subject: Re: Painting a cube

Nick Wedd n...@maproom.co.uk writes:
[a very nice case analysis of painting a cube with three colors].

But earlier, you wrote:
> >What about if you have n colors, instead of three?

> 27*Cn,2 + 30*Cn,3 + 80*Cn,4 + 60*Cn,5 + 30*Cn,6
> or, if mirror images are considered the same,
> 27*Cn,2 + 29*Cn,3 + 52*Cn,4 + 30*Cn,5 + 15*Cn,6

That doesn't even agree with the three-color case, though
maybe you meant 9Cn,2. But that's still wrong, and there
are 3 other errors.

I'll give you my analysis (with no gratutitous whitespace*).

The answer as a polynomial is almost immediate from the
Cauchy-Frobenius aka Polya-(not)Burnside theorem.  For
each of the 24 rotations of the cube (or the 48 rotations
and reflections) each cycle of faces must be monochrome,
so it contributes  n^c/|G|  where n is the number of colors,
c is the number of cycles, and |G| is the size of the group (24 or 48).
So we add up

representative       number of    contribution   contribution
rotation/           equivalents   counting       including
reflection         (conjugates)   rotations      reflections

(B)(F)(T)(D)(L)(R)      1            n^6/24          n^6/48
(B,F)(T,D)(L)(R)        3          3 n^4/24        3 n^4/48
(B,T,L)(F,D,R)          8          8 n^2/24        8 n^2/48
(B,F)(T,L)(D,R)         6          6 n^3/24        6 n^3/48
(B,T,F,D)(L)(R)         6          6 n^3/24        6 n^3/48
(B,F)(T,D)(L,R)         1                            n^3/48
(B,F)(T)(D)(L)(R)       3                          3 n^5/48
(B,T,L,F,D,R)           8                          8 n  /48
(B,T)(F,D)(L)(R)        6                          6 n^4/48
(B,T,F,D)(L)(R)         6                          6 n^6/48

so there are (n^6 + 3n^4 + 12n^3 + 8n^2)/24 paintings up to
rotation, or (n^6 + 3n^5 + 9n^4 + 13n^3 + 14n^2 + 8n)/48 up
to rotations and reflections.

Converting to binomial coefficents may be done by dividing
out by their polynomial representations

  Cn,1 = n
  Cn,2 = (n^2 - n)/2
  Cn,3 = (n^3 - 3n^2 + 2n)/6
  Cn,4 = (n^4 - 6n^3 + 11n^2 - 6n)/24
  Cn,5 = (n^5 - 10n^4 + 35n^3 - 50n^2 + 24n)/120
  Cn,6 = (n^6 - 15n^5 + 85n^4 - 225n^3 + 274n^2 - 120n)/720

to get
  30Cn,6 + 75Cn,5 + 68Cn,4 + 30Cn,3 + 8Cn,2 + Cn,1
counting only rotations, or
  15Cn,6 + 45Cn,5 + 52Cn,4 + 29Cn,3 + 8Cn,2 + Cn,1
including reflection.

Alternatively, we can generalize your case analysis:

Color counts   subcase    arrangements (rot or rot+ref)

6                           Cn,1

5 1                        2Cn,2
4 2            ad          2Cn,2
4 2            op          2Cn,2
3 3            clump        Cn,2
3 3            strip        Cn,2

4 1 1          ad          3Cn,3
4 1 1          op          3Cn,3
3 2 1          clump       6Cn,3
3 2 1          1 midstrip  6Cn,3
3 2 1          1 end strip 6Cn,3
2 2 2          op op op     Cn,3
2 2 2          op ad ad    3Cn,3
2 2 2          ad ad ad    2Cn,3 or Cn,3

3 1 1 1        clump       8Cn,4 or 4Cn,4
3 1 1 1        strip      12Cn,4
2 2 1 1        op op op    6Cn,4
2 2 1 1        op ad ad   12Cn,4
2 2 1 1        ad ad op    6Cn,4
2 2 1 1     ad ad ad   24Cn,4 or 12Cn,4

2 1 1 1 1   op         15Cn,5
2 1 1 1 1   ad         60Cn,5 or 30Cn,5

1 1 1 1 1 1            30Cn,6 or 15Cn,6

which yields the same result.

Dan Hoey                        Posted and -emailed
haoyuep@aol.com                 * Why? Because I think it's silly.