login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A272773 Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood). 9
1, 8, 56, 360, 2240, 13696, 82808, 496656, 2961136, 17573608, 103911424, 612577272, 3602222736, 21137815952, 123811421128, 724064474968, 4228582808424 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 08:29 EDT 2021. Contains 345162 sequences. (Running on oeis4.)