Associated Topics || Dr. Math Home || Search Dr. Math

### Color Arrangements on the Face of a Cube

```Date: 11/23/2001 at 12:51:14
From: Jhonen
Subject: Color Arrangements on the Face of a Cube

Dear Dr. Math,

I've heard the familiar problem about whether or not it is possible to
use 3, 4, etc. colors to paint the faces of a cube such that no face
painted one color is adjacent to another face of the same color.
Here's another problem in the same vein which I'm not sure how to
approach other than by trying to write out every possible combination:

Suppose you have three colors in which to paint the face of a cube,
either red, blue, or yellow. How many different color patterns are
there if each face of the cube must be painted red, blue, or yellow
(assuming that two patterns are the same if the two cubes painted
with them can be made to look the same by simply rotating one or the
other. E.g. there is only one pattern of say, five red faces and one
yellow).

It seems that there must be patterns of only one color, and six more
of five of the same colors and one different one. Further, it seems as
if there are two possibilities for the case of four sides of the same
color and two sides of one different color, two possibilities for
three sides of one color, and three of another. It seems that if one
allows cubes of only two colors, that there are: 8*2*3 = 48 different
possible color patterns.

Is there a better way to approach this problem, and how can the
conditions stated in the problem, which allow for each cube to have a
color pattern of up to three colors, be dealt with?

Sincerely,
Jhonen

```

```Date: 11/23/2001 at 18:31:48
From: Doctor Anthony
Subject: Re: Color Arrangements on the Face of a Cube

This is a problem requiring the use of Burnside's lemma. You consider
the 24 symmetries of a cube and sum all those symmetries that keep
colours fixed. The number of non-equivalent configurations is then the
total sum divided by the order of the group (24 in this case).

We first find the cycle index of the group of FACE permutations
induced by the rotational symmetries of the cube.

Looking down on the cube, label the top face 1, the bottom face 2 and
the side faces 3, 4, 5, 6 (clockwise).

You should hold a cube and follow the way the cycle index is
calculated as described below. The notation (1)(23)(456) =
(x1)(x2)(x3) means that we have a permutation of 3 disjoint cycles
in which face 1 remains fixed, face 2 moves to face 3 and 3 moves to
face 2, face 4 moves to 5, 5 moves to 6, and 6 moves to 4. (This is
not a possible permutation for our cube, it is just to illustrate the
notation.) We now calculate the cycle index.

(1) e = (1)(2)(3)(4)(5)(6);  index = (x1)^6
(2) 3 permutations like (1)(2)(35)(46); index 3(x1)^2.(x2)^2
(3) 3 permutations like (1)(2)(3456); index 3(x1)^2.(x4)
(4) 3 further as above but counterclockwise; index 3(x1)^2.(x4)
(5) 6 permutations like (15)(23)(46); index 6(x2)^3
(6) 4 permutations like (154)(236); net index 4(x3)^2
(7) 4 further as above but counterclockwise; net index 4(x3)^2

Then the cycle index is

P[x1,x2,...x6] =(1/24)[x1^6 + 3x1^2.x2^2 + 6x2^3 + 6x1^2.x4 + 8x3^2]

and the pattern inventory for these configurations is given by the
generating function:

(I shall use r = red, b = blue, y = yellow as the three colours.)

f(r,b,y) = (1/24)[(r+b+y)^6 + 3(r+b+y)^2.(r^2+b^2+y^2)^2
+ 6(r^2+b^2+y^2)^3 + 6(r+b+y)^2.(r^4+b^4+y^4)
+ 8(r^3+b^3+y^3)^2]

and putting r = 1, b = 1, y = 1 this gives

= (1/24)[3^6 + 3(3^2)(3^2) + 6(3^3) + 6(3^2)(3) + 8(3^2)]

= (1/24)[729 + 243 + 162 + 162 + 72]

= 1368/24

= 57

So there are 57 non-equivalent configurations.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/

```

