cp's OEIS Frontend

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.

%I A006189 M2891 #70 Sep 08 2022 08:44:34
%S A006189 1,1,3,11,38,126,415,1369,4521,14933,49322,162900,538021,1776961,
%T A006189 5868903,19383671,64019918,211443426,698350195,2306494009,7617832221,
%U A006189 25159990673,83097804242,274453403400,906458014441,2993827446721,9887940354603,32657648510531
%N 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.
%C A006189 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
%D A006189 H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
%D A006189 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006189 Andrew Howroyd, <a href="/A006189/b006189.txt">Table of n, a(n) for n = 0..100</a>
%H A006189 H. L. Abbott and D. Hanson, <a href="/A006189/a006189.pdf">A lattice path problem</a>, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)
%H A006189 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3,2,1).
%F A006189 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
%F A006189 G.f.: (1-x)*(1-2*x)/((1 - x + x^2)*(1 - 3*x - x^2)). - _Colin Barker_, Nov 17 2017
%F A006189 2*a(n) = A010892(n) + A052924(n). - _R. J. Mathar_, Sep 27 2020
%F A006189 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
%t A006189 LinearRecurrence[{4,-3,2,1}, {1,1,3,11,38}, 100] (* _Jean-François Alcover_, Oct 08 2017 *)
%t A006189 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 *)
%o A006189 (PARI) Vec((1-x)*(1-2*x)/((1-x+x^2)*(1-3*x-x^2)) + O(x^40)) \\ _Colin Barker_, Nov 17 2017
%o A006189 (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
%o A006189 (Sage)
%o A006189 u=chebyshev_U;
%o A006189 [(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
%Y A006189 Column 3 of A271465.
%Y A006189 Cf. A005409 (grids with 3 rows), A001333.
%Y A006189 Cf. A214931 (grids with 4 rows).
%Y A006189 Cf. A216211 (grids with 4 columns).
%K A006189 nonn,walk,easy
%O A006189 0,3
%A A006189 _N. J. A. Sloane_
%E A006189 Based on upper-left to lower-left path-counting program, more terms from _Toby Gottfried_, Mar 04 2013
%E A006189 Name clarified, offset changed, a(16)-a(25) from _Andrew Howroyd_, Apr 07 2016
%E A006189 a(0)=1 prepended by _Colin Barker_, Nov 17 2017