Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #24 Aug 02 2021 06:41:03
%S 0,1,6,2,21,31,3,36,53,80,4,55,84
%N Triangle T(j,k) read by rows, where T(j,k) is the number of single tile moves in the longest optimal solution of the j X k generalization of the sliding block 15-puzzle, starting with the empty square in a corner.
%C T(k,j) = T(j,k).
%C T(2,2), T(2,3), T(4,2), T(4,3) from Karlemo and Östergård, T(3,3) from Reinefeld, T(4,4) from Bruengger et al.
%D For references and links see A087725(n)=T(n,n).
%e The triangle begins
%e 0
%e 1 6
%e 2 21 31
%e 3 36 53 80
%e 4 55 84 ...
%e .
%e a(6)=T(3,3)=31 because the A090163(3,3)=2 longest optimal solution paths of the 3 X 3 (9-) sliding block puzzle have length 31 (see A089473).
%o (Python) # alst(), moves(), swap() in A089473
%o def T(j, k): # chr(45) is '-'
%o start, shape = "".join(chr(45+i) for i in range(j*k)), (j, k)
%o return len(alst(start, shape))-1
%o for j in range(1, 5):
%o for k in range(1, j+1):
%o print(T(j,k), end=", ") # _Michael S. Branicky_, Aug 02 2021
%Y Cf. A087725, A089473, A089484, A090034, A090035, A090036, A090166, A090163 corresponding number of different configurations with largest distance.
%Y Cf. A151944 same as this sequence, but written as full array.
%K nonn,tabl,hard,more
%O 1,3
%A _Hugo Pfoertner_, Nov 23 2003
%E T(5,3) copied from A151944 by _Hugo Pfoertner_, Aug 02 2021