[seqfan] chess king paths in 3D cube
Richard Mathar
mathar at strw.leidenuniv.nl
Fri Jun 11 20:55:40 CEST 2010
I thought to count the 3D analog of A081113, here the number
of n-1-step paths a 3D chess king can make starting from one face of the
n-by-n-by-n cube to the opposite one. The rule is that the king can move in one
step to any of the 26 (=3*3-1) adjacent positions; because we allow only
solutions with n-1 steps, one component of the direction is enforced and there
only a choice of 9 different next steps remains; if the path is close to the cube
surface, even less.
Example: for n=2, we can start from any of the 4 places on one face and move
from there directly to any of the 4 positions on the opposite side: a(2)=4*4=16.
The answer seems to be 1,16,289,4624,67081,902500,11471769,139570596 (n=1,2,3..)
by brute force count. Unexpectedly, these are the squares of A081113. Is there
some reason for such an outcome (perhaps in some 3D Motzkin-path section)?
Richard
post scriptum: luckily, there are no primes in the sequence!
post scriptum II: A003991, referenced in A081113, has two different formulas,
the one as an array T(i,j)=i*j in the definition, and one in the formula section
T(n,m)=m*(n-m+1), as a triangle. Only one of these can be correct.
# 3D analog of A081113 (beware: Maple)
# Cube edge length is n. thisr and thisc are the two coordinates projected
# to the starting face, 1<=thisr,thisc<=n. 1<=z<=n is the perpendicular coordinate
# where 1=starting face, n= final face.
# Count the different ways to make it from z (as given) to z=n.
thDrec := proc(n,thisr,thisc,z)
local a,r,c ;
a := 0 ;
if z < n then
# not yet at opposite face: check the 3-by-3 different new
# positions to be still within the cube, and accumulate their
# count recursively.
for r from thisr-1 to thisr+1 do
for c from thisc-1 to thisc+1 do
if r >= 1 and r <=n and c >=1 and c <=n then
a := a+procname(n,r,c,z+1) ;
end if;
end do:
end do:
return a;
elif z = n then
# if position at the opposite face and still in the cube:
# one more path found.
if thisr >= 1 and thisr <= n and thisc >=1 and thisc <= n then
return 1;
else
return 0;
end if;
end if;
end proc:
thD := proc(n)
local strt,r,c,a ;
# The array of the different starting positions on the initial
# side and the corresponding differnt paths counted (initially none).
strt := array(1..n,1..n) ;
for r from 1 to n do
for c from 1 to n do
strt[r,c] := 0 ;
end do:
end do:
for r from 1 to n do
for c from 1 to n do
# if paths not yet known: start from that (row,column) position
# and use some symmetry of the square to fill in equivalent
# other positions (mirror and rotational symmetries), lazy and incomplete
if strt[r,c] = 0 then
strt[r,c] := thDrec(n,r,c,1) ;
strt[n-r+1,c] := strt[r,c] ;
strt[r,n-c+1] := strt[r,c] ;
strt[c,r] := strt[r,c] ;
end if;
end do:
end do:
# total of paths is the sum over all paths from any of the n-by-n
# starting positions.
a := 0 ;
for r from 1 to n do
for c from 1 to n do
a := a+strt[r,c] ;
end do:
end do:
a ;
end proc:
# run the function for edge lengths of 1 and more
for n from 1 do
print(n,thD(n)) ;
end do:
More information about the SeqFan
mailing list