[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)?

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;
			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