

A006189


Number of selfavoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 3 columns.
(Formerly M2891)


8



1, 1, 3, 11, 38, 126, 415, 1369, 4521, 14933, 49322, 162900, 538021, 1776961, 5868903, 19383671, 64019918, 211443426, 698350195, 2306494009, 7617832221, 25159990673, 83097804242, 274453403400, 906458014441, 2993827446721, 9887940354603, 32657648510531
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

a(n) = number of nonselfintersecting (or selfavoiding) paths from upperleft to lowerleft of a grid of squares with 3 columns and n rows. E.g., for 3 columns and 2 rows, the paths are D, RDL, and RRDLL and the second a(n) = 3. The next a(n) = 11, which is the number of paths in a 3 X 3 grid: DD, DRDL, DRRDLL, DRURDDLL, RDDL, RDRDLL, RDLD, RRDDLL, RRDDLULD, RRDLDL, RRDLLD (where R=right, L=left, D=down, U=up).  Toby Gottfried, Mar 04 2013


REFERENCES

H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163178.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..100
H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163178. (Annotated scanned copy)
Index entries for linear recurrences with constant coefficients, signature (4,3,2,1).


FORMULA

a(n) = 4*a(n1)  3*a(n2) + 2*a(n3) + a(n4) for n > 3.  Giovanni Resta, Mar 13 2013
G.f.: (1  x)*(1  2*x) / ((1  x + x^2)*(1  3*x  x^2)).  Colin Barker, Nov 17 2017


MATHEMATICA

(* Checked against 100 terms of bfile *) LinearRecurrence[{4, 3, 2, 1}, {1, 3, 11, 38}, 100] (* JeanFrançois Alcover, Oct 08 2017 *)


PROG

(PARI) Vec((1  x)*(1  2*x) / ((1  x + x^2)*(1  3*x  x^2)) + O(x^40)) \\ Colin Barker, Nov 17 2017


CROSSREFS

Column 3 of A271465.
Cf. A005409 (grids with 3 rows), A001333.
Cf. A214931 (grids with 4 rows).
Cf. A216211 (grids with 4 columns).
Sequence in context: A265796 A129962 A026361 * A092201 A273526 A026943
Adjacent sequences: A006186 A006187 A006188 * A006190 A006191 A006192


KEYWORD

nonn,walk,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

Based on upperleft to lowerleft pathcounting program, more terms from Toby Gottfried, Mar 04 2013
Name clarified, offset changed, a(16)a(25) from Andrew Howroyd, Apr 07 2016
a(0)=1 prepended by Colin Barker, Nov 17 2017


STATUS

approved



