• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Calculating Permutations on nxnxn Rubik's cube

Joined
Apr 4, 2010
Messages
82
Likes
0
Thread starter #1
anybody know how to calculate the number of permutations on an nXnXn 6-coloured rubik's cube?
(sort like this:
odd:
even: )
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Likes
134
Location
Atlanta, Georgia
WCA
2003HARD01
#5
He's looking for permutations, though. That formula factors in orientation.
In my formula, in the numerator, replace \( (24\times 2^{10}\times 12!)^{(n\ mod\ 2)} \) with \( (4\times 12!)^{(n\ mod\ 2)} \) and also delete the \( 3^6 \) term. This new formula will calculate only permutations and ignore orientations.

Chris
 
Joined
Sep 17, 2009
Messages
901
Likes
45
Location
New Orleans, LA
YouTube
4EverTrying
#10
\( \text{AmodB}=A-B\times floor\left( \frac{A}{B} \right) \), and floor is the greatest integer function. Mod is the remainder of a quotient. You can type Chris' formula into wolframalpha, and it is able to calculate large numbers and even gives their designated name.
 
Last edited:
Joined
Sep 17, 2009
Messages
901
Likes
45
Location
New Orleans, LA
YouTube
4EverTrying
#15
You can type Chris' formula into wolframalpha
With great difficulty :p
Yeah, you've got to know the syntax.

Here is Chris' formula which takes into account orientations as well.
Here is his adjusted formula that ignores orientations (that is, if I understood the changes he said to be made).

So, from the first formula (which I think Sharkretriver was really after):
2X2X2, 3X3X3, 4X4X4, 5X5X5, 6X6X6, 7X7X7, 10X10X10, 100X100X100, 1000X1000X1000, etc.
 
Joined
Jun 17, 2011
Messages
8
Likes
0
#16
I don't really get most of this stuff..
I can understand the math of calculating combinations and restrictions of corners and edges moving in pairs. But wich part of the formula restrict x y z (orientation of the cube)?? Thanks
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Likes
134
Location
Atlanta, Georgia
WCA
2003HARD01
#17
I don't really get most of this stuff..
I can understand the math of calculating combinations and restrictions of corners and edges moving in pairs. But wich part of the formula restrict x y z (orientation of the cube)?? Thanks
I can't believe I missed this question for so long :fp

If you look at my formula for the number of possible positions to a standard n x n x n Rubik's cube:
\( F(n) = \frac{(24*12!*2^{10})^{n (mod 2)}*7!*3^6*(24!)^{\lfloor\frac{n^2-2n}{4}\rfloor}}{(4!)^{6\lfloor\frac{(n-2)^2}{4}\rfloor}} \)

The portion that makes sure there are no overcounts considering x,y,z rotations of the cube is:
\( (24*12!*2^{10})^{n (mod 2)}*7!*3^6 \)

This term counts all possible positions of corners (if n is even), or corners and central edges (if n is odd).

In order to see how this avoids overcounting we will consider two cases:

Case 1:
If n is an even number (n=2k where k is a natural number), then we have:
\( (24*12!*2^{10})^{2k (mod 2)}*7!*3^6 = 7!*3^6 \)

There are only 7!*3^6 different possible positions for 8 corners, taking into account cube rotations as overcounting as well as the cube laws about twists of the corners.

If you don't see this, try to start with \( 8!*3^8 \) and figure out how this is an overcount by a factor of 72.

Case 2:
If n is an odd number (n=2k+1 where k is a natural number), then we have:
\( (24*12!*2^{10})^{2k + 1 (mod 2)}*7!*3^6 = (24*12!*2^{10})*7!*3^6 = 8!*3^7*12!*2^{10} \)

This is the number of ways that the corners and central edges can be permuted on an odd n x n x n cube, assuming that the central most centers are fixed, and define the solved state.

Just as we did for corners on an even cube, it would seem initially that the 8 corners and 12 edges should have the following number of possible positions:
\( 8!*3^8*12!*2^{12} \)

However, this is an overcount by a factor of 12. The reason why is based off of cube laws for rotations of corners, flips of edges, and parity restrictions for the corners and central most edges.

