%I M1439 N0569 #828 Oct 22 2024 16:02:55

%S 1,1,2,5,13,34,89,233,610,1597,4181,10946,28657,75025,196418,514229,

%T 1346269,3524578,9227465,24157817,63245986,165580141,433494437,

%U 1134903170,2971215073,7778742049,20365011074,53316291173,139583862445,365435296162,956722026041

%N a(n) = 3*a(n-1) - a(n-2) for n >= 2, with a(0) = a(1) = 1.

%C This is a bisection of the Fibonacci sequence A000045. a(n) = F(2*n-1), with F(n) = A000045(n) and F(-1) = 1.

%C Number of ordered trees with n+1 edges and height at most 3 (height=number of edges on a maximal path starting at the root). Number of directed column-convex polyominoes of area n+1. Number of nondecreasing Dyck paths of length 2n+2. - _Emeric Deutsch_, Jul 11 2001

%C Terms are the solutions x to: 5x^2-4 is a square, with 5x^2-4 in A081071 and sqrt(5x^2-4) in A002878. - _Benoit Cloitre_, Apr 07 2002

%C a(0) = a(1) = 1, a(n+1) is the smallest Fibonacci number greater than the n-th partial sum. - _Amarnath Murthy_, Oct 21 2002

%C The fractional part of tau*a(n) decreases monotonically to zero. - _Benoit Cloitre_, Feb 01 2003

%C Numbers k such that floor(phi^2*k^2) - floor(phi*k)^2 = 1 where phi=(1+sqrt(5))/2. - _Benoit Cloitre_, Mar 16 2003

%C Number of leftist horizontally convex polyominoes with area n+1.

%C Number of 31-avoiding words of length n on alphabet {1,2,3} which do not end in 3. (E.g., at n=3, we have 111, 112, 121, 122, 132, 211, 212, 221, 222, 232, 321, 322 and 332.) See A028859. - _Jon Perry_, Aug 04 2003

%C Appears to give all solutions > 1 to the equation: x^2 = ceiling(x*r*floor(x/r)) where r=phi=(1+sqrt(5))/2. - _Benoit Cloitre_, Feb 24 2004

%C a(1) = 1, a(2) = 2, then the least number such that the square of any term is just less than the geometric mean of its neighbors. a(n+1)*a(n-1) > a(n)^2. - _Amarnath Murthy_, Apr 06 2004

%C All positive integer solutions of Pell equation b(n)^2 - 5*a(n+1)^2 = -4 together with b(n)=A002878(n), n >= 0. - _Wolfdieter Lang_, Aug 31 2004

%C Essentially same as Pisot sequence E(2,5).

%C Number of permutations of [n+1] avoiding 321 and 3412. E.g., a(3) = 13 because the permutations of [4] avoiding 321 and 3412 are 1234, 2134, 1324, 1243, 3124, 2314, 2143, 1423, 1342, 4123, 3142, 2413, 2341. - _Bridget Tenner_, Aug 15 2005

%C Number of 1324-avoiding circular permutations on [n+1].

%C A subset of the Markoff numbers (A002559). - _Robert G. Wilson v_, Oct 05 2005

%C (x,y) = (a(n), a(n+1)) are the solutions of x/(yz) + y/(xz) + z/(xy) = 3 with z=1. - _Floor van Lamoen_, Nov 29 2001

%C Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 1. - _Herbert Kociemba_, Jun 10 2004

%C With interpolated zeros, counts closed walks of length n at the start or end node of P_4. a(n) counts closed walks of length 2n at the start or end node of P_4. The sequence 0,1,0,2,0,5,... counts walks of length n between the start and second node of P_4. - _Paul Barry_, Jan 26 2005

%C a(n) is the number of ordered trees on n edges containing exactly one non-leaf vertex all of whose children are leaves (every ordered tree must contain at least one such vertex). For example, a(0) = 1 because the root of the tree with no edges is not considered to be a leaf and the condition "all children are leaves" is vacuously satisfied by the root and a(4) = 13 counts all 14 ordered trees on 4 edges (A000108) except (ignore dots)

%C |..|

%C .\/.

%C which has two such vertices. - _David Callan_, Mar 02 2005

%C Number of directed column-convex polyominoes of area n. Example: a(2)=2 because we have the 1 X 2 and the 2 X 1 rectangles. - _Emeric Deutsch_, Jul 31 2006

%C Same as the number of Kekulé structures in polyphenanthrene in terms of the number of hexagons in extended (1,1)-nanotubes. See Table 1 on page 411 of I. Lukovits and D. Janezic. - _Parthasarathy Nambi_, Aug 22 2006

%C Number of free generators of degree n of symmetric polynomials in 3-noncommuting variables. - _Mike Zabrocki_, Oct 24 2006

%C Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5)*a(n) + sqrt(5*a(n)^2 - 4))/2) = n for n >= 1. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007

%C Consider a teacher who teaches one student, then he finds he can teach two students while the original student learns to teach a student. And so on with every generation an individual can teach one more student then he could before. a(n) starting at a(2) gives the total number of new students/teachers (see program). - _Ben Paul Thurston_, Apr 11 2007

