Proof of the number of combinations to the n x n x n cube

PROVE THAT THE ORIENTATION AND PERMUTATION OF PIECES WITHIN THE SAME ORBIT ARE INDEPENDENT OF EACH OTHER
Proof of the number of combinations to an n x n x n Rubik's Cube

First of all I want to mention that I am not the first person to come up with this formula, I know that several other people have also discovered it. I had even seen it before trying to prove it myself. However, on this page I'm going to attempt to give as rigorous a proof as I know how that the above expression is exactly the number of combinations to the n x n x n Rubik's Cube. This is my first attempt at trying to actually write out a rigorous proof relating to the cube, so bear with me. I've just seen enough faulty logic on the internet about larger cubes that I felt I should write this proof to help clear things up.

First note that an n x n x n Rubik's cube consists of 6n²-12n+8 individual pieces, not 6n² stickers. Also note that not not all of these pieces can occupy just any position, for example you couldn't have a corner piece occupying the position of a center piece.

Defintions:

1) Let an orbit be defined as the set of all positions that a certain type of piece may occupy. For the example the corner piece orbit consits of 8 locations, namely the 8 corners of the cube.

2) Define the concept of parity within an orbit as follows: The parity of an orbit is even if the permutation of the pieces in that orbit is even, meaning that you could place each piece in it's correct location using an even number of transpositions. The parity of an orbit is odd if the permutation of the pieces is odd, meaning that it would require an odd number of transpositions to place all the pieces back into their correct locations. Note that the concept of parity doesn't make sense, and is undefined, for all center piece orbits on any n x n x n cube. This is due to the fact that center pieces of the same color are indistinguishable from each other.

3) Whenever I mention the "n x n x n cube" I mean only the cube where center pieces in the same orbit and of the same color are indistinguishable from each other. I will soon write a proof for my supercube formula as well, in which this won't be the case.

Proof:

In order to make the explanation easier we will first assume that n is an even number. Therefore we only seek to examine the number of combinations to the 2x2x2, 4x4x4, 6x6x6, etc.. sized cubes. In order to avoid overcounting positions we have to define a reference point around which we are to base the solved state. Given any scrambled even degree cube, the reference for what the solved state should look like will be the FUL corner. By saying that this corner is a reference, I mean that it is defined to be in the correct location, and have the correct orientation. This helps to eliminate possible overcounts by not taking into account the 24 rotational symmetries of a cube.

Now we are going to scramble our even degree n x n x n cube. Let us start with the smallest portion of this task, and assign to the corners their possible permutations and orientations. In order to rigorously prove some of the statements I will be saying I need to prove the following lemma, the sum of the number of clockwise twists on each corner is congruent to 0 (mod 3).

----------------
Lemma 1:
This can be assumed using group theory, however I have only had an introdcutory modern algebra course, and I cannot recall how to do this using group theory. Therefore for completeness here is my proof of this lemma using simply the properties of the n x n x n cube.
----------------

I also have to prove one more lemma in order to allow us to permute the pieces of our cube. I claim that on the even degree n x n x n cube the parity of every orbit is independent of all the other orbits. Again note that the concept of even or odd parity does not exist for the center orbits on any even n x n x n cube.

----------------
Lemma 2:
This can also be proved using permutation groups and group theory, however I have only seen an introduction to that subject and do not feel confident enough to be able to rigorously prove it for the n x n x n cube. Therefore here is my proof of this using the concept of number of transpositions needed to solve the pieces in each orbit.
----------------

Now we are ready to permute and rotate the corners of our even degree n x n x n cube into all of their possible locations. Remember that we defined the FUL corner to already be in the solved position, to make sure we don't overcount due to the 24 rotational symmetries of the cube. Now we must permute and orient the remaining 7 corners. As we have seen from lemma #2 the corner orbit can have either odd or even parity wholly independent of the parity of the rest of the pieces. Therefore we can permute the corners into either an odd or even permutation without creating an illegal position. So let the remaining corners permute into their total 7! possible combinations. For the orientations we have already defined the corner FUL to be correctly oriented, so we must choose the orientations of the remaining 7 corners. As we saw from lemma #1 the sum of the number of clockwise twists on the corners must be congruent to 0 (mod 3). Let us orient 6 of the remaining corners into all of their 3⁶ total orientations. As we can see, the orientation of the last corner has no freedom and must be decided. This must be done to ensure that the sum of the number of clockwise twists on the corners is congruent to 0 (mod 3). Therefore the corners have a total of 7!*3⁶ total possible positions.

Now, using lemma #2 again, we can permute all the edges in each of the (n-2)/2 edge orbits into all of their allowable positions. This is because the parity of each edge orbit is independent of the rest of the cube. Therefore each edge orbit has 24! total positions, and there are (n-2)/2 edge orbits, therefore there are 24!^(n-2)/2 total positions for all of the edge pieces.

