A300665 -id:A300665 - cp's OEIS frontend

A272763 Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood).

1, 8, 56, 368, 2336, 14576, 89928, 550504, 3349864, 20290360, 122445504, 736685008, 4421048016, 26475370088, 158257613848, 944493430152, 5628996811904

Offset: 0

Francois Alcover, May 05 2016

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

Cf. A001411, A272773, A300665.

# 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

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

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

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.

Original entry on oeis.org

71, 71, 40, 77, 45, 51, 42, 56, 49, 51, 48, 54

Offset: 3

Hugo Pfoertner, Dec 27 2018

The cases n = 3, 4, and 6 correspond to the usual self-avoiding random walks on the honeycomb net, the square lattice, and the hexagonal lattice, respectively. The other cases n = 5, 7, ... are a generalization using self-avoiding rooted walks similar to those defined in A306175, A306177, ..., A306182. The walk is trapped if it cannot be continued without either hitting an already visited (lattice) point or crossing or touching any straight line connecting successively visited points on the path up to the current point.
The result 71 for n=4 was established in 1984 by Hemmer & Hemmer.
The sequence data are based on the following results of at least 10^9 simulated random walks for each n <= 12, with an uncertainty of +- 0.004 for the average walk length:
   n  length
71.132
70.760 (+-0.001)
40.375
77.150
45.297
51.150
42.049
56.189
48.523
51.486
47.9   (+-0.2)
53.9   (+-0.2)

S. Hemmer, P. C. Hemmer, An average self-avoiding random walk on the square lattice lasts 71 steps, J. Chem. Phys. 81, 584 (1984)
Hugo Pfoertner, Examples of self-trapping random walks.
Hugo Pfoertner, Probability density for the number of steps before trapping occurs, 2018.
Hugo Pfoertner, Results for the 2D Self-Trapping Random Walk.
Alexander Renner, Self avoiding walks and lattice polymers, Diplomarbeit, Universität Wien, December 1994.

Cf. A001668, A001411, A001334, A077482, A306175, A306177, A306178, A306179, A306180, A306181, A306182.

Cf. A122223, A122224, A122226, A127399, A127400, A127401, A300665, A323141, A323560, A323562, A323699.

cp's OEIS Frontend

A272763 Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Extensions

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

cp's OEIS Frontend

A272763 Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Extensions

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi*(2*k/n - 1), k = 1..n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.