|
| |
|
|
A272763
|
|
Number of n-step self-avoiding walks on the square lattice with diagonals allowed (Moore neighborhood).
|
|
6
|
|
|
|
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
|
|
|
|
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;
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,walk,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