I know this maybe doesn't explicitly answer your question, but you can find a more detailed explanation on Ryan Heise's page describing the fundamental cube laws.
 
Joined
Sep 17, 2009
Messages
901
Likes
45
Location
New Orleans, LA
YouTube
4EverTrying
#19
@cmhardw (and anyone else who understands these formulas for number of permutations on the nxnxn cube),

I have a question regarding the formula for the nxnxn supercube. However, I first am going to show how I approached the regular nxnxn first (my formula is correct to my knowledge).

Here's my formula for the non-supercube (not simplified), [Link]
\( F\left( n \right)=\frac{\left( 8!\times 3^{7} \right)\left( \frac{24!}{\left( 4! \right)^{6}} \right)^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }\left( 24!^{\left\lfloor \frac{n-2}{2} \right\rfloor } \right)\left( 12!\times 2^{11} \right)^{n\bmod 2}}{\left( 24-23\left( n\bmod 2 \right) \right)2^{n\bmod 2}} \)
Just to show those that may be interested,
\( \left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor =\left\lfloor \frac{n-2}{2} \right\rfloor \left( n-2-\left\lfloor \frac{n-2}{2} \right\rfloor \right) \)\( =\frac{n-2-\left| \sin \left( \frac{n\pi }{2} \right) \right|}{2}\left( n-2-\frac{n-2-\left| \sin \left( \frac{n\pi }{2} \right) \right|}{2} \right) \),
\( n\bmod 2=n-2\left\lfloor \frac{n}{2} \right\rfloor =-\left\lfloor \left\lfloor \frac{n}{2} \right\rfloor -\frac{n}{2} \right\rfloor =\left\lceil \frac{n}{2}-\left\lfloor \frac{n}{2} \right\rfloor \right\rceil =\left| \sin \left( \frac{n\pi }{2} \right) \right|\text{ for }n\in \mathbb{Z}^{+} \),
and \( \left( 24-23\left( n\bmod 2 \right) \right)=24^{\left| \cos \left( \frac{n\pi }{2} \right) \right|} \).

(Hence the formula can be written with trig functions instead of step functions)
Corners
\( \left( 8!\times 3^{7} \right) \)
There are 8 corners, hence 8! permutations of them.
The orientation of one corner depends on the other 7. Each corner can be twisted 3 ways, so we have \( 3\times 3\times 3\times 3\times 3\times 3\times 3=3^{7} \)

Non-Fixed (NF) Center Pieces
\( \left( \frac{24!}{\left( 4! \right)^{6}} \right)^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor } \)

There are \( \left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor \) NF center orbits on the nxnxn cube. Each orbit is independent from the other (pieces from one NF center piece orbit cannot go into any other NF center pieces orbit), and each orbit contains (4 center pieces in each face)*(6 faces) = 24 pieces. 24 pieces can be arranged in 24! different ways. Because we are considering the non-supercube, then we reduce 24! by a factor of \( \left( 4! \right)^{6} \) before raising to \( \left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor \), the number of NF center orbits. The reason for the \( \left( 4! \right)^{6} \) reduction is because there are 4! ways to arrange the same color center pieces per NF center orbit (in any configuration) and there are 6 faces (hence raised to the 6th power).

Wing Edges
\( 24!^{\left\lfloor \frac{n-2}{2} \right\rfloor } \)
There are \( \left\lfloor \frac{n-2}{2} \right\rfloor \) orbits of wing edges on the nxnxn cube. Each orbit contains 24 pieces and each orbit is independent from the other (wing edges from one orbit cannot go into any other wing edge orbit). Hence each orbit of wings has 24! different permutations, and we raise it to the number of wing edge orbits, \( \left\lfloor \frac{n-2}{2} \right\rfloor \).

