OFFSET
1,2
COMMENTS
The recurrence of Giovanni Resta and g.f. of Bruno Berselli are correct for all n. Proof sketch: a SAW from NW to SW in the 4 X n grid is a simple path between two fixed left-boundary terminals, enumerated by a transfer matrix on the non-crossing boundary-connectivity states of the 4-slot vertical cut (each state records, per row, an empty slot, a stub linked through the left to the source or to the target, or a pair of slots joined by a left-closed arc); adding a column rebuilds the full local graph and rejects any cycle, any cell of degree > 2, and any dead end. Summing the width-resolved completions gives a(n) = e^T A^(n-1) w_1 for an explicit augmented operator A and seed vector w_1. The exact minimal polynomial of w_1 under A is x^5 - 7*x^4 + 12*x^3 - 7*x^2 + 3*x + 2, which is precisely the characteristic polynomial of Resta's recurrence (and the reciprocal of Berselli's g.f. denominator); since p(A)*w_1 = 0, a(n) = 7*a(n-1) - 12*a(n-2) + 7*a(n-3) - 3*a(n-4) - 2*a(n-5) for all n >= 6, and the seeds match. - Yiming Beckmann, Jun 06 2026
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..100
FORMULA
Recurrence: a(1,...,5) = (1, 8, 38, 178, 844), a(n) = 7*a(n-1) - 12*a(n-2) + 7*a(n-3) - 3*a(n-4) - 2*a(n-5). - Giovanni Resta, Mar 13 2013
G.f.: x*(1+x-6*x^2+x^3+x^4)/(1-7*x+12*x^2-7*x^3+3*x^4+2*x^5). - Bruno Berselli, Mar 13 2013
EXAMPLE
For n=2, and moves U(p), D(own), R(ight), L(eft), the a(2)=8 walks are {DDD, DRDDL, DRDLD, DDRDL, RDDDL, RDDLD, RDLDD, RDLDRDL} with only the last touching all 8 squares of the grid.
Illustration of the 8 walks of a(2):
.__ __ __ . . . . __
__| . | . | |__ |__ | . | . __|
| . __| . | __| . | |__ | . |__
| . | . __| | . __| __| | . __|
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Toby Gottfried, Mar 09 2013
EXTENSIONS
Missing a(7) and a(13)-a(14) from Giovanni Resta, Mar 13 2013
a(15)-a(24) from Andrew Howroyd, Apr 08 2016
STATUS
approved