[seqfan] Re: chess king paths in 3D cube

[Robert Gerbicz]

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).