# Rubik's cube and counting

Inspired by this question, I formulate the following:

Suppose I have a $3\times3\times3$ Rubik's cube, call each small square on the surface a piece, there are then $3*3*6 = 54$ pieces. Enumerate the 54 pieces by $[54]:=\{1,2,\cdots,54\}$. Given a permutation $\sigma$ of $[54]$, for every $k\in [54]$ we replace the piece numbered by $k$ with the piece numbered by $\sigma(k)$.

Question: Consider the set of all permutations of $[54]$ and their corresponding coloring of the cube, how many different Rubik's cube colorings can I get? Two colorings are different if they cannot be obtained from another by any sequence of legal Rubik's cube movement.

I plan to tackle the question by Burnside's Lemma, and essentially count the number of orbits in the motion group of Rubik's cube.

Further question Is there a closed form formula for number of orbits under Rubik's motion group for a $n\times n\times n$ Rubik's cube?

Let $\Pi$ be the space of colorings and fix an element $\pi\in\Pi$. There is a set-theoretic isomorphism given by $S_{54}\to\Pi:\sigma\mapsto\sigma(\pi)$. Thus we can consider the rubik's cube action as taking place on the symmetric group. In particular, we have an embedding $R\hookrightarrow S_{54}$ when we view $\pi$ as the standard configuration of the cube. The action of $R$ on $S_{54}$ is given by left multiplication.

When a subgroup $H\le G$ acts on $G$ by left multiplication, the orbits are of the form $Hg$, so we actually are looking at the right coset space $G/H$. The number of orbits is then $|G/H|$.

Therefore the number of colorings modulo rubics cube actions is

$$\frac{54!}{43252003274489856000}=5337179318013082492954222792315582522933248000000000.$$

I would personally avoid Burnside's lemma for this type of problem, where a direct computation is perfectly feasible while the group's structure (and therefore its fixed point sets) are more difficult to characterize than the original coset space's size.

• This seems to be assuming that all of the 54 stickers can be distinguished. On a standard cube there are 6 groups of 9 indistinguishable stickers, which complicates the counting quite a bit. Also, the divisor of 43252003274489856000 doesn't account for the possibility of turning the entire cube on its side (which usually is not relevant because the center colors determine how it has been turned, but this is not necessarily the case for a restickered cube). – Henning Makholm Mar 18 '13 at 22:47
• @HenningMakholm Indeed, the numbers 1-54 are distinct in the OP's problem so this is different from a usual cube situation. I am not sure what you mean by turning the entire cube on its side being unaccounted for in the denominator - isn't this easily obtainable through legal cube moves (namely, three twists around the axis of turning)? – anon Mar 18 '13 at 22:56
• No, 43252003274489856000 is the number of movements that leave the 6 center faces fixed in space. However, for example, one of the 54! restickerings can be achieved by turning the entire cube upside down -- which is not an operation that's counted among the 43252003274489856000 -- but even considering the 54 stickers distinct, we probably wouldn't think that's a "different cube coloring". – Henning Makholm Mar 18 '13 at 23:00
• Ah, you are right. The cube group fixes all of the center faces - I did not realize this. – anon Mar 18 '13 at 23:06
• @mezhang: Stangely enough, MSE doesn't seem to have a question explicitly addressing the number 43252003274489856000. However, it only takes basic combinatorics to see that if we take the cube apart (not removing the stickers, just the 20 moveable cubies) there's $12!\cdot 8!\cdot 2^{12}\cdot 3^8$ different positions we can put it back together in, and we do have a question explaining that exactly one twelfth of those can be reached by legal moves. So the large number is $$\frac{12!\cdot 8!\cdot 2^{12}\cdot 3^8}{12}$$ – Henning Makholm Mar 22 '13 at 10:15