|
%I M3418 #136 Aug 01 2023 09:55:57
%S 1,1,4,11,28,69,168,407,984,2377,5740,13859,33460,80781,195024,470831,
%T 1136688,2744209,6625108,15994427,38613964,93222357,225058680,
%U 543339719,1311738120,3166815961,7645370044,18457556051,44560482148,107578520349,259717522848
%N 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.
%C Starting with n=1, the sum of the antidiagonals of the array in a comment from Cloitre regarding A002002. - _Gerald McGarvey_, Aug 12 2004
%C Cumulative sum of A001333. - _Sture Sjöstedt_, Nov 15 2011
%C 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
%C 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
%C 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
%C For n > 1, also the rank of the (n-1)-Pell graph. - _Eric W. Weisstein_, Aug 01 2023
%D R. Courant and H. Robbins, What is Mathematics?, Oxford Univ. Press, 1941, p. 103.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A005409/b005409.txt">Table of n, a(n) for n = 1..300</a>
%H Bill Allombert, Nicolas Brisebarre, and Alain Lasjaunias. <a href="https://doi.org/10.1007/s11139-017-9892-7">On a two-valued sequence and related continued fractions in power series fields</a>, The Ramanujan Journal 45.3 (2018): 859-871. See Theorem 3.
%H M. Bicknell, <a href="http://www.fq.math.ca/Scanned/13-4/bicknell.pdf">A Primer on the Pell Sequence and related sequences</a>, Fibonacci Quarterly, Vol. 13, No. 4, 1975, pp. 345-349.
%H Georg Cantor, <a href="http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002155583">Ueber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen</a>. Journal für die reine und angewandte Mathematik 77 (1874), 258-262. English translation by Christopher P. Grant: <a href="https://srjcstaff.santarosa.edu/~jomartin/IrratFiles/Cantors1874Paper.pdf">On a Property of the Class of All Real Algebraic Numbers</a>.
%H S. M. Diano, <a href="/A005409/a005409.pdf">Letter to N. J. A. Sloane</a>
%H A. F. Horadam, <a href="http://www.fq.math.ca/Scanned/5-5/horadam.pdf">Special properties of the sequence W_n(a,b; p,q)</a>, Fib. Quart., 5.5 (1967), 424-434.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H Gy. Tasi and F. Mizukami, <a href="http://dx.doi.org/10.1023/A:1019163812482">Quantum algebraic-combinatoric study of the conformational properties of n-alkanes</a>, J. Math. Chemistry, 25, 1999, 55-64 (see p. 63).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PellGraph.html">Pell Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphRank.html">Graph Rank</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-1).
%F a(n) = A000129(n) - 1, n > 1.
%F a(n) = ((1+sqrt(2))^n - (1-sqrt(2))^n)/(2*sqrt(2))-1 for n > 1, a(1)=1.
%F G.f.: 1 + x*(1+x)/( (1-x)*(1-2*x-x^2) ). - _Simon Plouffe_ in his 1992 dissertation.
%F a(n) = 3*a(n-1) - a(n-2) - a(n-3). - _Toby Gottfried_, Mar 08 2013
%F (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
%F E.g.f.: 1 + exp(x)*(2*(cosh(sqrt(2)*x) - 1) + sqrt(2)*sinh(sqrt(2)*x))/2. - _Stefano Spezia_, Jun 26 2022
%t 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 *)
%t Join[{1}, CoefficientList[Series[(x + 1)/((x - 1) (x^2 + 2 x - 1)), {x, 0, 40}], x]] (* _Vladimir Joseph Stephan Orlovsky_, Jan 21 2012 *)
%t Join[{1}, Fibonacci[Range[2, 35], 2] -1] (* _G. C. Greubel_, Apr 22 2021 *)
%t Join[{1}, LinearRecurrence[{3, -1, -1}, {1, 4, 11}, 20]] (* _Eric W. Weisstein_, Aug 01 2023 *)
%o (PARI) a(n)=polcoeff(1+x*(1+x)/(1-3*x+x^2+x^3)+x*O(x^n),n) \\ _Paul D. Hanna_
%o (Haskell)
%o a005409 n = a005409_list !! (n-1)
%o a005409_list = 1 : scanl1 (+) (tail a001333_list)
%o -- _Reinhard Zumkeller_, Jul 08 2012
%o (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
%o (Sage) [1]+[lucas_number1(n,2,-1) -1 for n in (2..35)] # _G. C. Greubel_, Apr 22 2021
%Y Cf. A000129, A001333, A048654, A048655, A048745.
%Y Cf. A214931 (walks on grids with 4 rows), A006189 (grids with 3 columns).
%Y Cf. A216211 (grids with 4 columns).
%K nonn,easy,nice
%O 1,3
%A _N. J. A. Sloane_, S. M. Diano
%E Additional comments from _Barry E. Williams_
|
