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. (Formerly M3418)

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,3

Comments

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

References

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

Links

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.

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

Formula

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

Mathematica

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

Prog

(PARI) a(n)=polcoeff(1+x*(1+x)/(1-3*x+x^2+x^3)+x*O(x^n), n) \\ Paul D. Hanna
(Haskell)
a005409 n = a005409_list !! (n-1)
a005409_list = 1 : scanl1 (+) (tail a001333_list)
-- Reinhard Zumkeller, Jul 08 2012
(Magma) [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
(Sage) [1]+[lucas_number1(n, 2, -1) -1 for n in (2..35)] # G. C. Greubel, Apr 22 2021

Crossrefs

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

Sequence in context: A099326 A127985 A339252 * A245124 A020964 A113067

Adjacent sequences: A005406 A005407 A005408 * A005410 A005411 A005412

Keyword

nonn,easy,nice

Author

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

Extensions

Additional comments from Barry E. Williams

Status

approved