%C The Diophantine equation a(n)=m has a solution (for m >= 1) iff ceiling(arcsinh(sqrt(5)*m/2)/log(phi)) != ceiling(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130255(m)=A130256(m). - _Hieronymus Fischer_, May 24 2007

%C a(n+1) = B^(n)(1), n >= 0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 2=`0`, 5=`00`, 13=`000`, ..., in Wythoff code.

%C Bisection of the Fibonacci sequence into odd-indexed nonzero terms (1, 2, 5, 13, ...) and even-indexed terms (1, 3, 8, 21, ...) may be represented as row sums of companion triangles A140068 and A140069. - _Gary W. Adamson_, May 04 2008

%C a(n) is the number of partitions pi of [n] (in standard increasing form) such that Flatten[pi] is a (2-1-3)-avoiding permutation. Example: a(4)=13 counts all 15 partitions of [4] except 13/24 and 13/2/4. Here "standard increasing form" means the entries are increasing in each block and the blocks are arranged in increasing order of their first entries. Also number that avoid 3-1-2. - _David Callan_, Jul 22 2008

%C Let P be the partial sum operator, A000012: (1; 1,1; 1,1,1; ...) and A153463 = M, the partial sum & shift operator. It appears that beginning with any randomly taken sequence S(n), iterates of the operations M * S(n), -> M * ANS, -> P * ANS, etc. (or starting with P) will rapidly converge upon a two-sequence limit cycle of (1, 2, 5, 13, 34, ...) and (1, 1, 3, 8, 21, ...). - _Gary W. Adamson_, Dec 27 2008

%C Number of musical compositions of Rhythm-music over a time period of n-1 units. Example: a(4)=13; indeed, denoting by R a rest over a time period of 1 unit and by N[j] a note over a period of j units, we have (writing N for N[1]): NNN, NNR, NRN, RNN, NRR, RNR, RRN, RRR, N[2]R, RN[2], NN[2], N[2]N, N[3] (see the J. Groh reference, pp. 43-48). - Juergen K. Groh (juergen.groh(AT)lhsystems.com), Jan 17 2010

%C Given an infinite lower triangular matrix M with (1, 2, 3, ...) in every column but the leftmost column shifted upwards one row. Then (1, 2, 5, ...) = lim_{n->infinity} M^n. (Cf. A144257.) - _Gary W. Adamson_, Feb 18 2010

%C As a fraction: 8/71 = 0.112676 or 98/9701 = 0.010102051334... (fraction 9/71 or 99/9701 for sequence without initial term). 19/71 or 199/9701 for sequence in reverse. - _Mark Dols_, May 18 2010

%C For n >= 1, a(n) is the number of compositions (ordered integer partitions) of 2n-1 into an odd number of odd parts. O.g.f.: (x-x^3)/(1-3x^2+x^4) = A(A(x)) where A(x) = 1/(1-x)-1/(1-x^2).

%C For n > 0, determinant of the n X n tridiagonal matrix with 1's in the super and subdiagonals, (1,3,3,3,...) in the main diagonal, and the rest zeros. - _Gary W. Adamson_, Jun 27 2011

%C The Gi3 sums, see A180662, of the triangles A108299 and A065941 equal the terms of this sequence without a(0). - _Johannes W. Meijer_, Aug 14 2011

%C The number of permutations for which length equals reflection length. - _Bridget Tenner_, Feb 22 2012

%C Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n+1, with exactly 2 elements of each rank between 0 and 1. (Uniform used in the sense of Retakh, Serconek and Wilson. Graded used in R. Stanley's sense that all maximal chains have the same length.)

%C HANKEL transform of sequence and the sequence omitting a(0) is the sequence A019590(n). This is the unique sequence with that property. - _Michael Somos_, May 03 2012

%C The number of Dyck paths of length 2n and height at most 3. - _Ira M. Gessel_, Aug 06 2012

%C Pisano period lengths: 1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, ... - _R. J. Mathar_, Aug 10 2012

%C Primes in the sequence are 2, 5, 13, 89, 233, 1597, 28657, ... (apparently A005478 without the 3). - _R. J. Mathar_, May 09 2013

%C a(n+1) is the sum of rising diagonal of the Pascal triangle written as a square - cf. comments in A085812. E.g., 13 = 1+5+6+1. - _John Molokach_, Sep 26 2013

%C a(n) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 1, 1, 1; 0, 1, 1] or [1, 1, 1; 0, 1, 1; 1, 1, 1] or [1, 1, 0; 1, 1, 1; 1, 1, 1] or [1, 0, 1; 1, 1, 1; 1, 1, 1]. - _R. J. Mathar_, Feb 03 2014

%C Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - _Colin Barker_, Feb 04 2014

%C Except for the initial term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 64 = 0. - _Colin Barker_, Feb 16 2014

%C Positive values of x such that there is a y satisfying x^2 - xy - y^2 - 1 = 0. - _Ralf Stephan_, Jun 30 2014

%C a(n) is also the number of permutations simultaneously avoiding 231, 312 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - _Manda Riehl_, Aug 07 2014

%C (1, a(n), a(n+1)), n >= 0, are Markoff triples (see A002559 and _Robert G. Wilson v_'s Oct 05 2005 comment). In the Markoff tree they give one of the outer branches. Proof: a(n)*a(n+1) - 1 = A001906(2*n)^2 = (a(n+1) - a(n))^2 = a(n)^2 + a(n+1)^2 - 2*a(n)*a(n+1), thus 1^2 + a(n)^2 + a(n+1)^2 = 3*a(n)*a(n+1). - _Wolfdieter Lang_, Jan 30 2015

%C For n > 0, a(n) is the smallest positive integer not already in the sequence such that a(1) + a(2) + ... + a(n) is a Fibonacci number. - _Derek Orr_, Jun 01 2015

%C Number of vertices of degree n-2 (n >= 3) in all Fibonacci cubes, see Klavzar, Mollard, & Petkovsek. - _Emeric Deutsch_, Jun 22 2015

%C Except for the first term, this sequence can be generated by Corollary 1 (ii) of Azarian's paper in the references for this sequence. - _Mohammad K. Azarian_, Jul 02 2015

%C Precisely the numbers F(n)^k + F(n+1)^k that are also Fibonacci numbers with k > 1, see Luca & Oyono. - _Charles R Greathouse IV_, Aug 06 2015

%C a(n) = MA(n) - 2*(-1)^n where MA(n) is exactly the maximum area of a quadrilateral with lengths of sides in order L(n-2), L(n-2), F(n+1), F(n+1) for n > 1 and L(n)=A000032(n). - _J. M. Bergot_, Jan 28 2016

%C a(n) is the number of bargraphs of semiperimeter n+1 having no valleys (i.e., convex bargraphs). Equivalently, number of bargraphs of semiperimeter n+1 having exactly 1 peak. Example: a(5) = 34 because among the 35 (=A082582(6)) bargraphs of semiperimeter 6 only the one corresponding to the composition [2,1,2] has a valley. - _Emeric Deutsch_, Aug 12 2016

%C Integers k such that the fractional part of k*phi is less than 1/k. See Byszewski link p. 2. - _Michel Marcus_, Dec 10 2016

%C Number of words of length n-1 over {0,1,2,3} in which binary subwords appear in the form 10...0. - _Milan Janjic_, Jan 25 2017

%C With a(0) = 0 this is the Riordan transform with the Riordan matrix A097805 (of the associated type) of the Fibonacci sequence A000045. See a Feb 17 2017 comment on A097805. - _Wolfdieter Lang_, Feb 17 2017

%C Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) < e(k). [Martinez and Savage, 2.12] - _Eric M. Schmidt_, Jul 17 2017

%C Number of permutations of [n] that avoid the patterns 321 and 2341. - _Colin Defant_, May 11 2018

%C The sequence solves the following problem: find all the pairs (i,j) such that i divides 1+j^2 and j divides 1+i^2. In fact, the pairs (a(n), a(n+1)), n > 0, are all the solutions. - _Tomohiro Yamada_, Dec 23 2018

%C Number of permutations in S_n whose principal order ideals in the Bruhat order are lattices (equivalently, modular, distributive, Boolean lattices). - _Bridget Tenner_, Jan 16 2020

%C From _Wolfdieter Lang_, Mar 30 2020: (Start)

%C a(n) is the upper left entry of the n-th power of the 2 X 2 tridiagonal matrix M_2 = Matrix([1,1], [1,2]) from A322602: a(n) = ((M_2)^n)[1,1].

%C Proof: (M_2)^2 = 3*M + 1_2 (with the 2 X 2 unit matrix 1_2) from the characteristic polynomial of M_2 (see a comment in A322602) and the Cayley-Hamilton theorem. The recurrence M^n = M*M^(n-1) leads to (M_n)^n = S(n, 3)*1_2 + S(n-a, 3)*(M - 3*1_2), for n >= 0, with S(n, 3) = F(2(n+1)) = A001906(n+1). Hence ((M_2)^n)[1,1] = S(n, 3) - 2*S(n-1, 3) = a(n) = F(2*n-1) = (1/(2*r+1))*r^(2*n-1)*(1 + (1/r^2)^(2*n-1)), with r = rho(5) = A001622 (golden ratio) (see the first Aug 31 2004 formula, using the recurrence of S(n, 3), and the _Michael Somos_ Oct 28 2002 formula). This proves a conjecture of _Gary W. Adamson_ in A322602.

%C The ratio a(n)/a(n-1) converges to r^2 = rho(5)^2 = A104457 for n -> infinity (see the a(n) formula in terms of r), which is one of the statements by _Gary W. Adamson_ in A322602. (End)

%C a(n) is the number of ways to stack coins with a bottom row of n coins such that any coin not on the bottom row touches exactly two coins in the row below, and all the coins on any row are contiguous [Wilf, 2.12]. - _Greg Dresden_, Jun 29 2020

%C a(n) is the upper left entry of the (2*n)-th power of the 4 X 4 Jacobi matrix L with L(i,j)=1 if |i-j| = 1 and L(i,j)=0 otherwise. - _Michael Shmoish_, Aug 29 2020

%C All positive solutions of the indefinite binary quadratic F(1, -3, 1) := x^2 - 3*x*y + y^2, of discriminant 5, representing -1 (special Markov triples (1, y=x, z=y) if y <= z) are [x(n), y(n)] = [abs(F(2*n+1)), abs(F(2*n-1))], for n = -infinity..+infinity. (F(-n) = (-1)^(n+1)*F(n)). There is only this single family of proper solutions, and there are no improper solutions. [See also the Floor van Lamoen Nov 29 2001 comment, which uses this negative n, and my Jan 30 2015 comment.] - _Wolfdieter Lang_, Sep 23 2020

%C These are the denominators of the lower convergents to the golden ratio, tau; they are also the numerators of the upper convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - _Clark Kimberling_, Jan 02 2022

%C a(n+1) is the number of subgraphs of the path graph on n vertices. - _Leen Droogendijk_, Jun 17 2023

%C For n > 4, a(n+2) is the number of ways to tile this 3 x n "double-box" shape with squares and dominos (reflections or rotations are counted as distinct tilings). The double-box shape is made up of two horizontal strips of length n, connected by three vertical columns of length 3, and the center column can be located anywhere not touching the two outside columns.

%C _ _ _ _ _ _ _ _ _ _ _ _ _ _

%C |_|_|_|_|_|_|_|_|_|_|_|_|_|_|

%C |_|_ _ _ _|_|_ _ _ _ _ _ _|_|

%C |_|_|_|_|_|_|_|_|_|_|_|_|_|_|. - _Greg Dresden_ and Ruishan Wu, Aug 25 2024

%D R. C. Alperin, A family of nonlinear recurrences and their linear solutions, Fib. Q., 57:4 (2019), 318-321.

%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 13,15.

%D N. G. de Bruijn, D. E. Knuth, and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.

%D GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 92.

%D Jurgen Groh, Computerimprovisation mit Markoffketten und "kognitiven Algorithmen", Studienarbeit, Technische Hochschule Darmstadt, 1987.

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 39.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. Stanley, Enumerative combinatorics, Vol. 1. Cambridge University Press, Cambridge, 1997, pp. 96-100.

%D H. S. Wilf, Generatingfunctionology, 3rd ed., A K Peters Ltd., Wellesley, MA, 2006, p. 41.

%H T. D. Noe, <a href="/A001519/b001519.txt">Table of n, a(n) for n = 0..200</a>

%H H. Acan and P. Hitczenko, <a href="https://arxiv.org/abs/1406.3958">On random trees obtained from permutation graphs</a>, arXiv:1406.3958 [math.CO], 2014-2016.

%H N. Allegra, <a href="http://arxiv.org/abs/1410.4131">Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics</a>, arXiv preprint arXiv:1410.4131 [cond-mat.stat-mech], 2014. See Table 1.

%H W. K. Alt, <a href="http://www.wyattalt.com/static/thesis.pdf">Enumeration of Domino Tilings on the Projective Grid Graph</a>, A Thesis Presented to The Division of Mathematics and Natural Sciences, Reed College, May 2013.

%H Mohammad K. Azarian, <a href="http://www.m-hikari.com/ijcms/ijcms-2012/37-40-2012/azarianIJCMS37-40-2012.pdf">Fibonacci Identities as Binomial Sums</a>, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38, 2012, pp. 1871-1876.

%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating Functions for Generating Trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

%H E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170, 1997, 211-217.

%H E. Barcucci, A. Del Lungo, R. Pinzani, and R. Sprugnoli, <a href="http://www.mat.univie.ac.at/~slc/opapers/s31barc.html">La hauteur des polyominos dirigés verticalement convexes</a>, Séminaire Lotharingien de Combinatoire, B31d (1993), 11 pp.

%H E. Barcucci, R. Pinzani, and R. Sprugnoli, <a href="http://dx.doi.org/10.1007/3-540-56610-4_71">Directed column-convex polyominoes by recurrence relations</a>, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.

%H J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/cartes.pdf">Rooted planar maps modulo some patterns</a>, Preprint 2016.

%H Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1803.06706">Descent distribution on Catalan words avoiding a pattern of length at most three</a>, arXiv:1803.06706 [math.CO], 2018.

%H J.-L. Baril and A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/equivdyck.pdf">Equivalence classes of Dyck paths modulo some statistics</a>, 2014.

%H Jean-Luc Baril, José L. Ramírez, and Lina M. Simbaqueba, <a href="http://jl.baril.u-bourgogne.fr/barasi2.pdf">Equivalence Classes of Skew Dyck Paths Modulo some Patterns</a>, 2021.

%H Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.

%H Paul Barry, <a href="https://arxiv.org/abs/1910.00875">Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials</a>, arXiv:1910.00875 [math.CO], 2019.

%H Paul Barry, <a href="https://arxiv.org/abs/1912.01124">A Note on Riordan Arrays with Catalan Halves</a>, arXiv:1912.01124 [math.CO], 2019.

%H A. M. Baxter and L. K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014.

%H C. Bean, M. Tannock, and H. Ulfarsson, <a href="http://arxiv.org/abs/1512.08155">Pattern avoiding permutations and independent sets in graphs</a>, arXiv:1512.08155 [math.CO], 2015.

%H N. Bergeron, C. Reutenauer, M. Rosas, and M. Zabrocki, <a href="https://arxiv.org/abs/math/0502082">Invariants and coinvariants of the symmetric group in noncommuting variables</a>, arXiv:math/0502082 [math.CO], 2005; Canadian Journal of Mathematics 60:2 (2008), pp. 266-296.

%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.

%H A. Blecher, C. Brennan, and A. Knopfmacher, <a href="http://dx.doi.org/10.1080/0035919X.2015.1059905">Peaks in bargraphs</a>, Trans. Royal Soc. South Africa, 71, No. 1, 2016, 97-103.

%H T. Boothby, J. Burkert, M. Eichwald, D. C. Ernst, R. M. Green, and M. Macauley, <a href="https://doi.org/10.1007/s10801-011-0327-z">On the cyclically fully commutative elements of Coxeter groups</a>, J. Algebr. Comb. 36, No. 1, 123-148 (2012), Table 1 CFC A,B,F.

%H S. Brlek, E. Duchi, E. Pergola, and S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.019">On the equivalence problem for succession rules</a>, Discr. Math., 298 (2005), 142-154.

%H Jakub Byszewski and Jakub Konieczny, <a href="https://arxiv.org/abs/1612.00073">Sparse generalised polynomials</a>, arXiv:1612.00073 [math.NT], 2016.

%H David Callan, <a href="https://arxiv.org/abs/math/0210014">Pattern avoidance in circular permutations</a>, arXiv:math/0210014 [math.CO], 2002.

%H David Callan, <a href="http://arxiv.org/abs/0802.2275">Pattern avoidance in "flattened" partitions </a>, arXiv:0802.2275 [math.CO], 2008.

%H David Callan and Toufik Mansour, <a href="https://doi.org/10.1515/puma-2015-0027">Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns</a>, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 62-97.

%H Naiomi T. Cameron and Asamoah Nkwanta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html">On Some (Pseudo) Involutions in the Riordan Group</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

%H Giulio Cerbai, Anders Claesson, and Luca Ferrari, <a href="https://arxiv.org/abs/1907.08142">Stack sorting with restricted stacks</a>, arXiv:1907.08142 [cs.DS], 2019.

%H Lapo Cioni, Luca Ferrari, and Rebecca Smith, <a href="https://arxiv.org/abs/2406.16399">Pop Stacks with a Bypass</a>, arXiv:2406.16399 [cs.DM], 2024. See pp. 73-74.

%H Tyler Clark and Tom Richmond, <a href="http://www.fq.math.ca/Papers1/48-1/Clark_Richmond.pdf">Collections of Mutually Disjoint Convex Subsets of a Totally Ordered Set</a>, Fib. Q., 48 (No. 1, 2010), 77-80.

%H Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, <a href="http://arxiv.org/abs/1510.05434">Patterns in Inversion Sequences I</a>, arXiv:1510.05434 [math.CO], 2015.

%H Aleksandar Cvetkovic, Predrag Rajkovic, and Milos Ivkovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL5/Ivkovic/ivkovic3.html">Catalan Numbers, the Hankel Transform and Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.3.

%H Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, <a href="https://doi.org/10.37236/2099">Non-contiguous pattern avoidance in binary trees</a>, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From _N. J. A. Sloane_, Feb 01 2013

%H E. Deutsch and H. Prodinger, <a href="https://doi.org/10.1016/S0304-3975(03)00222-6">A bijection between directed column-convex polyominoes and ordered trees of height at most three</a>, Theoretical Comp. Science, 307, 2003, 319-325.

%H Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1809.00742">Exhaustive generation for permutations avoiding a (colored) regular sets of patterns</a>, arXiv:1809.00742 [cs.DM], 2018.

%H Enrica Duchi, Andrea Frosini, Renzo Pinzani, and Simone Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Duchi/duchi4.html">A Note on Rational Succession Rules</a>, J. Integer Seqs., Vol. 6, 2003.

%H J.-P. Ehrmann et al., <a href="http://forumgeom.fau.edu/POLYA/ProblemCenter/POLYA003.html">POLYA003: Integers of the form a/(bc) + b/(ca) + c/(ab)</a>.

%H S. B. Ekhad and D. Zeilberger, <a href="http://arxiv.org/abs/1303.5306">How To Generate As Many Somos-Like Miracles as You Wish</a>, arXiv preprint arXiv:1303.5306 [math.CO], 2013.

%H C. Elsner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Elsner/elsner9.html">Series of Error Terms for Rational Approximations of Irrational Numbers </a>, J. Int. Seq. 14 (2011) # 11.1.4.

%H Henrik Eriksson and Markus Jonsson, <a href="https://www.fq.math.ca/Papers1/55-3/ErikssonJonsson03112017.pdf">Level sizes of the Bulgarian solitaire game tree</a>, Fib. Q., 35:3 (2017), 243-251.

%H Sergio Falcon, <a href="http://www.mathnet.or.kr/mathnet/thesis_file/CKMS-28-4-827-832.pdf">Catalan transform of the K-Fibonacci sequence</a>, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.

%H Sergio Falcon, <a href="http://dx.doi.org/10.4236/am.2014.515216">Relationships between Some k-Fibonacci Sequences</a>, Applied Mathematics, 2014, 5, 2226-2234.

%H S. Felsner and D. Heldt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Felsner/felsner2.html">Lattice Path Enumeration and Toeplitz Matrices</a>, J. Int. Seq. 18 (2015) # 15.1.3.

%H Margherita Maria Ferrari and Norma Zagaglia Salvi, <a href="https://www.emis.de/journals/JIS/VOL20/Salvi/salvi3.html">Aperiodic Compositions and Classical Integer Sequences</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.8.

%H Alex Fink, Richard K. Guy, and Mark Krusemeyer, <a href="https://doi.org/10.11575/cdm.v3i2.61940">Partitions with parts occurring at most thrice</a>, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114. See Section 13.

%H I. M. Gessel and Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013) 13.4.5.