Middle Edges (Odd Cubes Only)
\( \left( 12!\times 2^{11} \right)^{n\bmod 2} \)
There are 12 edges and therefore 12! permutations of them. The orientation of one of the edges depends on the orientation of the other 11. An edge can be flipped in two ways, so we have \( 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2=2^{11} \). Since middle edges are only in odd cubes, we raise all of this to n mod 2 which simply means for our purposes:
\( \left\{ \begin{matrix}
0,\text{ if }n\text{ is even,} \\
1,\text{ if }n\text{ is odd}\text{.} \\
\end{matrix} \right. \)
(Obviously anything^1 is itself and anything^0 = 1).


Odd Permutation Reduction
\( \frac{1}{2^{n\bmod 2}} \)
Middle Edges are in an odd permutation if and only if corners are in an odd permutation. The total number of odd permutations = the total number of even permutations and thus we divide by a factor of 2. However, we only do so if the cube is odd, so we raise it to n mod 2.

Even Cube Symmetry Reduction
\( \frac{1}{\left( 24-23\left( n\bmod 2 \right) \right)} \)

If n is even, then there are 24 equivalent cube rotations in which the even cube can be in. Thus we need to have a function that yields the result:
\( f\left( n \right)=\left\{ \begin{matrix}
24,\text{ if }n\text{ is even,} \\
1,\text{ if }n\text{ is odd}\text{.} \\
\end{matrix} \right. \)
By how I showed the mod function works in the previous section, we can see that the piece above satisfies this requirement.
My formula for the nxnxn supercube (not simplified and which is equivalent to Chris Hardwick's) is: [Link]
\( F\left( n \right)=\frac{\left( 8!\times 3^{7} \right)\left( 12!\times 2^{11} \right)^{n\bmod 2}\left( 4^{6} \right)^{n\bmod 2}}{\left( 2^{n\bmod 2} \right)\left( 2^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor } \right)\left( 2^{n\bmod 2} \right)} \)\( \text{ }\times \left( 24!^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor } \right)\times \left( 24!^{\left\lfloor \frac{n-2}{2} \right\rfloor } \right)\times \frac{1}{24-23\left( n\bmod 2 \right)} \)
Corners (Same and non-supercubes)
\( \left( 8!\times 3^{7} \right) \)
There are 8 corners, hence 8! permutations of them.
The orientation of one corner depends on the other 7. Each corner can be twisted 3 ways, so we have \( 3\times 3\times 3\times 3\times 3\times 3\times 3=3^{7} \)

Non-Fixed (NF) Center Pieces
\( \left( 24!^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor } \right) \)
Unlike the non-supercubes, we do not reduce this by a factor of \( \left( 4! \right)^{6} \) because center pieces are now unique to their positions.

Wing Edges (Same as non-supercubes)
\( 24!^{\left\lfloor \frac{n-2}{2} \right\rfloor } \)
There are \( \left\lfloor \frac{n-2}{2} \right\rfloor \) orbits of wing edges on the nxnxn cube. Each orbit contains 24 pieces and each orbit is independent from the other (wing edges from one orbit cannot go into any other wing edge orbit). Hence each orbit of wings has 24! different permutations, and we raise it to the number of wing edge orbits, \( \left\lfloor \frac{n-2}{2} \right\rfloor \).

Middle Edges (Odd Cubes Only) (Same as non-supercubes)
\( \left( 12!\times 2^{11} \right)^{n\bmod 2} \)
There are 12 edges and therefore 12! permutations of them. The orientation of one of the edges depends on the orientation of the other 11. An edge can be flipped in two ways, so we have \( 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2=2^{11} \). Since middle edges are only in odd cubes, we raise all of this to n mod 2 which simply means for our purposes:
\( \left\{ \begin{matrix}
0,\text{ if }n\text{ is even,} \\
1,\text{ if }n\text{ is odd}\text{.} \\
\end{matrix} \right. \)
(Obviously anything^1 is itself and anything^0 = 1).

Fixed Center Pieces (On Odd Cubes Only)
\( \left( 4^{6} \right)^{n\bmod 2} \)
There are 6 fixed center pieces on the odd nxnxn cube. Each stay fixed with respect to each other, and each can be rotated in 4 ways in their locations. Since each can be rotated in their locations 4 ways and there are 6 of them, there are \( 4^{6} \) possible ways this can be done.

Odd Permutation Reduction
a) \( \frac{1}{2^{n\bmod 2}} \) (Odd Cubes Only) (Same as the non-supercube)
Middle Edges are in an odd permutation if and only if corners are in an odd permutation. The total number of odd permutations = the total number of even permutations and thus we divide by a factor of 2. However, we only do so if the cube is odd, so we raise it to n mod 2.

