A272773
Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).
Original entry on oeis.org
1, 8, 56, 360, 2240, 13696, 82808, 496656, 2961136, 17573608, 103911424, 612577272, 3602222736, 21137815952, 123811421128, 724064474968, 4228582808424
Offset: 0
-
# 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
-
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 *)
A323562
Number of rooted self-avoiding king's walks on an infinite chessboard trapped after n moves.
Original entry on oeis.org
8, 200, 2446, 21946, 169782, 1205428, 8119338, 52862872, 336465352, 2108185746
Offset: 8
a(8) = 8, because the following 8 walks of 8 moves of a king starting at S with a first move (0,0)->(1,0) visit all neighbors of the trapping location T. The starting point itself is also blocked. There are no such shortest walks with first move (0,0)->(1,1).
.
o <-- o <-- o o o <-- o o --> o --> o o <-- o <-- o
| ^ ^ \ / ^ ^ | | ^
v | | / \ | | v v |
o --> T o o T o o T o o T o
^ ^ \ \ | | / ^
| | \ \ v v / |
S --> o --> o S --> o --> o S --> o o o S --> o
.
S --> o --> o S --> o --> o S --> o o o S --> o
| | / / ^ ^ \ |
v v / / | | \ v
o --> T o o T o o T o o T o
^ | | \ / | | ^ ^ |
| v v / \ v v | | v
o <-- o <-- o o o <-- o o --> o --> o o <-- o <-- o
- _Hugo Pfoertner_, Jul 23 2020
A323560
Number of self-avoiding knight's paths trapped after n moves on an infinite chessboard with first move specified.
Original entry on oeis.org
1728, 10368, 332660, 1952452
Offset: 15
There are two (of a(15)=1728) paths of 15 moves of minimum extension 5 X 5:
(N) b1 d2 e4 c5 a4 b2 d1 e3 d5 b4 a2 c1 e2 d4 b5 c3, and
(N) a4 c5 e4 d2 b1 a3 b5 d4 e2 c1 a2 b4 d5 e3 d1 c3.
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.
Original entry on oeis.org
71, 71, 40, 77, 45, 51, 42, 56, 49, 51, 48, 54
Offset: 3
- 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.
A323140
Number of uncrossed king's paths of length n, reduced for symmetry, A272773/8.
Original entry on oeis.org
1, 7, 45, 280, 1712, 10351, 62082, 370142, 2196701, 12988928, 76572159, 450277842, 2642226994, 15476427641, 90508059371
Offset: 1
Showing 1-5 of 5 results.
Comments