|
|
A322419
|
|
Number of n-step self-avoiding walks on L-lattice.
|
|
4
|
|
|
1, 2, 4, 8, 12, 20, 32, 52, 84, 136, 220, 356, 564, 904, 1448, 2320, 3684, 5872, 9376, 14960, 23688, 37652, 59912, 95316, 150744, 239080, 379528, 602424, 951788, 1507136, 2388252, 3784344, 5973988, 9447880, 14950796, 23658540, 37321752, 58965260, 93206864, 147333080, 232286272
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
The L-lattice is an oriented square lattice in which each step must be followed by a step perpendicular to the preceding one.
|
|
LINKS
|
|
|
FORMULA
|
It is proved that a(n)^(1/n) has a limit mu called the "connective constant" of the L-lattice; approximate value of mu: 1.5657. It is only conjectured that a(n + 1) ~ mu * a(n).
|
|
EXAMPLE
|
a(1) = 2 because there are only two possible directions at each intersection; for the same reason a(2) = 2*2 and a(3) = 2*4 ; but a(4) = 12 (not 16) because four paths return to the starting point and are not self-avoiding. See the 12 paths under "links".
|
|
MAPLE
|
walks:=proc(n)
option remember;
local i, father, End, X, walkN, dir, u, x, y;
if n=1 then [[[0, 0]]] else
father:=walks(n-1):
walkN:=NULL:
for i to nops(father) do
u:=father[i]:End:=u[n-1]:if n mod 2 = 0 then
dir:=[[1, 0], [-1, 0]] else dir := [[0, 1], [0, -1]] fi:
for X in dir do
if not(member(End+X, u)) then walkN:=walkN, [op(u), End+X] fi;
od od:
[walkN] fi end:
n:=5:L:=walks(n):N:=nops(L);
# This program explicitly gives the a(n) walks.
|
|
MATHEMATICA
|
mo = {{1, 0}, {-1, 0}}; moo = {{0, 1}, {0, -1}}; a[0] = 1;
a[tg_, p_: {{0, 0}}] := Module[{e, mv},
If[Mod[tg, 2] == 0, mv = Complement[Last[p] + # & /@ mo, p],
mv = Complement[Last[p] + # & /@ moo, p]];
If[tg == 1, Length@mv, Sum[a[tg - 1, Append[p, e]], {e, mv}]]];
|
|
PROG
|
(Python)
def add(L, x):
M = [y for y in L]
M.append(x)
return M
plus = lambda L, M: [x + y for x, y in zip(L, M)]
mo = [[1, 0], [-1, 0]]
moo = [[0, 1], [0, -1]]
def a(n, P=[[0, 0]]):
if n == 0:
return 1
if n % 2 == 0:
mv1 = [plus(P[-1], x) for x in mo]
else:
mv1 = [plus(P[-1], x) for x in moo]
mv2 = [x for x in mv1 if x not in P]
if n == 1:
return len(mv2)
else:
return sum(a(n - 1, add(P, x)) for x in mv2)
[a(n) for n in range(21)]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,walk
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|