A214931 -id:A214931 - cp's OEIS frontend

A005409 Number of polynomials of height n: a(1)=1, a(2)=1, a(3)=4, a(n) = 2*a(n-1) + a(n-2) + 2 for n >= 4.

1, 1, 4, 11, 28, 69, 168, 407, 984, 2377, 5740, 13859, 33460, 80781, 195024, 470831, 1136688, 2744209, 6625108, 15994427, 38613964, 93222357, 225058680, 543339719, 1311738120, 3166815961, 7645370044, 18457556051, 44560482148, 107578520349, 259717522848

Offset: 1

N. J. A. Sloane, S. M. Diano

Starting with n=1, the sum of the antidiagonals of the array in a comment from Cloitre regarding A002002. - Gerald McGarvey, Aug 12 2004
Cumulative sum of A001333. - Sture Sjöstedt, Nov 15 2011
a(n) is the number of self-avoiding walks on a 3 rows X n columns grid of squares, starting top-left, ending bottom-left, using moves of R(ight), L(eft), U(p), D(own). E.g., for 3 X 1 there is just the path (D,D), and a(1) = 1. For 3 X 2, there are 4 paths (D,D) (D,R,D,L) (R,D,D,L) and (R,D,L,D) and a(2) = 4. - Toby Gottfried, Mar 04 2013
Define a triangle to have T(n,1) = n*(n-1)+1 and T(n,n) = n; the other terms T(r,c) = T(r-1,c) + T(r-1,c-1) + T(r-2,c-1). The sum of the terms in row(n+1) minus those in row(n) = a(n+2). - J. M. Bergot, Apr 30 2013
Since the terms of the sequence are all finite, it can be used in enumerating all polynomials with integer coefficients. Since each polynomial has only a finite number of roots, this enumeration can be used in turn to enumerate the algebraic numbers. Cantor uses this to derive the existence of transcendental numbers as a corollary of his stronger result that no enumerable sequence of real numbers can include all of them. - Morgan L. Owens, May 15 2022
For n > 1, also the rank of the (n-1)-Pell graph. - Eric W. Weisstein, Aug 01 2023

R. Courant and H. Robbins, What is Mathematics?, Oxford Univ. Press, 1941, p. 103.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..300
Bill Allombert, Nicolas Brisebarre, and Alain Lasjaunias. On a two-valued sequence and related continued fractions in power series fields, The Ramanujan Journal 45.3 (2018): 859-871. See Theorem 3.
M. Bicknell, A Primer on the Pell Sequence and related sequences, Fibonacci Quarterly, Vol. 13, No. 4, 1975, pp. 345-349.
Georg Cantor, Ueber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen. Journal für die reine und angewandte Mathematik 77 (1874), 258-262. English translation by Christopher P. Grant: On a Property of the Class of All Real Algebraic Numbers.
S. M. Diano, Letter to N. J. A. Sloane
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434.
El-Mehdi Mehiri, Saad Mneimneh, and Hacène Belbachir, The Towers of Fibonacci, Lucas, Pell, and Jacobsthal, arXiv:2502.11045 [math.CO], 2025. See p. 12.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Gy. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 63).
Eric Weisstein's World of Mathematics, Pell Graph
Eric Weisstein's World of Mathematics, Graph Rank
Index entries for linear recurrences with constant coefficients, signature (3,-1,-1).

Cf. A000129, A001333, A048654, A048655, A048745.
Cf. A214931 (walks on grids with 4 rows), A006189 (grids with 3 columns).
Cf. A216211 (grids with 4 columns).

a005409 n = a005409_list !! (n-1)
a005409_list = 1 : scanl1 (+) (tail a001333_list)
-- Reinhard Zumkeller, Jul 08 2012

[1] cat [n le 2 select n^2 else 2*Self(n-1) +Self(n-2) +2: n in [1..30]]; // G. C. Greubel, Apr 22 2021

Join[{1}, RecurrenceTable[{a[1] == 1, a[2] == 4, a[n] == 2 a[n - 1] + a[n - 2] + 2}, a[n], {n, 30}]] (* Harvey P. Dale, Jul 27 2011 *)
Join[{1}, CoefficientList[Series[(x + 1)/((x - 1) (x^2 + 2 x - 1)), {x, 0, 40}], x]] (* Vladimir Joseph Stephan Orlovsky, Jan 21 2012 *)
Join[{1}, Fibonacci[Range[2, 35], 2] -1] (* G. C. Greubel, Apr 22 2021 *)
Join[{1}, LinearRecurrence[{3, -1, -1}, {1, 4, 11}, 20]] (* Eric W. Weisstein, Aug 01 2023 *)

a(n)=polcoeff(1+x*(1+x)/(1-3*x+x^2+x^3)+x*O(x^n),n) \\ Paul D. Hanna

[1]+[lucas_number1(n,2,-1) -1 for n in (2..35)] # G. C. Greubel, Apr 22 2021

