

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)


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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 number of paths in 3x3 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 = 1..100


FORMULA

Empirical recurrence: a(n) = 4*a(n1)  3*a(n2) + 2*a(n3) + a(n4) for n > 4.  Giovanni Resta, Mar 13 2013


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


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


STATUS

approved



