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$
5
  • 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
  • $\begingroup$ I am doubtful whether the video is a correct reference. The paper „Rubik's revenge: the group theoretical solution“ (Larsen 1985) arrives at a different result for the 4x4 case. On first sight I would trust the paper more since it properly analyzes the group instead of giving ad-hoc combinatorial arguments without proof. $\endgroup$ Mar 20, 2023 at 12:44
  • $\begingroup$ @LukasJuhrich Well, I'm inclined to think that the result in that paper is wrong, because it disagrees with the result on Wikipedia and OEIS. $\endgroup$
    – K.defaoite
    Mar 20, 2023 at 17:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .