|
| |
|
|
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)
|
|
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 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 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), 163-178.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 4*a(n-1) - 3*a(n-2) + 2*a(n-3) + a(n-4) 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
a(n) = (1/2)*( ChebyshevU(n, 1/2) - ChebyshevU(n-1, 1/2) + i^n*( ChebyshevU(n, -3*i/2) + i*ChebyshevU(n-1, -3*i/2) ) ). - G. C. Greubel, May 24 2021
|
|
|
MATHEMATICA
|
LinearRecurrence[{4, -3, 2, 1}, {1, 1, 3, 11, 38}, 100] (* Jean-François Alcover, Oct 08 2017 *)
With[{U = ChebyshevU}, Table[(1/2)*(U[n, 1/2] -U[n-1, 1/2] + I^n*(U[n, -3*I/2] + I*U[n-1, -3*I/2]) ), {n, 0, 40}]] (* G. C. Greubel, May 24 2021 *)
|
|
|
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
(Magma) I:=[1, 3, 11, 38]; [1] cat [n le 4 select I[n] else 4*Self(n-1) -3*Self(n-2) +2*Self(n-3) +Self(n-4): n in [1..41]]; // G. C. Greubel, May 24 2021
(Sage)
u=chebyshev_U;
[(1/2)*( u(n, 1/2) - u(n-1, 1/2) + i^n*(u(n, -3*i/2) + i*u(n-1, -3*i/2)) ) for n in (0..30)] # G. C. Greubel, May 24 2021
|
|
|
CROSSREFS
|
Cf. A216211 (grids with 4 columns).
|
|
|
KEYWORD
|
nonn,walk,easy
|
|
|
AUTHOR
|
|
|
|
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
|
| |
|
|
