OFFSET
5,1
COMMENTS
A growing self-avoiding walk (GSAW) is a walk on a graph that is directed, does not visit the same vertex twice, and for which all neighbors of the endpoint are part of the walk, i.e., the endpoint is trapped. This sequence is about GSAWs on the grid graph of integer points (x,y) where x >= 0 and y is in {0,1,2,3}. The GSAW must start at the point (0,0). The length of a GSAW is the number of edges.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 5..1000
Jay Pantone, Alexander R. Klotz, and Everett Sullivan, Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height., arXiv:2407.18205 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (2,4,-5,-9,-5, 20,17,-9,-41,-11, 66,41,-53,-103,10, 102,91,-54,-130, -51,134,73,-104, -90,67,177,-17,-165, -72,44,129,38,-69, -34,-24,28,32,-8,-8).
FORMULA
G.f.: -x^5*(12*x^39 + 14*x^38 - 20*x^37 - 18*x^36 - 45*x^35 - 12*x^34 + 107*x^33 - 38*x^32 + 3*x^31 - 49*x^30 - 38*x^29 + 242*x^28 - 11*x^27 - 66*x^26 - 181*x^25 - 144*x^24 + 246*x^23 + 91*x^22 + 72*x^21 - 208*x^20 - 150*x^19 + 98*x^18 + 57*x^17 + 143*x^16 - 74*x^15 + 5*x^14 - 21*x^13 + 28*x^12 - 17*x^11 - 55*x^10 - 17*x^9 + 22*x^8 + 45*x^7 + 10*x^6 - 19*x^5 - 21*x^4 + 3*x^3 + 7*x^2 + 4*x - 3)/((2*x^19 + 2*x^18 - 7*x^17 - 6*x^16 + 5*x^15 + 8*x^14 + 7*x^13 - 17*x^12 - 8*x^11 + 3*x^10 + 10*x^9 + 3*x^8 - 8*x^7 + 2*x^6 - x^5 + 6*x^4 - 3*x^3 - 2*x + 1)*(4*x^20 - 2*x^18 - 5*x^16 + 8*x^14 - x^12 + 2*x^10 - 4*x^8 + 2*x^6 + 3*x^4 - 4*x^2 + 1)).
EXAMPLE
The a(5) = 3 walks are:
*--* * * * * * * *
|
*--* * *--* * * * *
| | |
* * * * * * *--*--*
| | | |
* * * *--* * * *--*
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Jay Pantone, Jul 15 2024
EXTENSIONS
More terms from Andrew Howroyd, Oct 30 2025
STATUS
approved