Combinatorics – Rubik’s Cube and Counting

combinatoricsdiscrete mathematicsrubiks-cube

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?

Best Answer

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.