Finally we must concentrate on permuting the center pieces, and this will finish off with the number of combinations to the even n x n x n cube. Note that there are (n-2)²/4 center piece orbits. Remember also that the 24 center pieces in an orbit can be broken up into 6 groups of 4 identically colored pieces. Note that you can appear to switch only two pieces in an orbit by performing the even permutation of a 3-cycle on two pieces of the same color and one piece of another color. This will appear to perform a transposition, however it is in effect an even permutation complicated by the fact that some of the center pieces are indistinguishable from the rest. Therefore for each center piece orbit, you can permute all 24 pieces into all of their 24! possible positions, and then divide out the 4! possible permutations for each of the 6 groups of 4 pieces in that orbit. Therefore if it can be proved that the permutations of the center pieces is independent of the corners and edges then the centers could be in 24!^(n-2)²/4/(4!^6*(n-2)²/4).

For a proof of the necessary proposition see below:

----------------
Lemma 3:
Proof of the proposition that the permutation within each center orbit is independent of all the other orbits of the cube due to the fact that certain groups of pieces in each orbit are indistinguishable from each other.
----------------

Now that we know that the permutations of each center orbit is independent of all the other orbits we can now permute the centers within their orbits without worrying about creating an illegal position. Each orbit will then have 24!/4!⁶ possible positions to account for the indistinguishability of the 6 groups of 4 centers that are indistinguishable from each other. There are (n-2)²/4 center orbits to the even n x n x n cube, so the total number of positions the centers can be in is
24!^(n-2)²/4/4!^6*(n-2)²/4

Finally if we combine all our terms, we have the exact number of combinations to the even n x n x n cube:

Now all we need is a formula for the number of combinations to the odd n x n x n cube.

Now we need to use this same process to find the number of combinations to the n x n x n cube when n is odd. One thing to notice about an odd degree cube is that it will have a set center piece in the very middle of each face, whereas an even cube does not have this. Therefore for all our odd degree n x n x n cubes we will define the center pieces of each face to be the reference point for what describes the solved state. By this we imply that turning a central most layer would really be turning all the (n-1) parallel layers, rather than turning the central most layer.

Similar to the even degree cube we are going to permute the pieces orbit by orbit until we are finished, making sure to not overcount any positions due to symmetry or allow impossible positions.

The first thing we will do is to prove how the corner orbit and the central most edge piece orbit relate to each other. This will allow us to permute the corners and edges. Afterward we will examine how these orbits relate to the other orbits, so that we can continue to permute the rest of the pieces. I need to prove two lemmas in order to do this. First, that the number of incorrectly oriented edge pieces is always even. Second I need to show that the parity of the corner orbit and the parity of the edge orbit must be the same, and hence either both are even or both are odd.

----------------
Lemma 4:
Here is a proof that the number of incorrectly flipped edges on the odd degree n x n x n cube must be even.

Lemma 5:
Here is a proof that the parity of the corner orbit and the parity of the innermost edge orbit must be the same, and therefore either both are even or both are odd.
----------------

Recall the result of lemma 1, that the number of clockwise twists on the corner must be congruent to 0 (mod 3). Now we know enough to permute and orient the corners and innermost edges of the odd degree n x n x n cube.

Remember that we defined the reference of what will be the solved state to be the positions of the centermost pieces of each face. Fix these positions in space, meaning we ban any innermost slice move from the n x n x n cube, and this uniquely determines the solved state out of the 24 symmetries of the cube. Since our definition of the solved state does not relate to the corners, as was the case with the even degree n x n x n cube, we can now permute all the 8 corners into any of their allowable 8! positions. Now the corners either have even or odd parity after permuting them, and this parity must be reflected in the edges. Therefore we cannot permute the 12 innermost edges into all 12! of their possible positions, as half of those positions would have the corner and edge orbits having opposite parity. Therefore we can permute 10 of the pieces into their possible locations, which would uniquely determine the positions of the last two pieces in that orbit to make sure that the parity of that orbit is the same as the parity of the corner orbit. There the total number of positions that the corners and edges can be permuted into is 8!*P(12,10), where P(12,10)=12*11*10*9*8*7*6*5*4*3.

Now that the corners and edges are permuted into all of their allowable positions, we have to orient them. We can arbitrarily orient 7 of the 8 corners, which would uniquely determine the orientation of the 8th corner to satisfy lemma 1. Similarly we can arbitrarily orient 11 of the 12 edges, which would uniquely determine the orientation of the 12th edge in order to satisfy lemma 4. This means that given any permutation of the corners and edges there are 3⁷*2¹¹ possible orientations.

Therefore on the odd degree n x n x n cube the corners and edges can be permuted and oriented into 8!*P(12,10)*3⁷*2¹¹ possible positions. In order to write this in a simpler form, notice that 8!*P(12,10)*3⁷*2¹¹ = 8!*12!*3⁷*2¹⁰

remove this text later *final formula number below*