%H A. Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding <a href="http://www.fq.math.ca/Scanned/9-3/gougenheim-a.pdf">Part 1</a> <a href="http://www.fq.math.ca/Scanned/9-3/gougenheim-b.pdf">Part 2</a>, Fib. Quart., 9 (1971), 277-295, 298.

%H R. K. Guy, <a href="/A005347/a005347.pdf">The Second Strong Law of Small Numbers</a>, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]

%H Daniel Heldt, <a href="http://dx.doi.org/10.14279/depositonce-5182">On the mixing time of the face flip-and up/down Markov chain for some families of graphs</a>, Dissertation, Mathematik und Naturwissenschaften der Technischen Universität Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.

%H Edyta Hetmaniok, Bożena Piątek, and Roman Wituła, <a href="https://doi.org/10.1515/math-2017-0047">Binomials Transformation Formulae of Scaled Fibonacci Numbers</a>, Open Mathematics, 15(1) (2017), 477-485.

%H M. Hyatt and J. Remmel, <a href="http://arxiv.org/abs/1208.1052">The classification of 231-avoiding permutations by descents and maximum drop</a>, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=127">Encyclopedia of Combinatorial Structures 127</a>

%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Janjic/janjic42.html">Determinants and Recurrence Sequences</a>, Journal of Integer Sequences, 2012, Article 12.3.5. - From _N. J. A. Sloane_, Sep 16 2012

%H I. Jensen, <a href="https://researchers.ms.unimelb.edu.au/~ij@unimelb/polygons/Polygons_ser.html">Series expansions for self-avoiding polygons</a>

%H O. Khadir, K. Liptai, and L. Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Szalay/szalay11.html">On the Shifted Product of Binary Recurrences</a>, J. Int. Seq. 13 (2010), 10.6.1.

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H S. Kitaev, J. Remmel, and M. Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I</a>, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012

%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (<a href="http://arxiv.org/abs/1302.2274">arXiv:1302.2274</a>)

%H S. Klavzar, M. Mollard, and M. Petkovsek, <a href="http://dx.doi.org/10.1016/j.disc.2011.03.019">The degree sequence of Fibonacci and Lucas cubes</a>, Discrete Math., 311, 2011, 1310-1322.

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibpi.html">Pi and the Fibonacci numbers</a>

%H F. Luca and R. Oyono, <a href="https://doi.org/10.3792/pjaa.87.45">An exponential Diophantine equation related to powers of two consecutive Fibonacci numbers</a>, Proc. Japan Acad. Ser. A Math. Sci. 87 (2011), pp. 45-50.

%H Giovanni Lucca, <a href="http://forumgeom.fau.edu/FG2019volume19/FG201902index.html">Integer Sequences and Circle Chains Inside a Hyperbola</a>, Forum Geometricorum (2019) Vol. 19, 11-16.

%H I. Lukovits and D. Janezic, <a href="http://dx.doi.org/10.1021/ci034240k">Enumeration of conjugated circuits in nanotubes</a>, J. Chem. Inf. Comput. Sci., vol. 44 (2004) pp. 410-414.

%H K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, <a href="http://arxiv.org/abs/1510.01952">Equivalence classes of ballot paths modulo strings of length 2 and 3</a>, arXiv:1510.01952 [math.CO], 2015.

%H Eric Marberg, <a href="http://arxiv.org/abs/1203.5738">Crossings and nestings in colored set partitions</a>, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.

%H M. D. McIlroy, <a href="/A005207/a005207.pdf">The number of states of a dynamic storage system</a>, Computer J., 25 (No. 3, 1982), 388-392. (Annotated scanned copy)

%H Ângela Mestre and José Agapito, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL22/Mestre/mestre2.html">Square Matrices Generated by Sequences of Riordan Arrays</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.

%H W. H. Mills, <a href="https://doi.org/10.2140/pjm.1953.3.209">A system of quadratic Diophantine equations</a>. Pacific J. Math. 3:1 (1953), 209-220, available from <a href="https://projecteuclid.org/euclid.pjm/1103051516">Project Euclid</a>.

%H D. Nacin, <a href="http://arxiv.org/abs/1204.1534">The Minimal Non-Koszul A(Gamma)</a>, arXiv preprint arXiv:1204.1534 [math.QA], 2012. - From _N. J. A. Sloane_, Oct 05 2012

