OFFSET
1,1
COMMENTS
From M. F. Hasler, Jun 18 2025: (Start)
This sequence gives the number of self-avoiding paths starting and ending at the origin. It does not consider equivalence with respect to translations, rotations or reflections. So it does count multiple cycles whose set of edges represents the same polygon. For example, a(2) = 48 counts 4-step cycles which all correspond to a unit square.
This explains why 8n | a(n) for all n, and a(n)/8n = (1, 3, 38, 717, 16308, 422216, 11959932, 361658946, 11492507204, 379727971590, ...)
Also, a(n = 1) = 8 gives the 2-step cycles which correspond to one step in any of the 8 directions, and one step back. Although this path is self-avoiding since it does not cross any point multiple times, it uses the same edge for the first and second step, and therefore might be excluded from the counting. In three dimensions this is done in A001413, A001413(1) = 0, as opposed to A010567(1) = 6. For two dimensions, this alternate definition is also used in A010566(1) = 0.
(End)
LINKS
Nathan Clisby, Richard Liang, and Gordon Slade, Self-avoiding walk enumeration via the lace expansion, J. Phys. A: Math. Theor. 40 (2007), 10973-11017. Table A6 "Enumeration results for d = 4", column p_n, row 2*n gives a(n)/(4*n) for n>1.
Nathan Clisby, Richard Liang, and Gordon Slade, Self-avoiding walk enumeration via the lace expansion. [Tables in machine-readable format on separate pages.]
M. E. Fisher and D. S. Gaunt, Ising model and self-avoiding walks on hypercubical lattices and high density expansions, Phys. Rev. 133 (1964) A224-A239.
FORMULA
For all n, a(n) is divisible by 8*n. - M. F. Hasler, Jun 18 2025
PROG
(Python)
def A010568(n): # For illustration - becomes slow for n > 5
if not hasattr(A:=A010568, 'r'):
A.terms = [8]; O = 0,; I = O*4, (1, *O*3)
A.paths = (*I, (2, *O*3)), (*I, (1, 1, 0, 0))
while n > len(A.terms):
for L in (0, 1):
new=[]; cycles = 0; O=(0, )*4; I = 0, 1, 2, 3
for path in A.paths:
end = path[-1]; weight = 48 if path[2][1] else 8
for i in I:
for s in (1, -1):
t = tuple(end[j]if j!=i else end[j]+s for j in I)
if t not in path: new.append(path+(t, ))
elif L and t==O: cycles += weight
A.paths = new
A.terms.append(cycles)
return A.terms[n-1] # M. F. Hasler, Jun 17 2025
CROSSREFS
KEYWORD
nonn,walk,more,changed
AUTHOR
EXTENSIONS
a(6)-a(8) from Sean A. Irvine, May 31 2018
a(9)-a(10) from Sean A. Irvine, Aug 09 2020
"Self-avoiding" inserted in definition by M. F. Hasler, Jun 18 2025
a(11)-a(13) from Clisby et al.'s data added by Andrei Zabolotskii, Jun 25 2025
STATUS
approved