login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A272763 Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood). 2
1, 8, 56, 368, 2336, 14576, 89928, 550504, 3349864, 20290360, 122445504, 736685008, 4421048016, 26475370088, 158257613848, 944493430152, 5628996811904 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Moore neighborhood :

o o o

o x o

o o o

Von Neumann neighborhood (A001411):

  o

o x o

  o

Note that the path avoids already visited lattice points, but can intersect itself (two diagonal steps). A nonintersecting version is A272773.

The Moore neighborhood characterizes king tours. # Rainer Rosenthal, Jan 05 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.

# If there are n+1 then the path is self-avoiding.

isSelfAvoiding := proc(Ldir) local Delta, dir, ep, 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

      ep := ep + Delta[dir];

      path := {op(path), ep};

   od;

   return evalb(nops(path)=nops(Ldir)+1);

end:

# Count only king tours which are self-avoiding

A272763 := 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 isSelfAvoiding(p) then count := count+1; fi;

   od:

   return count;

end: # Rainer Rosenthal, Jan 05 2019

MATHEMATICA

mo=Most@Tuples[{-1, 1, 0}, 2]; a[0]=1; a[tg_, p_: {{0, 0}}] := Block[{e, mv = Complement[Last[p] + # & /@ mo, p]}, If[tg == 1, Length@mv, Sum[a[tg - 1, Append[p, e]], {e, mv}]]]; a /@ Range[0, 7] (* Giovanni Resta, May 06 2016 *)

CROSSREFS

Cf. A001411, A272773, A300665.

Sequence in context: A272773 A162754 A081626 * A199939 A003494 A057084

Adjacent sequences:  A272760 A272761 A272762 * A272764 A272765 A272766

KEYWORD

nonn,walk,more

AUTHOR

Francois Alcover, May 05 2016

EXTENSIONS

a(13)-a(16) from Giovanni Resta, May 06 2016

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 January 24 00:10 EST 2019. Contains 319404 sequences. (Running on oeis4.)