%H D. Necas and I. Ohlidal, <a href="http://dx.doi.org/10.1364/OE.22.004499">Consolidated series for efficient calculation of the reflection and transmission in rough multilayers</a>, Optics Express, Vol. 22, 2014, No. 4; DOI:10.1364/OE.22.004499. See Table 1.

%H László Németh and László Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Nemeth/nemeth8.html">Sequences Involving Square Zig-Zag Shapes</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.

%H J. G. Penaud and O. Roques, <a href="https://dx.doi.org/10.1016/S0012-365X(01)00261-8">Génération de chemins de Dyck à pics croissants</a>, Discrete Mathematics, Vol. 246, no. 1-3 (2002), 255-267.

%H T. K. Petersen and Bridget Eileen Tenner, <a href="http://arxiv.org/abs/1202.4765">The depth of a permutation</a>, arXiv:1202.4765 [math.CO], 2012-2014.

%H T. Kyle Petersen and Bridget Eileen Tenner, <a href="http://arxiv.org/abs/1202.5319">How to write a permutation as a product of involutions (and why you might care)</a>, arXiv:1202.5319 [math.CO], 2012.

%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 Helmut Prodinger, <a href="https://arxiv.org/abs/1910.11808">Words, Dyck paths, Trees, and Bijections</a>, arXiv:1910.11808 [math.CO], 2019.

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a>, (slides from a talk, mentions many sequences), 2012.

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, 2015.

%H L. Pudwell, A. Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014.

%H Dun Qiu and Jeffery Remmel, <a href="https://arxiv.org/abs/1804.07087">Patterns in words of ordered set partitions</a>, arXiv:1804.07087 [math.CO], 2018.

%H M. Renault, <a href="http://www.math.temple.edu/~renault/fibonacci/thesis.html">Dissertation</a>

%H V. Retakh, S. Serconek, and R. Wilson, <a href="http://arxiv.org/abs/1010.6295">Hilbert Series of Algebras Associated to Directed Graphs and Order Homology</a>, arXiv:1010.6295 [math.RA], 2010-2011.

%H Simone Rinaldi and D. G. Rogers, <a href="http://www.jstor.org/stable/27821767">Indecomposability: polyominoes and polyomino tilings</a>, The Mathematical Gazette 92.524 (2008): 193-204.

%H J. Riordan, <a href="/A001519/a001519_1.pdf">Letter to N. J. A. Sloane, Jul. 1968</a>

%H J. Riordan, <a href="/A001519/a001519.pdf">Letter to N. J. A. Sloane, Nov. 1970</a>

%H John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.

%H Luigi Santocanale, <a href="https://arxiv.org/abs/1906.05590">On discrete idempotent paths</a>, arXiv:1906.05590 [math.LO], 2019.

%H N. J. A. Sloane, <a href="/A001514/a001514.pdf">Letter to J. Riordan, Nov. 1970</a>

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

%H B. E. Tenner, <a href="https://arxiv.org/abs/2001.05011">Interval structures in the Bruhat and weak orders</a>, arXiv:2001.05011 [math.CO], 2020.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FibonacciHyperbolicFunctions.html">Fibonacci Hyperbolic Functions</a>

%H R. Witula and Damian Slota, <a href="http://dx.doi.org/10.2298/AADM0902310W">delta-Fibonacci numbers</a>, Appl. Anal. Discr. Math 3 (2009) 310-329, <a href="http://www.ams.org/mathscinet-getitem?mr=2555042">MR2555042</a>

%H M. C. Wolf, <a href="http://dx.doi.org/10.1215/S0012-7094-36-00253-3">Symmetric functions of noncommutative elements</a>, Duke Math. J. 2 (1936), 626-637.

%H Chunyan Yan and Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.

%H F. Yano and H. Yoshida, <a href="https://doi.org/10.1016/j.disc.2007.03.050">Some set partition statistics in non-crossing partitions and generating functions</a>, Discr. Math., 307 (2007), 3147-3160.

%H D. Zeilberger, <a href="https://arxiv.org/abs/math/9801016">Automated counting of LEGO towers</a>, arXiv:math/9801016 [math.CO], 1998.

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1).

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F G.f.: (1-2*x)/(1-3*x+x^2).

%F G.f.: 1 / (1 - x / (1 - x / (1 - x))). - _Michael Somos_, May 03 2012

%F a(n) = A001906(n+1) - 2*A001906(n).

%F a(n) = a(1-n) for all n in Z.

%F a(n+2) = (a(n+1)^2+1)/a(n) with a(1)=1, a(2)=2. - _Benoit Cloitre_, Aug 29 2002

%F a(n) = (phi^(2*n-1) + phi^(1-2*n))/sqrt(5) where phi=(1+sqrt(5))/2. - _Michael Somos_, Oct 28 2002

%F a(n) = A007598(n-1) + A007598(n) = A000045(n-1)^2 + A000045(n)^2 = F(n)^2 + F(n+1)^2. - _Henry Bottomley_, Feb 09 2001

%F a(n) = Sum_{k=0..n} binomial(n+k, 2*k). - _Len Smiley_, Dec 09 2001

%F a(n) ~ (1/5)*sqrt(5)*phi^(2*n+1). - Joe Keane (jgk(AT)jgk.org), May 15 2002

%F a(n) = Sum_{k=0..n} C(n, k)*F(k+1). - _Benoit Cloitre_, Sep 03 2002

%F Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i); then q(n, 1)=a(n) (this comment is essentially the same as that of L. Smiley). - _Benoit Cloitre_, Nov 10 2002

%F a(n) = (1/2)*(3*a(n-1) + sqrt(5*a(n-1)^2-4)). - _Benoit Cloitre_, Apr 12 2003