a(n) = A000129(n) - 1, n > 1.
a(n) = ((1+sqrt(2))^n - (1-sqrt(2))^n)/(2*sqrt(2))-1 for n > 1, a(1)=1.
G.f.: 1 + x*(1+x)/( (1-x)*(1-2*x-x^2) ). - Simon Plouffe in his 1992 dissertation.
a(n) = 3*a(n-1) - a(n-2) - a(n-3). - Toby Gottfried, Mar 08 2013
(1, 4, 11, 28, ...) = (1, 2, 2, 2, ...) * the Pell sequence starting (1, 2, 5, 12, 29, ...); such that, for example: a(5) = (2, 2, 2, 1) dot (1, 2, 5, 12) = (2 + 4 + 10 + 12) = 48. - Gary W. Adamson May 21 2013
E.g.f.: 1 + exp(x)*(2*(cosh(sqrt(2)*x) - 1) + sqrt(2)*sinh(sqrt(2)*x))/2. - Stefano Spezia, Jun 26 2022

Additional comments from Barry E. Williams

A271465 Array read by antidiagonals: T(n,m) = number of self-avoiding walks of any length from NW to SW corners on a grid with n rows and m columns.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 11, 8, 1, 1, 5, 28, 38, 16, 1, 1, 6, 69, 178, 126, 32, 1, 1, 7, 168, 844, 1008, 415, 64, 1, 1, 8, 407, 4012, 8590, 5493, 1369, 128, 1, 1, 9, 984, 19072, 74148, 81445, 29879, 4521, 256, 1

Offset: 1

Andrew Howroyd, Apr 08 2016

			The start of the sequence as table:
*  1   1    1     1        1         1         1 ...
*  1   2    3     4        5         6         7 ...
*  1   4   11    28       69       168       407 ...
*  1   8   38   178      844      4012     19072 ...
*  1  16  126  1008     8590     74148    638472 ...
*  1  32  415  5493    81445   1246850  19011465 ...
*  1  64 1369  29879  761047  20477490 550254085 ...
*  ...

Andrew Howroyd, Table of n, a(n) for n = 1..378

Main diagonal is A271507. Rows include A005409, A214931. Columns include A006189, A216211. Cf. A064298 (paths from NW to SE).

T(1,n)=1, T(2,n)=n, T(n,1)=1, T(n,2)=2^(n-1).

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.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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

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).

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), 163-178. (Annotated scanned copy)
Index entries for linear recurrences with constant coefficients, signature (4,-3,2,1).

Column 3 of A271465.
Cf. A005409 (grids with 3 rows), A001333.
Cf. A214931 (grids with 4 rows).
Cf. A216211 (grids with 4 columns).

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

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 *)

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

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

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
2*a(n) = A010892(n) + A052924(n). - R. J. Mathar, Sep 27 2020
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

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
a(0)=1 prepended by Colin Barker, Nov 17 2017

A216211 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 4 columns.

Original entry on oeis.org

1, 4, 28, 178, 1008, 5493, 29879, 163357, 895519, 4911542, 26932856, 147666219, 809584243, 4438588016, 24334993398, 133419407518, 731487440774, 4010463570150, 21987820817522, 120550714106036, 660932932241338, 3623639639745022, 19867014703421770, 108923158026586497, 597183548915194615

Offset: 1

Toby Gottfried, Mar 13 2013

As n increases, the ratio of a(n)/a(n-1) appears to converge to around 5.483.

			For n=2, using the notation D(own), R(ight), L(eft), U(p), the 4 walks are {D, RDL, RRDLL, RRRDLLL}.

Andrew Howroyd, Table of n, a(n) for n = 1..100

Column 4 of A271465. Cf. A005409 for grids with 3 rows, A006189 for grids with 3 columns, and A214931 for grids with 4 rows.

a[n_] := Block[{t=0,w,b=Array[1&, {n,4}]}, w[rr_,cc_] := Block[{r,c}, If[rr+cc == 2, t++, Do[{r,c} = {rr,cc} + e; If[0 0, b[[r,c]] = 0; w[r, c]; b[[r,c]] = 1], {e, {{-1,0}, {1,0}, {0,1}, {0,-1}}}]]]; b[[n,1]] = 0; w[n,1]; t]; a /@ Range[6] (* Giovanni Resta, Mar 13 2013 *)

Conjectures from Colin Barker, Nov 18 2017: (Start)
G.f.: x*(1 - 8*x + 34*x^2 - 66*x^3 + 21*x^4 + 85*x^5 - 64*x^6 - 45*x^7 + 26*x^8 + 11*x^9 - 3*x^10 - x^11) / ((1 - 8*x + 15*x^2 - 5*x^3 - 9*x^4 + 2*x^5 + x^6)*(1 - 4*x + 7*x^2 - 3*x^3 - 7*x^4 + 2*x^5 + x^6)).
a(n) = 12*a(n-1) - 54*a(n-2) + 124*a(n-3) - 133*a(n-4) - 16*a(n-5) + 175*a(n-6) - 94*a(n-7) - 69*a(n-8) + 40*a(n-9) + 12*a(n-10) - 4*a(n-11) - a(n-12) for n>12.
(End)

a(13)-a(14) from Giovanni Resta, Mar 13 2013

Terms a(15) and beyond from Andrew Howroyd, Apr 08 2016

cp's OEIS Frontend

A005409 Number of polynomials of height n: a(1)=1, a(2)=1, a(3)=4, a(n) = 2*a(n-1) + a(n-2) + 2 for n >= 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Sage

Formula

Extensions

A271465 Array read by antidiagonals: T(n,m) = number of self-avoiding walks of any length from NW to SW corners on a grid with n rows and m columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

Extensions

A216211 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 4 columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions