A335136 Irregular triangle read by rows: T(n,k) is the number of permutations of an n X n Rubik's Square reachable in k or fewer moves, terminating at the maximum value.

1, 2, 1, 5, 6, 1, 7, 30, 71, 119, 160, 184, 192, 1, 9, 53, 221, 592, 1072, 1296, 1, 11, 80, 488, 2550, 10511, 35601, 99142, 218400, 382480, 538912, 630080, 658944, 663552

Offset

1,2

Comments

For this sequence, a Rubik's Square is 2 dimensional and only has 2 colors. This sequence uses quarter-turn notation; a move is a reversion of either a row or column. So, if one color is '1' and the other is '0', performing a move on [0,1,1,0,0] would make that row/column [1,1,0,0,1].

There are two questions associated with this triangle. First, how many permutations are reachable for an n X n Rubik's Square (what is the maximum value in the n-th row)? Second, what is the number of moves necessary to solve an n X n Rubik's Square (when does the n-th row terminate)?

Links

Table of n, a(n) for n=1..34.

E. D. Demaine, M. L. Demaine, S. Eisenstat, A. Lubiw, and A. Winslow, Algorithms for Solving Rubik’s Cubes, arXiv:1106.5736 [cs.DS], 2011.

E. D. Demaine, S. Eisenstat, and M. Rudoy, Solving the Rubik's Cube Optimally is NP-complete, arXiv:1706.06708 [cs.CC], 2017-2018.

Example

The irregular triangle T(n,k) starts:
  n\k 0  1  2   3    4     5     6     7      8      9     10     11 ...
   1: 1  2
   2: 1  5  6
   3: 1  7 30  71  119   160   184   192
   4: 1  9 53 221  592  1072  1296
   5: 1 11 80 488 2550 10511 35601 99142 218400 382480 538912 630080 ...

Prog

(PARI) A335136_row(n)={my(total=List([0]), completed=List(), moves=[1..2*n], moves2=select(X->X, [-n..n]), M=List([]), moves2bits=Map(Mat([moves~, apply(y-> my(Q=Map(Mat([(S=select(X->floor(X/(n^(y<0)))%n==(abs(y)-1), [0..n^2-1]))[1..ceil(#S/2)]~, Vecrev(S)[1..ceil(#S/2)]~])));
apply(X->shift(shift(1, mapget(Q, X)-X)+(X!=mapget(Q, X)), X), Mat(Q)[, 1]) , moves2)~])), mover(Y, Z)=bitxor(Z, vecsum(select(W->my(B=bitand(Z, W)); (!B||B==W), mapget(moves2bits, Y)))));
while(#completed<#total, listput(M, #total); my(new=setminus(Vec(total), Vec(completed))); completed=total; forvec(A=[[1, 2*n], [1, #new]], my(F=mover(A[1], new[A[2]]), S=setsearch(total, F, 1)); if(S, listinsert(total, F, S)))); M}

Crossrefs

Sequence in context: A269019 A184234 A193816 * A193722 A193635 A241168

Adjacent sequences: A335133 A335134 A335135 * A335137 A335138 A335139

Keyword

nonn,tabf,more

Author

Davis Smith, Jun 02 2020

Status

approved