9
$\begingroup$

I'd like to know how fast the number of permutations grows on an $n\times n\times n$ Rubik's Cube as $n$ increases. I'm well aware of the $\frac{3^88!2^{12}12!}{12}$ calculation for the permutations of a $3\times3\times3$, and I know this idea generalizes (with a little bit of work to deal with the denominator). But I'm struggling to come up with a general formula for the number of permutations in an $n\times n\times n$ Cube. I would hypothesize that the rate of growth is worse than super-exponential, but I'm not sure.

$\endgroup$

1 Answer 1

8
$\begingroup$

I believe that for an $n\times n\times n$ cube the formula for the number of Rubik's cube permutations ($\text{RCP}$) is $$\text{RCP}(n)=\frac{1}{24^{(n+1)~\text{mod}~2}}3^7\cdot8!\left(\frac{24!}{24^6}\right)^{\left\lfloor\left(\frac{n-2}{2}\right)^2\right\rfloor}(24!)^{\left\lfloor\frac{n-2}{2}\right\rfloor}(2^{10}\cdot12!)^{n~\text{mod}~2}$$ Reference: This video. I implemented it in Desmos and it indeed produces the correct numbers for the $3\times 3\times 3$, $4\times 4\times 4$, and $5\times 5\times 5$ cases. It appears to grow at a roughly $~\mathcal{O}(C^{n^2})$ rate with some constant $C$.

UPDATE:

I've implemented a scatterplot of this feature in Desmos but it gives up after $n=10$ as the numbers get too large. You can find it here. I'll give it a shot in Python to see if I can crunch the numbers on a few more data points.

UPDATE #2:

Nope, Python gives up after $n=11$ as well. Perhaps somebody with Wolfram premium server computations can produce a few more data points. Here's what I have so far:

RCP graph

And the code used to generate this:

import numpy as np
import matplotlib.pyplot as plt
import math
def RCP(n):
    return (1/24**((n+1)%2))*(3**7)*math.factorial(8)*(math.factorial(24)/(24**6))**(int(((n-2)/2)**2))*math.factorial(24)**(int((n-2)/2))*(2**10 *math.factorial(12))**(n%2)
N=11
nums=range(2,N)
perms=np.zeros(len(nums))
for n in range(0,len(perms)):
    perms[n]=RCP(nums[n])
plt.scatter(nums,np.log(perms))
plt.xlabel("$n$")
plt.ylabel("$\log(RCP(n))$")
plt.show()

UPDATE #3: I crunched the numbers for the higher cases, albeit crudely. For the large numbers shown on this page I copied the number, threw it into Python, got the length of the string, then chopped off the first 10-20 digits of the number and took the log of that number multiplied by $10^{\text{length }-1}$. Here is the code with the numbers I crunched:

import numpy as np
import matplotlib.pyplot as plt
nums=range(1,28)
logperms=np.zeros(len(nums))
logperms[0]=1
logperms[1]=np.log(3674160.0)
logperms[2]=np.log(43252003274489856000.0)
logperms[3]=105.617970907
logperms[4]=171.431117455
logperms[5]=267.551919553
logperms[6]=369.081472517
logperms[7]=500.918681032
logperms[8]=638.164640411
logperms[9]=805.7182553
logperms[10]=978.6806211
logperms[11]=1181.950642
logperms[12]=1390.629414
logperms[13]=1629.615842
logperms[14]=1874.011021
logperms[15]=2148.713855
logperms[16]=2428.82544030884974
logperms[17]=2739.24468090354993
logperms[18]=3055.07267236335638
logperms[19]=3401.208319374081227
logperms[20]=3752.752717249912322
logperms[21]=4134.604770676661809
logperms[22]=4521.865574968517551
logperms[23]=4939.43403481129168567718
logperms[24]=5362.41124551917207073483
logperms[25]=5815.69611177797085072813
logperms[26]=6274.38972890187588125802
plt.scatter(nums,logperms)
plt.xlabel("$n$")
plt.ylabel("$\log(RCP(n))$")
plt.show()

And the graph it produced:

RCP scatterplot (more data)

It follows a nice parabolic shape :)

Hope you enjoyed reading!

$\endgroup$
3
  • 2
    $\begingroup$ here are the values up to $n=27$ oeis.org/A075152/b075152.txt (also some good resources here oeis.org/A075152) $\endgroup$
    – timidpueo
    Jul 8, 2020 at 3:17
  • $\begingroup$ Note: not sure why I decided to take the double log. A single log would be more suitable. As the graph @timidpueo linked shows, $\ln(\text{RCP}(n))$ grows roughly as $\mathcal{O}(n^2)$. $\endgroup$
    – K.defaoite
    Jul 8, 2020 at 4:40
  • 1
    $\begingroup$ @Atsina I added a graph with more data points. $\endgroup$
    – K.defaoite
    Jul 8, 2020 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.