A272773 Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).

1, 8, 56, 360, 2240, 13696, 82808, 496656, 2961136, 17573608, 103911424, 612577272, 3602222736, 21137815952, 123811421128, 724064474968, 4228582808424

Offset

0,2

Comments

The path cannot return to a lattice point nor intersect with itself (which IS allowed in A272763).

The Moore neighborhood characterizes king tours. - Rainer Rosenthal, Jan 06 2019

Links

Table of n, a(n) for n=0..16.

Maple

# For starting point stp and list Ldir of n directions (1..8)
# construct the points of the whole path and count them.
# In order to avoid crossings consider the n midpoints, too.
# If there are 2*n+1 then the path is self-avoiding and uncrossed.
isNice := proc(Ldir) local Delta, dir, ep, mp, path;
   Delta := [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]];
   ep := [0, 0]; path := {ep};
   for dir in Ldir do
      mp := ep + Delta[dir];
      ep := mp + Delta[dir];
      path := {op(path), mp, ep};
   od;
   return evalb(nops(path)=2*nops(Ldir)+1);
end:
# Count only king tours which are nice, i.e. self-avoiding and uncrossed.
A272773 := proc(n) local count, T, p;
   count := 0:
   T := combinat[cartprod]([seq([$1..8], j=1..n)]):
   while not T[finished] do
      p := T[nextvalue]();
      if isNice(p) then count := count+1; fi;
   od:
   return count;
end: # Rainer Rosenthal, Jan 06 2019

Mathematica

mo = Most@Tuples[{-1, 1, 0}, 2]; a[0] = 1; a[tg_, p_: {{0, 0}}] := Block[{e, z = Last@p, w, mv = {}}, Do[w = {z+e, z+2*e}; If[Intersection[w, p] == {}, AppendTo[mv, w]], {e, mo}]; If[tg == 1, Length[mv], Sum[a[tg-1, Join[p, e]], {e, mv}]]]; a /@ Range[0, 7] (* Corrected following a suggestion by Rainer Rosenthal, Giovanni Resta, Jan 06 2019 *)

Crossrefs

Cf. A272763, A001411, A323140, A323141.

Sequence in context: A334333 A307813 A291387 * A162754 A081626 A272763

Adjacent sequences: A272770 A272771 A272772 * A272774 A272775 A272776

Keyword

nonn,walk,more

Author

Giovanni Resta, May 06 2016

Extensions

a(5)-a(7) corrected by Rainer Rosenthal, Jan 06 2019

a(8)-a(16) from Hugo Pfoertner, Jan 06 2019

Status

approved