```Date: 09/29/2008 at 18:40:06
From: Gopal
Subject: Distinct colored cubes

I read your article on painting the faces of a cube but I couldn't
understand how it was done.  Can we somehow use a combination formula
to do it?

I started with six of the same color, than five of the same color,
then four of same color and so on.  As I moved down the chain I kept
record of the number of distinct cubes.  So with all the same color
there are 3 distinct cubes.  With five the same color there are 6
distinct possibilities.  I got stuck when I had three of the same
color painted.

```

```Date: 09/30/2008 at 05:48:40
From: Doctor Jacques
Subject: Re: Distinct colored cubes

Hi Gopal,

The solution of this problem requires the use of a theorem of
Burnside; that theorem is part of a discipline known as group
theory.  I don't know if you are familiar with group theory: I will
give you the practical method of computing the result, and some kind
of "plausibility argument" to show you why it works (this is not a
proof).  If you know some group theory and want the actual proof,

To illustrate the problem, I will start with a simpler version. We
will consider a board of 4 squares:

+---+---+
| 1 | 2 |
+---+---+
| 3 | 4 |
+---+---+

and try to count the number of possible ways of coloring the 4
squares in two colors, say black and white, where two colorings are
considered the same if they can be obtained from each other by a
symmetry of the whole square.

If we ignore symmetries, we can color the square in 2^4 = 16 ways,
because each of the 4 squares can be colored in two ways.  (If we had
k colors available, there would be k^4 possible colorings).  This
means that, if we take symmetries into account, we can only reduce
that number.

The first step is to define precisely what are the symmetries, or
operations, we want to consider.  Those are the permutations of the 4
squares that correspond to a physical movement of the board
(rotation or flipping).  Let us enumerate them.

We have the permutation that does nothing, i.e., that leaves every
square in its place.  We will denote that operation by I (for
Identity).  You might wonder why we bother to include it; I will come
to that later.

Next, we have the rotations by 90° in either direction.  We will call
those R (for Right) and L (for Left).  For example, R corresponds to
the permutation:

1 -> 2 -> 4 -> 3 -> 1

which is usually written as (1243).

We have the reflections across the horizontal and vertical medians,
we will call these H and V.  We have:

H = (13)(24)
V = (12)(34)

We have the reflections across the diagonals, we will call these U
and D, with:

U = (14)(2)(3)
D = (1)(23)(4)

(This means, for example, that D leaves 1 and 4 fixed, and
interchanges 2 and 3)

Finally, we have the rotation by 180°, which we call C:

C = (14)(23)

In total, we have 8 operations: I, R, L, H, V, U, D, C.

This set of operations (we will call it G) has some interesting
properties:

If A and B are two operations, then, by executing A followed by B
(we will call that operation AB), we get another operation of the
set.  This is a requirement for symmetries, because if neither A and
B changes the color of any square, then the same must be true for
AB.  For example, if we execute H followed by V, the squares move as
follows:

Initial position    1  2  3  4
After H             3  4  1  2
After HV            4  3  2  1

This means that HV sends 1 to 4, 2 to 3, 3 to 2, and 4 to 1; we can
write this as (14)(23), which is the same as C.

Now, if, for example, we execute H twice, then each square goes back
to its initial position, which is the operation we denoted by I (the
one that does nothing).  This explains why we need to include I in
our set.  Note that we would write I as (1)(2)(3)(4).

This set of operations is an example of what is called a group (in
general, a group needs to satisfy additional requirements, but these
are always satisfied for sets of permutations of a finite set).

After these preliminaries, we can go back to the problem of counting
the colorings of the square.  We want to count the number of distinct
colorings of the square, in such a way that two colorings are
considered the same if there is some operation in G that transforms
one into the other.  In other words, we want to partition the
2^4 = 16 colorings into sets (called orbits) in such a way that two
colorings belong to the same orbit if there is an operation in G
that sends one to the other.  We are interested in the number of
orbits.

The intuitive approach is to count separately the number of distinct
colorings invariant for each operation of G, and to take the
average.  Burnside's theorem essentially says that this gives the
right result; as I said before, if you know some group theory and
want to discuss this further, please write back.

I = (1)(2)(3)(4).  In this case, all 16 colorings are invariant under
I (because I moves nothing), and we have 16 distinct colorings.

For the operation R = (1243), as soon as we choose a color for
square 1, all the colors of the other squares are fixed.  Indeed, R
sends square 1 to square 2, which must therefore have the same color
as square 1.  In the same way, square 2 is sent to square 3, and, by
continuing the argument, we see that all the squares must have the
same color.  This means that there are only two possibilities,
depending on the color we choose for square 1 : those are the
colorings where all the squares have the same color.

For the operation H = (13)(24), we can freely choose the colors for
squares 1 and 2, and this forces the colors of squares 3 (=1) and 4
(=2).  This means that we have 2^2 = 4 distinct colorings invariant
under H.

At this point, we can see a pattern emerging.  For example, H is
written as (13)(24), i.e., as 2 cycles.  This means that the sets
{1,3} and {2,4} are separately invariant under H: each element of
one of these sets (cycles) is sent by H to another element of the
same cycle.  This implies that elements of each cycle must have the
same color; once you select a color for one element, the colors of
the other elements of the set are fixed.  You can only choose colors
for one element of each cycle, and the number of colorings invariant
under the operation is 2^t, where t is the number of cycles.  Note
that you must write down all the cycles, including those of 1
element, like we did for I (in that case, there were 4 cycles, and
the number of colorings was 2^4).

We should do this for all the operations in G.  However, we can
simplify the problem a little, by noting that some operations, like
H and V, or D and U, are "similar" in a sense that should be made
precise.  The important point is that similar operations have the
same number of cycles, and will therefore yield the same number of
colorings.  We can therefore compute the number of colorings for one
set of each class of similar operations, and multiply by the number
of operations in the class.  This gives the following table:

Operations  N  t  2^t  N*2^t
I           1  4   16     16
L,R         2  1    2      4
H,V         2  2    4      8
U,D         2  3    8     16
C           1  2    4      4
----------------------------
Total       8             48

In this table, N is the number of operations in each class, t is the
number of cycles in each operation, 2^t is the number of distinct
colorings for that operation, and N*2^t is the total number of
colorings to take into account for the class.

As I said before, the answer to the problem is the average of all
the distinct colorings.  As there are 8 operations, this average is
48/8 = 6 : there are 6 distinct colorings of the square.  Using the
order [1,2,3,4], these colorings are:

BBBB, WWWW, BBWW, BWWB, BWWW, WBBB

In this case, it would have been easy to obtain those colorings by
inspection.

If we had k colors instead of 2, we could repeat the same argument.
However, in this case, there would be k possible choices for each
square, and we would have to replace 2^t by k^t in the above table.
This would give the number of colorings as:

(k^4 + 2k^3 + 3k^2 + 2k)/8

This shows, for example, that, with 3 colors, there are 21 distinct
colorings (this would already be harder to obtain by inspection).

Now, we can use the same argument for the colorings of a cube with k

colors.  In this case, there are 24 operations, which are listed,
with their cycle structure, in the article you refer to.

We can make a similar table.  In this case, the second column will
contain an example of cycle structure for each class.

Class  Structure               N  t  N*k^t
1      (1)(2)(3)(4)(5)(6)      1  6  k^6
2      (1)(2)(35)(46)          3  4  3k^4
3      (1)(2)(3456)            3  3  3k^3
4      (1)(2)(3654)            3  3  3k^3
5      (15)(23)(46)            6  3  6k^3
6      (154)(236)              4  2  4k^2
7      (145)(263)              4  2  4k^2
-----------------------------------------
Total                         24     k^6+3k^4+12k^3+8k^2

The operations are as follows:

* Class 1 only contains the identity.

* Class 2 contains the rotations of 180° through an axis going
through the centers of two opposite faces.

* Classes 3 and 4 contain rotations of 90° through the same axes.

* Class 5 contains rotations of 180° through the line joining the
midpoints of two opposite edges.

* Classes 6 and 7 contains rotations of 120° through an axis joining
two opposite vertices.

This gives the total number of distinct colorings as:

(k^6+3k^4+12k^3+8k^2)/24

In the particular case of 3 colors (k=3), we get 57 colorings.

Please feel free to write back if you require further assistance.

- Doctor Jacques,  The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search