In January of this year, Jerry Bryan and I wrote of counting the
number of M-conjugacy classes of Rubik's cube. In the sense that (for
instance) there is really only one position 1 QT from start, even
though that QT may be applied in twelve different ways, this task
amounts to counting the true number of positions of the cube. The
earlier discussion centered on calculations involving computer
analysis of large numbers of positions. However, a look in Paul B.
Yale's book _Geometry and Symmetry_ gave me a clue: the Polya-Burnside
theorem is a tool that allows us to perform this calculation by hand.

The Polya-Burnside theorem describes a relation between a finite group
J and a _representation_ of the group. For our purposes, a represen-
tation is a homomorphism of J into a permutation group, R: J -> S[X].
Here, S[X] refers to the group of all permutations of a set X; the
image of J, called R(J), need not be the whole of S[X], but R(J) will
be a subgroup of S[X]. The _orbits_ of R(J) are the equivalence
classes of X under the relation x~y, said to be true if there is some
permutation p in R(J) for which p(x)=y. The _fixed points_ of a
permutation p in R(J) are the elements x of X for which p(x)=x. The
Polya-Burnside theorem states that the average number of fixed points
of permutations in R(J) is equal to the number of orbits of R(J).
That is,
|R(J)| |Orbits(R(J))| = Sum[p in R(J)] |FixedPoints(p)|.
The average may also be taken over J:
|J| |Orbits(R(J))| = Sum[j in J] |FixedPoints(R(j))|,
a nontrivial distinction, since R may not be one-to-one (though it is
for our application). The Polya-Burnside theorem is not very
inaccessible nor hard to prove, but I will not prove it here.

For our purpose, we take the group J to be M, the 48-element group of
symmetries of the cube. X will be the set of all cube positions,
which we usually call Gx (for GE, GC, or G, depending on whether we
consider edges, corners, or both; we are considering the positions
relative to fixed face centers in all three cases). And the repre-
sentation R is the operation of M-conjugation: (R(m))(g) = m' g m.
Verifying that R is a homomorphism is an exercise in associativity
that Jim Saxe and I carried out in the Symmetry and Local Maxima
paper, in the archives [cube-mail-1, 14 December 1980].

R has been so chosen because we wish to calculate the number of
M-conjugacy classes of Gx, |Gx\Conj(M)|, which is be the number of
orbits of R(M). To apply the Polya-Burnside theorem for this, we need
to calculate, for each element of m of M, the number of fixed points
of R(m). That is the number of elements g of Gx for which m' g m = g.
Multiplying by m, this becomes g m = m g: the fixed points we wish to
count are just those elements g of Gx that commute with m.

There are several tools to make the counting easier. First, I'll note
that just as there are M-conjugacy classes of Gx, there are
M-conjugacy classes of M itself. The number of fixed points of R(m)
is the same for any m in a given conjugacy class. So to calculate the
total number of fixed points over R(M), we need only calculate the
number of g in Gx commuting with each of the ten classes of cube
symmetry and multiply by the size of the class.

