# How many disconnected graphs of the Rubik's cube exist?

Let us say that a Rubik's cube in a particular configuration is in a particular "state". All other configurations of this cube (other "states"), which can be achieved by rotations of the cube can be thought to be connected to each other... rotations are like walking the edges of the graph where the different states are the vertices.

Now, if our Rubik's cube is of the type where we can peel off the stickers easily and put them back too, then we can swap 2 of the stickers in a corner.

I understand that the cube cannot be solved any more. Our cube has moved to a new state which is disconnected from the previous graph built above. Also, all the states reachable from this new state are also disconnected from the other graph. (otherwise the cube would be solvable). So now we have 2 graphs which are disconnected from each other. A third set of states might be disconnected from both the above states.

For all possible reasonable color assignments ( by reasonable, I mean to preserve the number of tiles for each color=9), how many such disconnected graphs exist for a 3x3x3 Rubik's cube?

• For the related problem where you can move around the subcubes arbitrarily but can't peel off stickers, the answer is 12. The answer is surely much larger for your question, because you're allowing me to combine the stickers in arbitrary ways. – Michael Lugo Oct 1 '10 at 15:48

You can calculate this using Burnside's Lemma, http://en.wikipedia.org/wiki/Burnside%27s_lemma, once you know the group of transformations for Rubik's cube.

All connected components are isomorphic groups, so you can consider them as equivalence classes of the same size.

Now we know the size of one of the classes (i.e. the one containing the solved cube). From wikipedia:

$$|N_1| = 8! \times 3^7 \times \frac{12!}{2} \times 2^{11}$$

Let $|states|$ be the total number of states you consider. Then the number of equivalence classes or connected components is:

$$\frac{|states|}{|N_1|}$$

First, if you only consider the cases where you can move individual litle cubes, then the number of states is: $$|states_1| = 8! \times 3^8 \times 12! \times 2^{12}$$ And hence $$\frac{|states_1|}{|N_1|} = 3 \times 2 \times 2 = 12$$

In your case, where you allow stickers to be moved around, The number of states is much higher. I think it's computed by the following:

$$|states_2| = \frac{\text{total permutations}}{\text{cube rotational symetries}} = \frac{6! \times 24! \times 24! }{24}$$

$$\frac{|states_2|}{|N_1|} = \frac {6! \times 24! \times 23! } {8! \times 3^7 \times 12! \times 2^{12}}$$
• MathJax hint: for multicharacter exponents, put them in braces, so 2^{11} gives $2^{11}$ instead of 2^11 which gives $2^11$. – Ross Millikan Nov 28 '17 at 16:19