[seqfan] Re: chess king paths in 3D cube
Robert Gerbicz
robert.gerbicz at gmail.com
Fri Jun 11 21:15:59 CEST 2010
2010/6/11 Richard Mathar <mathar at strw.leidenuniv.nl>
>
> 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:
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
Yes, that is the square of that sequence, because for both x and y
coordinates you have a(n) possibilities for the path. (and you can choose
them independently).
More information about the SeqFan
mailing list