The fundamental principle we use in finding whether g commutes with m
can be found by examining the cycles of m. Suppose m permutes a cycle
(c1,c2,...,ck), so that c2=m(c1), c3=m(c2),...,ck=m(c[k-1]),c1=m(ck).
For g to commute with m, we have g(c2)=m(g(c1)), g(c3)=m(g(c2)), ...,
g(ck)=m(g(c[k-1]), and g(c1)=m(g(ck)). So (g(c1),g(c2),...,g(ck)) is
also a cycle of m. Thus g must map each k-cycle of m to another
k-cycle of m, and in the same order. Conversely, if g acts thus on
cycles, then g will commute with m, and so g is a fixed point of R(m).

Suppose that m has j different k-cycles of cubies. There are j! k^j
possibilities for g's action on the cubies in those k-cycles: j!
permutations of cycles, and for each g:(c1,c2,...,ck)->(d1,d2,...,dk),
k choices for g(c1) among {d1,...,dk}. It turns out to be a fairly
easy exercise to show that half of those possibilities are even
permutations and half odd, though the partition by parity is
surprisingly different depending on whether k is even or odd. This
will allow us to combine the results for GE and GC simply by
multiplying together and dividing by two.

Now consider orientation of cubies. This is similar to the case of
permutation, in that the orientation that g imposes on a cubie is a
constant for all cubies in a cycle. I will first discuss the edge
orientation, which is fairly straightforward, and continue to corner
orientation, which has some surprising features.

For edge orientation, if all the cycles have even length, then g's
orientation parity is zero over each cycle, and so zero over the
entire cube. So we can choose the orientation of imposed by c1->g(c1)
for each cycle (c1,...,ck) in 2^j ways. If there are odd-length
cycles, then half of the orientations will have nonzero orientation
parity, and only 2^(j-1) possible orientations can be achieved.

For corners, we might expect there to be 3^(j-1) orientations, except
3^j for cycles of length a multiple of three, and this is often so.
But there are two important exceptions. First, if m is a reflection
(i.e., not a proper rotation in C) then alternate cubies in each cycle
must be given the opposite orientation by g. If the cycle has even
length, this conserves orientation, so there will be 3^j possibili-
ties. If the cycle has odd length, this implies that the orientation
of each cubie must be its own opposite (i.e., zero twist). Thus,
there there is only one possible orientation of the 1-cycles in the
diagonal reflections. The second exception, an even bigger surprise,
occurs when m is either the 120-degree rotation or the 60-degree in-
verted rotation. It turns out that the orientation constraint forbids
any permutation that exchanges the two 1-cycles in these positions.
(This constraint on permutations would throw off the equality between
even and odd permutations, except that these classes of m have other
corner cycles that restore the balance.) The impossibility of m
commuting with an exchange of the two corners can be verified by
examining the possible orientations, but I haven't got any good way of
characterizing when it would be be a problem in general. In fact, I
did not notice it until I investigated discrepancies with the
exhaustive computer analysis.

Using the above analysis, we may carry out the calculation as in the
three tables below. The first two tables count the number of fixed
points of R(m) for an element m of each class, multiply by the class
size, and divide by |J|=48 to get the number of orbits as in the
Polya-Burnside theorem. The third table calculates the number of
fixed points by combining the results of the first two tables, divided
by the class size (which was multiplied in both for edges and for
corners), and divided by 2 (because only half the combined positions
have matching permutation parity).

Counting M-conjugacy classes of the edges of Rubik's cube.

M class            Cycles                     Total F.P.      Numeric
  (class size)      of m     Perms   Oris     in class       Total/48
==============  ===========  ======  ======   ==========  ===========
Identity   (1)  12 1-cycles  12!     2^12/2   12! 2^11    20437401600

Axis Rot/2 (3)   6 2-cycles  6! 2^6  2^6      6! 3 2^12        184320

Rot/3      (8)   4 3-cycles  4! 3^4  2^4/2    4! 3^4 2^6         2592

Diag Rot/2 (6)   5 2-cycles  5! 2^5  2^5
                 2 1-cycles  2       2^2/2    5! 3 2^13         61440

Rot/4      (6)   3 4-cycles  3! 4^3  2^3      3! 3 2^10           384

Inv Rot/4  (6)   3 4-cycles  3! 4^3  2^3      3! 3 2^10           384

Diag Ref   (6)   5 2-cycles  5! 2^5  2^5
                 2 1-cycles  2       2^2/2    5! 3 2^13         61440

Inv Rot/6  (8)   2 6-cycles  2! 6^2  2^2      2! 3^2 2^7           48

Axis Ref   (3)   4 2-cycles  4! 2^4  2^4  
                 4 1-cycles  4!      2^4/2    4! 3^2 2^14       73728

Inversion  (1)   6 2-cycles  6! 2^6  2^6      6! 2^12           61440
                                                          -----------
                                        | GE\Conj(M) | =  20437847376

Counting M-conjugacy classes of the corners of Rubik's cube.

M class            Cycles                   Total F.P.    Numeric
  (class size)      of m     Perms   Oris   in class     Total/48
===============  ==========  ======  =====  ===========   =======
Identity   (1)   8 1-cycles  8!      3^8/3  8! 3^7        1837080

Axis Rot/2 (3)   4 2-cycles  4! 2^4  3^4/3  4! 3^4 2^4        648

Rot/3      (8)   2 3-cycles  2! 3^2  3^2  
                 2 1-cycles  1       3^2/3  3^5 2^4            81

Diag Rot/2 (6)   4 2-cycles  4! 2^4  3^4/3  4! 3^4 2^5       1296

Rot/4      (6)   2 4-cycles  2! 4^2  3^2/3  3^2 2^6            12

Inv Rot/4  (6)   2 4-cycles  2! 4^2  3^2    3^3 2^6            36

Diag Ref   (6)   2 2-cycles  2! 2^2  3^2
                 4 1-cycles  4!      1      4! 3^3 2^4        216

Inv Rot/6  (8)   1 6-cycle   6       3
                 1 2-cycle   1       3      3^3 2^4             9

Axis Ref   (3)   4 2-cycles  4! 2^4  3^4    4! 3^5 2^4       1944

Inversion  (1)   4 2-cycles  4! 2^4  3^4    4! 3^4 2^4        648
                                                          -------
                                        | GC\Conj(M) | =  1841970

Counting M-conjugacy classes of the entire Rubik's cube

M class             Edge         Corner       Corner times edge
  (class size)      F.P.          F.P.             / (96*class size)
===============  ==========     =========    =======================
Identity   (1)   12! 2^11       8! 3^7       901,083,401,551,872,000

Axis Rot/2 (3)    6! 3 2^12     4! 3^4 2^4               955,514,880

Rot/3      (8)    4! 3^4 2^6    3^5 2^4                      629,856

Diag Rot/2 (6)    5! 3 2^13     4! 3^4 2^5               318,504,960

Rot/4      (6)    3! 3 2^10     3^2 2^6                       18,432

Inv Rot/4  (6)    3! 3 2^10     3^3 2^6                       55,296

Diag Ref   (6)    5! 3 2^13     4! 3^3 2^4                53,084,160

Inv Rot/6  (8)    2! 3^2 2^7    3^3 2^4                        1,296

Axis Ref   (3)    4! 3^2 2^14   4! 3^5 2^4             1,146,617,856

Inversion  (1)    6! 2^12       4! 3^4 2^4               955,514,880
                                             -----------------------
                             | G\Conj(M) | = 901,083,404,981,813,616

These results have been corroborated and expanded by use of
combinatorial computer programs, to be described in a later message.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil