A374397 a(n) is the number of 4-step self avoiding walks in the n-dimensional hypercubic lattice that start at the origin.

2, 100, 726, 2696, 7210, 15852, 30590, 53776, 88146, 136820, 203302, 291480, 405626, 550396, 730830, 952352, 1220770, 1542276, 1923446, 2371240, 2893002, 3496460, 4189726, 4981296, 5880050, 6895252, 8036550, 9313976, 10737946, 12319260, 14069102, 15999040, 18121026

Offset: 1

Author

Johann Peters, Jul 07 2024

Keywords

• nonn
• walk
• easy

Comments

We have the formula below because we have 2*n choices for the first step, and (2*n-1)^3 choices for the next three, but have counted exactly 2*n*(2*n-1)*(2*n-2) self-intersecting walks.

References

• N. Madras and G. Slade, "The Self Avoiding Walk", Birkhäuser, 2013.

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000
• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Crossrefs

Cf. A010575.

Programs

Mathematica

A374397[n_] := 2*n*(4*n*(n - 1)*(2*n - 1) + 1);
Array[A374397, 50] (* or *)
LinearRecurrence[{5, -10, 10, -5, 1}, {2, 100, 726, 2696, 7210}, 50] (* Paolo Xausa, Sep 23 2024 *)

Formula

a(n) = 16*n^4 - 24*n^3 + 8*n^2 + 2*n.

G.f.: 2*x*(1 + 45*x + 123*x^2 + 23*x^3)/(1 - x)^5. - Stefano Spezia, Jul 07 2024