Source: Several sources.
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.
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