## Coloring a Cube

1. Coloring each face a solid color and using each of N colors (N=2,3,4,5,6) at least once, in how many ways can you color a cube, such that a duplicate cannot be found simply by rotating the cube?
2. Using each of N colors at least once (N=2,3,4), in how many ways can you color a tetrahedron?
The "Using each of N colors at least once" in the problem statements helps to limit the number of solutions. Can you solve them if that phrase is changed to "Using N colors"?

Source: Several sources.

Solutions were received from Al Zimmermann and Joseph DeVincentis. Their answers differ. I include them both here for anyone to prove or disprove. [I admit I know some of the numbers are correct, but I have not fully solved the problem so do not yet have my own solutions to compare. -KD]

Update 12/20/00: Gerd Baron sent the following analysis:

```If you follow this idea from Joseph DeVincentis:
For "Using N colors" instead of "Using each of N colors at least once",
the result is the sum for k=1,...,N of the solutions above multiplied
by the number of ways to choose a set of k colors from N colors.
(Note that there is 1 way to color a shape with 1 color.)

(Note that for k greater than 6 the summand is 0; Therefore only summing
over k=1,2,3,4,5,6 for the cube and over k=1,2,3,4 for the tetrahedron)

with the correct values from Al Zimmermann: (1,8,30,68,75,30 for the
cube and 1,3,3,2 for the tetrahedron)

and calculate it for general N, You will get for the cube
n^2(n^3+3n^2+12n+8)/24 and for the tetraedron n^2(n^2+11)/12.
The same results You get by using Polya's theorem of counting with the
group of rotations for the cube or the tetrahedron, respectively.
I used this way and got at first these general formulas and counted back
to the values for using each of the N colors at least once.
```

Update 1/9/00: Al Zimmermann sent these diagrams as additional proof of his solution: Four Color Cube, Five Color Cube. His explanation of them:

```I've created a justification for my statement that there are 68 (or 75)
distinct ways to color the faces of a cube using each of 4 (or 5) colors at
least once.

Label the faces of the cube with the integers from 1 to 6 as in the following
unfolded cube:
+---+
| 2 |
+---+---+---+---+
| 3 | 6 | 5 | 1 |
+---+---+---+---+
| 4 |
+---+

Assign letters to each of six different colors, as follows:
B = blue
C = cyan
G = green
M = magenta
R = red
Y = yellow

Now any coloring of the cube can be represented as a 6-letter string, where
the i-th letter represents the color of the i-th face.  For example, the
string RRRGRR represents the coloring where face 4 is green and all the
others are red.

To represent an entire class of equivalent colorings (that is, those which
can be derived from each other by rotation) order the representations of the
equivalent colorings alphabetically and choose the first.  For example, to
represent the class of colorings consisting of one green face and five red
faces use GRRRRR.
```

From Al Zimmermann:
```Let C(n,k) be the number of ways of choosing k colors from among n.  That is,
C(n,k) = n!/(k!(n-k)!).

Let F(n) be the number of distinct ways you can color a cube using each of n
colors at least once.  Let F'(n) be the number of distinct ways you can color
a cube using n colors.

Define D(n) and D'(n) analogously for tetrahedra.

Then
n
F'(n) = SUM C(n,i) * F(i)
i=1
and
n
D'(n) = SUM C(n,i) * D(i).
i=1

The following values for F(n) were determined by computer.  Those for D(n)
came from old fashioned cogitation.  The values for F'(n) and D'(n) were
derived from those of F(n) and D(n), respectively, using the above formulae.

n     F(n)     F'(n)     D(n)     D'(n)
---------------------------------------
1       1         1        1         1
2       8        10        3         5
3      30        57        3        15
4      68       240        2        36
5      75       800        0        75
6      30      2226
7       0      5390
```
And from Joseph DeVincentis:
```For the first problem, on the cube, I found:
8 colorings with 2 colors
30 colorings with 3 colors
56 colorings with 4 colors
45 colorings with 5 colors
30 colorings with 6 colors

For the tetrahedron, I found:
3 colorings with 2 colors
3 colorings with 3 colors
2 colorings with 4 colors

For "Using N colors" instead of "Using each of N colors at least once",
the result is the sum for k=1,...,N of the solutions above multiplied
by the number of ways to choose a set of k colors from N colors.
(Note that there is 1 way to color a shape with 1 color.)

So, for the cube:
2 colors: 1*2 + 8*1 = 10
3 colors: 1*3 + 8*3 + 30*1 = 57
4 colors: 1*4 + 8*6 + 30*4 + 56*1 = 228
5 colors: 1*5 + 8*10 + 30*10 + 56*5 + 45*1 = 710
6 colors: 1*6 + 8*15 + 30*20 + 56*15 + 45*6 + 30*1 = 1866

For the tetrahedron:
2 colors: 1*2 + 3*1 = 5
3 colors: 1*3 + 3*3 + 3*1 = 15
4 colors: 1*4 + 3*6 + 3*6 + 2*1 = 42
```

Mail to Ken