b) \( \frac{1}{2^{n\bmod 2}} \) (Odd Cubes Only)
Fixed center pieces are in an odd permutation if and only if corners are in an odd permutation if and only if middle edges are in an odd permutation.
The total number of odd permutations = the total number of even permutations and thus we divide by a factor of 2. However, we only do so if the cube is odd, so we raise it to n mod 2.

c) \( \frac{1}{2^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }} \)
If corners are in an odd permutation, then all non-fixed (NF) center orbits are in an odd permutation. (For those who can't see this, just do R to a supercube and see that it does a circular 4-cycle of every NF center piece orbit. Furthermore, corners in an odd permutation does not make the permutation of wing edges odd because R does 2 4-cycles of each and every orbit of wing edges, which is an even permutation).

The total number of odd permutations = the total number of even permutations and thus we divide by a factor of 2 per NF center orbit. Hence we raise 2 to \( \left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor \), the number of center orbits on the nxnxn cube (odd and even).

Even Cube Symmetry Reduction (Same as the non-supercube)
\( \frac{1}{\left( 24-23\left( n\bmod 2 \right) \right)} \)

If n is even, then there are 24 equivalent cube rotations in which the even cube can be in. Thus we need to have a function that yields the result:
\( f\left( n \right)=\left\{ \begin{matrix}
24,\text{ if }n\text{ is even,} \\
1,\text{ if }n\text{ is odd}\text{.} \\
\end{matrix} \right. \)
By how I showed the mod function works in the middle edges section, we can see that the piece above satisfies this requirement.
Now this is what I am questioning about the supercube formula. If you compare my supercube formula to Chris Hardick's, you will see they yield the same values. Now that you've seen I have taken care of the NF center piece reduction factor, the fixed center piece reduction factor, and the middle edge reduction factor, all directly associated with an odd permutation of corners AND yielding a formula identical to Chris Hardwick's...

Assume the corners are in an even permutation now. Then assume that either the NF center pieces or the wings (it doesn't really matter) are in an odd permutation. Then the other is in an odd permutation too, that is, for cube sizes \( \ge \)the 5x5x5 supercube.

I know it's very possible I have misinterprented the given values in my formula, but if not (meaning that my explanation of each factor of the formula is correct), shouldn't there be another odd permutation reduction factor of \( \frac{1}{2^{\left\lfloor \frac{n-2}{2} \right\rfloor }} \) for the 5x5x5 and greater cubes since the parity state of \( f\left( n,r \right)=n-2-2r\text{ }\left( n\ge 4,\text{ }r\ge 1,\text{ }n,r\in \mathbb{Z} \right) \) center orbits is changed to odd if the parity state of r orbits of wings (in any of the \( 2^{\left\lfloor \frac{n-2}{2} \right\rfloor }-1 \) possible combinations) is changed to an odd permutation?


EDIT:
Clearly both of my formulas can be combined into one (no simplification applied)


From this, we can see that the factor increase from the regular nxnxn to the supercube nxnxn is
\( \frac{4^{6n\bmod 2}4!^{6\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }}{2^{n\bmod 2}2^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }}=3^{6\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }2^{17\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor +11n\bmod 2} \)

Substituting in 7 for n, I got the same value mrCage got for "the number of solved positions for the 7x7x7" here. This is the link to my value (which matches it perfectly).

and 18698417887260966912 is the number of solved positions for the 5x5x5, etc.

But, until I can get someone to say with assurance that we don't need to multiply in the extra reducing factor, I am not sure these are the correct values either.:)
 
Last edited:
Joined
Sep 17, 2009
Messages
901
Likes
45
Location
New Orleans, LA
YouTube
4EverTrying
#20
If we do need that odd permutation reduction factor, I have managed to make a function that outputs \( \frac{1}{2^{\left\lfloor \frac{n-2}{2} \right\rfloor }} \) for cube sizes 5 and greater and 1 for cube sizes 2-4. It is \( \frac{1}{2^{\left\lfloor \frac{n-2}{2} \right\rfloor -\left\lfloor \frac{4}{n} \right\rfloor +\left\lfloor \frac{2}{n-1} \right\rfloor }} \). [Link]
 
Top