%F Main diagonal of array defined by T(i, 1) = T(1, j) = 1, T(i, j) = max(T(i-1, j) + T(i-1, j-1); T(i-1, j-1) + T(i, j-1)). - _Benoit Cloitre_, Aug 05 2003

%F Hankel transform of A002212. E.g., Det([1, 1, 3;1, 3, 10;3, 10, 36]) = 5. - _Philippe Deléham_, Jan 25 2004

%F Solutions x > 0 to equation floor(x*r*floor(x/r)) = floor(x/r*floor(x*r)) when r=phi. - _Benoit Cloitre_, Feb 15 2004

%F a(n) = Sum_{i=0..n} binomial(n+i, n-i). - _Jon Perry_, Mar 08 2004

%F a(n) = S(n-1, 3) - S(n-2, 3) = T(2*n-1, sqrt(5)/2)/(sqrt(5)/2) with S(n, x) = U(n, x/2), resp. T(n, x), Chebyshev's polynomials of the second, resp. first kind. See triangle A049310, resp. A053120. - _Wolfdieter Lang_, Aug 31 2004

%F a(n) = ((-1)^(n-1))*S(2*(n-1), i), with the imaginary unit i and S(n, x) = U(n, x/2) Chebyshev's polynomials of the second kind, A049310. - _Wolfdieter Lang_, Aug 31 2004

%F a(n) = Sum_{0<=i_1<=i_2<=n} binomial(i_2, i_1)*binomial(n, i_1+i_2). - _Benoit Cloitre_, Oct 14 2004

%F a(n) = L(n,3), where L is defined as in A108299; see also A002878 for L(n,-3). - _Reinhard Zumkeller_, Jun 01 2005

%F a(n) = a(n-1) + Sum_{i=0..n-1} a(i)*a(n) = F(2*n+1)*Sum_{i=0..n-1} a(i) = F(2*n). - Andras Erszegi (erszegi.andras(AT)chello.hu), Jun 28 2005

%F The i-th term of the sequence is the entry (1, 1) of the i-th power of the 2 X 2 matrix M = ((1, 1), (1, 2)). - _Simone Severini_, Oct 15 2005

%F a(n-1) = (1/n)*Sum_{k=0..n} B(2*k)*F(2*n-2*k)*binomial(2*n, 2*k) where B(2*k) is the (2*k)-th Bernoulli number. - _Benoit Cloitre_, Nov 02 2005

%F a(n) = A055105(n,1) + A055105(n,2) + A055105(n,3) = A055106(n,1) + A055106(n,2). - _Mike Zabrocki_, Oct 24 2006

%F a(n) = (2/sqrt(5))*cosh((2n-1)*psi), where psi=log(phi) and phi=(1+sqrt(5))/2. - _Hieronymus Fischer_, Apr 24 2007

%F a(n) = (phi+1)^n - phi*A001906(n) with phi=(1+sqrt(5))/2. - _Reinhard Zumkeller_, Nov 22 2007

%F a(n) = 2*a(n-1) + 2*a(n-2) - a(n-3); a(n) = ((sqrt(5) + 5)/10)*(3/2 + sqrt(5)/2)^(n-2) + ((-sqrt(5) + 5)/10)*(3/2 - sqrt(5)/2)^(n-2). - _Antonio Alberto Olivares_, Mar 21 2008

%F a(n) = A147703(n,0). - _Philippe Deléham_, Nov 29 2008

%F Sum_{n>=0} atan(1/a(n)) = (3/4)*Pi. - _Jaume Oliver Lafont_, Feb 27 2009

%F With X,Y defined as X = ( F(n) F(n+1) ), Y = ( F(n+2) F(n+3) ), where F(n) is the n-th Fibonacci number (A000045), it follows a(n+2) = X.Y', where Y' is the transpose of Y (n >= 0). - _K.V.Iyer_, Apr 24 2009

%F From _Gary Detlefs_, Nov 22 2010: (Start)

%F a(n) = Fibonacci(2*n+2) mod Fibonacci(2*n), n > 1.

%F a(n) = (Fibonacci(n-1)^2 + Fibonacci(n)^2 + Fibonacci(2*n-1))/2. (End)

%F INVERT transform is A166444. First difference is A001906. Partial sums is A055588. Binomial transform is A093129. Binomial transform of A000045(n-1). - _Michael Somos_, May 03 2012

%F a(n) = 2^n*f(n;1/2), where f(n;d), n=0,1,...,d, denote the so-called delta-Fibonacci numbers (see Witula et al. papers and comments in A000045). - _Roman Witula_, Jul 12 2012

%F a(n) = (Fibonacci(n+2)^2 + Fibonacci(n-3)^2)/5. - _Gary Detlefs_, Dec 14 2012

%F G.f.: 1 + x/( Q(0) - x ) where Q(k) = 1 - x/(x*k + 1 )/Q(k+1); (recursively defined continued fraction). - _Sergei N. Gladkovskii_, Feb 23 2013

