login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006189 Number of self-avoiding 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 non-self-intersecting (or self-avoiding) paths from upper-left to lower-left 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), 163-178.

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(n-1) - 3*a(n-2) + 2*a(n-3) + a(n-4) 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 upper-left to lower-left path-counting 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 06:24 EDT 2017. Contains 292502 sequences.