A216211 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 4 columns.

1, 4, 28, 178, 1008, 5493, 29879, 163357, 895519, 4911542, 26932856, 147666219, 809584243, 4438588016, 24334993398, 133419407518, 731487440774, 4010463570150, 21987820817522, 120550714106036, 660932932241338, 3623639639745022, 19867014703421770, 108923158026586497, 597183548915194615

Offset

1,2

Comments

As n increases, the ratio of a(n)/a(n-1) appears to converge to around 5.483.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

Formula

Conjectures from Colin Barker, Nov 18 2017: (Start)

G.f.: x*(1 - 8*x + 34*x^2 - 66*x^3 + 21*x^4 + 85*x^5 - 64*x^6 - 45*x^7 + 26*x^8 + 11*x^9 - 3*x^10 - x^11) / ((1 - 8*x + 15*x^2 - 5*x^3 - 9*x^4 + 2*x^5 + x^6)*(1 - 4*x + 7*x^2 - 3*x^3 - 7*x^4 + 2*x^5 + x^6)).

a(n) = 12*a(n-1) - 54*a(n-2) + 124*a(n-3) - 133*a(n-4) - 16*a(n-5) + 175*a(n-6) - 94*a(n-7) - 69*a(n-8) + 40*a(n-9) + 12*a(n-10) - 4*a(n-11) - a(n-12) for n>12.

(End)

Example

For n=2, using the notation D(own), R(ight), L(eft), U(p), the 4 walks are {D, RDL, RRDLL, RRRDLLL}.

Mathematica

a[n_] := Block[{t=0, w, b=Array[1&, {n, 4}]}, w[rr_, cc_] := Block[{r, c}, If[rr+cc == 2, t++, Do[{r, c} = {rr, cc} + e; If[0<c<5 && 0<r<=n && b[[r, c]] > 0, b[[r, c]] = 0; w[r, c]; b[[r, c]] = 1], {e, {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}}]]]; b[[n, 1]] = 0; w[n, 1]; t]; a /@ Range[6] (* Giovanni Resta, Mar 13 2013 *)

Crossrefs

Column 4 of A271465. Cf. A005409 for grids with 3 rows, A006189 for grids with 3 columns, and A214931 for grids with 4 rows.

Sequence in context: A026298 A181895 A264707 * A366810 A219405 A001396

Adjacent sequences: A216208 A216209 A216210 * A216212 A216213 A216214

Keyword

nonn,walk

Author

Toby Gottfried, Mar 13 2013

Extensions

a(13)-a(14) from Giovanni Resta, Mar 13 2013

Terms a(15) and beyond from Andrew Howroyd, Apr 08 2016

Status

approved