%F G.f.: (1-2*x)*G(0)/(2-3*x), where G(k) = 1 + 1/( 1 - x*(5*k-9)/(x*(5*k-4) - 6/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jul 19 2013

%F G.f.: 1 + x*(1-x^2)*Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+2 + 2*x - x^2)/( x*(4*k+4 + 2*x - x^2 ) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Sep 11 2013

%F G.f.: Q(0,u), where u=x/(1-x), Q(k,u) = 1 + u^2 + (k+2)*u - u*(k+1 + u)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Oct 07 2013

%F Sum_{n>=2} 1/(a(n) - 1/a(n)) = 1. Compare with A001906, A007805 and A097843. - _Peter Bala_, Nov 29 2013

%F Let F(n) be the n-th Fibonacci number, A000045(n), and L(n) be the n-th Lucas number, A000032(n). Then for n > 0, a(n) = F(n)*L(n-1) + (-1)^n. - _Charlie Marion_, Jan 01 2014

%F a(n) = A238731(n,0). - _Philippe Deléham_, Mar 05 2014

%F 1 = a(n)*a(n+2) - a(n+1)*a(n+1) for all n in Z. - _Michael Somos_, Jul 08 2014

%F a(n) = (L(2*n+4) + L(2*n-6))/25 for L(n)=A000032(n). - _J. M. Bergot_, Dec 30 2014

%F a(n) = (L(n-1)^2 + L(n)^2)/5 with L(n)=A000032(n). - _J. M. Bergot_, Dec 31 2014

%F a(n) = (L(n-2)^2 + L(n+1)^2)/10 with L(n)=A000032(n). - _J. M. Bergot_, Oct 23 2015

%F a(n) = 3*F(n-1)^2 + F(n-3)*F(n) - 2*(-1)^n. - _J. M. Bergot_, Feb 17 2016

%F a(n) = (F(n-1)*L(n) + F(n)*L(n-1))/2 = (A081714(n-1) + A128534(n))/2. - _J. M. Bergot_, Mar 22 2016

%F E.g.f.: (2*exp(sqrt(5)*x) + 3 + sqrt(5))*exp(-x*(sqrt(5)-3)/2)/(5 + sqrt(5)). - _Ilya Gutkovskiy_, Jul 04 2016

%F a(n) = ((M_2)^n)[1,1] = S(n, 3) - 2*S(n-1, 3), with the 2 X 2 tridiagonal matrix M_2 = Matrix([1,1], [1,2]) from A322602. For a proof see the Mar 30 2020 comment above. - _Wolfdieter Lang_, Mar 30 2020

%F Sum_{n>=1} 1/a(n) = A153387. - _Amiram Eldar_, Oct 05 2020

%F a(n+1) = Product_{k=1..n} (1 + 4*cos(2*Pi*k/(2*n + 1))^2). Special case of A099390. - _Greg Dresden_, Oct 16 2021

%F a(n+1) = 4^(n+1)*Sum_{k >= n} binomial(2*k,2*n)*(1/5)^(k+1). Cf. A102591. - _Peter Bala_, Nov 29 2021

%F a(n) = cosh((2*n-1)*arcsinh(1/2))/sqrt(5/4). - _Peter Luschny_, May 21 2022

%F From _J. M. Bergot_, May 27 2022: (Start)

%F a(n) = F(n-1)*L(n) - (-1)^n where L(n)=A000032(n) and F(n)=A000045(n).

%F a(n) = (L(n-1)^2 + L(n-1)*L(n+1))/5 + (-1)^n.

%F a(n) = 2*(area of a triangle with vertices at (L(n-2), L(n-1)), (F(n), F(n-1)), (L(n), L(n+1))) + 5*(-1)^n for n > 2. (End)

%F a(n) = A059929(n-1)+A059929(n-2), n>1. - _R. J. Mathar_, Jul 09 2024

%e a(3) = 13: there are 14 ordered trees with 4 edges; all of them, except for the path with 4 edges, have height at most 3.

%p A001519:=-(-1+z)/(1-3*z+z**2); # _Simon Plouffe_ in his 1992 dissertation; gives sequence without an initial 1

%p A001519 := proc(n) option remember: if n=0 then 1 elif n=1 then 1 elif n>=2 then 3*procname(n-1)-procname(n-2) fi: end: seq(A001519(n), n=0..28); # _Johannes W. Meijer_, Aug 14 2011

%t Fibonacci /@ (2Range[29] - 1) (* _Robert G. Wilson v_, Oct 05 2005 *)

%t LinearRecurrence[{3, -1}, {1, 1}, 29] (* _Robert G. Wilson v_, Jun 28 2012 *)

%t a[ n_] := With[{c = Sqrt[5]/2}, ChebyshevT[2 n - 1, c]/c]; (* _Michael Somos_, Jul 08 2014 *)

%t CoefficientList[ Series[(1 - 2x)/(1 - 3x + x^2), {x, 0, 30}], x] (* _Robert G. Wilson v_, Feb 01 2015 *)

%o (PARI) {a(n) = fibonacci(2*n - 1)}; /* _Michael Somos_, Jul 19 2003 */

%o (PARI) {a(n) = real( quadgen(5) ^ (2*n))}; /* _Michael Somos_, Jul 19 2003 */

%o (PARI) {a(n) = subst( poltchebi(n) + poltchebi(n - 1), x, 3/2) * 2/5}; /* _Michael Somos_, Jul 19 2003 */

%o (Sage) [lucas_number1(n,3,1)-lucas_number1(n-1,3,1) for n in range(30)] # _Zerinvary Lajos_, Apr 29 2009

%o (Haskell)

%o a001519 n = a001519_list !! n

%o a001519_list = 1 : zipWith (-) (tail a001906_list) a001906_list

%o -- _Reinhard Zumkeller_, Jan 11 2012

%o a001519_list = 1 : f a000045_list where f (_:x:xs) = x : f xs

%o -- _Reinhard Zumkeller_, Aug 09 2013

%o (Maxima) a[0]:1$ a[1]:1$ a[n]:=3*a[n-1]-a[n-2]$ makelist(a[n],n,0,30); /* _Martin Ettl_, Nov 15 2012 */

%o (Magma) [1] cat [(Lucas(2*n) - Fibonacci(2*n))/2: n in [1..50]]; // _Vincenzo Librandi_, Jul 02 2014

%o (GAP)

%o a:=[1,1];; for n in [3..10^2] do a[n]:=3*a[n-1]-a[n-2]; od; a; # _Muniru A Asiru_, Sep 27 2017

%Y Fibonacci A000045 = union of this sequence and A001906.

%Y Cf. A001653, A055105, A055106, A055107, A074664, A101368, A124292, A124293, A124294, A124295, A140069, A153463, A153266, A153267, A144257, A211216, A002559, A082582.

%Y a(n)= A060920(n, 0).

%Y Row 3 of array A094954.

%Y Equals A001654(n+1) - A001654(n-1), n > 0.

%Y A122367 is another version. Inverse sequences A130255 and A130256. Row sums of A140068, A152251, A153342, A179806, A179745, A213948.

%Y Cf. A001622, A001906, A104457, A153387, A322602.

%K nonn,nice,easy,core

%O 0,3

%A _N. J. A. Sloane_

%E Entry revised by _N. J. A. Sloane_, Aug 24 2006, May 13 2008