login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001519 a(n) = 3*a(n-1) - a(n-2), with a(0) = a(1) = 1.
(Formerly M1439 N0569)
294

%I M1439 N0569

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

%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 for n > 1 are the solutions to: 5x^2-4 is a square. - _Benoit Cloitre_, Apr 07 2002

%C a(0) = a(1) = 1, a(n+1) = 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 n such that floor(phi^2*n^2)-floor(phi*n)^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 a(n) = L(n,3), where L is defined as in A108299; see also A002878 for L(n,-3). - _Reinhard Zumkeller_, Jun 01 2005

%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 4*a(n) = A153266(n) + A153267(n), apart from initial terms. - _Creighton Dement_, Jan 02 2009

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

%C Summation of the squares of fibonacci numbers taken 2 at a time. Offset 1. a(3)=5. - Al Hakanson (hawkuu(AT)gmail.com), May 27 2009

%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->inf} 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 a(n) = 2^n a(n;1/2), where a(n;d). n=0,1,...,d, denote the so-called delta-Fibonacci number (see Witula et al. papers and comments in A000045). - _Roman Witula_, Jul 12 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 1 = a(n)*a(n+2) - a(n+1)*a(n+1) for all n in Z. - _Michael Somos_, Jul 08 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

%D C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, [http://algo.inria.fr/banderier/Papers/DiscMath99.ps Generating Functions for Generating Trees], Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

%D E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin, 1993, pp. 282-298.

%D JL Baril, R Genestier, A Giorgetti, A Petrossian, Rooted planar maps modulo some patternss, Preprint 2016; http://jl.baril.u-bourgogne.fr/cartes.pdf

%D J.-L. Baril, A. Petrossian, Equivalence classes of Dyck paths modulo some statistics, 2014; http://jl.baril.u-bourgogne.fr/Dyck.pdf.

%D A. M. Baxter, L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014, http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf

%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 S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.

%D D. Chmiela, K. Kaczmarek, R. Witula, Binomials Transformation Formulae of Scaled Fibonacci Numbers (submitted 2012).

%D Dairyko, Michael; Tyner, Samantha; Pudwell, Lara; Wynn, Casey. Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From _N. J. A. Sloane_, Feb 01 2013

%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 E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

%D Fink, Alex, Richard Guy, and Mark Krusemeyer. "Partitions with parts occurring at most thrice." Contributions to Discrete Mathematics 3.2 (2008), 76-114. See Section 13.

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

%D Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016; https://depositonce.tu-berlin.de/bitstream/11303/5553/5/heldt_daniel.pdf

%D F. Luca and R. Oyono, An exponential Diophantine equation related to powers of two consecutive Fibonacci numbers, Proc. Japan Acad. Ser. A Math. Sci. 87 (2011), pp. 45-50.

%D I. Lukovits and D. Janezic, "Enumeration of conjugated circuits in nanotubes", J. Chem. Inf. Comput. Sci., vol. 44 (2004) pp. 410-414.

%D D. Necas, I. Ohlidal, Consolidated series for efficient calculation of the reflection and transmission in rough multilayers, Optics Express, Vol. 22, 2014, No. 4; DOI:10.1364/OE.22.004499. See Table 1.

%D L. Pudwell, A. Baxter, Ascent sequences avoiding pairs of patterns, http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf, 2014

%D Rinaldi, Simone, and D. G. Rogers. "Indecomposability: polyominoes and polyomino tilings." The Mathematical Gazette 92.524 (2008): 193-204.

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

%D M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.

%D F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.

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

%H H Acan, P l Hitczenko, <a href="http://arxiv.org/abs/1406.5958">On random trees obtained from permutation graphs</a>, arXiv:1406.5958, 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 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 Jean-Luc Baril, Sergey Kirgizov, 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 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 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="http://arXiv.org/abs/math.CO/0502082">Invariants and coinvariants of the symmetric group in noncommuting variables</a>, Canadian Journal of Mathematics 60:2 (2008), pp. 266-296.

%H Daniel Birmajer, Juan B. Gil, 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 Jakub Byszewski, Jakub Konieczny, <a href="https://arxiv.org/abs/1612.00073">Sparse generalised polynomials</a>, arXiv:1612.00073 [math.NT], 2016.

%H D. 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, 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 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, 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 Phan Thuan Do, Thi Thu Huong Tran, 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 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 S. 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, 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, 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 I. M. Gessel, 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 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 M. 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="http://www.ms.unimelb.edu.au/~iwan/polygons/Polygons_ser.html">Series exapansions for self-avoiding polygons</a>

%H O. Khadir, K. Liptai, L. Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Szalay/szalay11.html">On the 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, 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, 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 K. Manes, A. Sapounakis, I. Tasoulas, 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 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 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="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%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; http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf.

%H Dun Qiu, 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FibonacciHyperbolicFunctions.html">Fibonacci Hyperbolic Functions</a>

%H R. Witula, 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 D. Zeilberger, <a href="http://arXiv.org/abs/math.CO/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) = 3*a(n-1) - a(n-2) = 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^(2n-1) + phi^(1-2n))/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, 2k). - _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) = 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 by 2 matrix M=((1, 1), (1, 2)). - _Simone Severini_, Oct 15 2005

%F a(n-1) = (1/n)*Sum_{k=0..n} B(2k)*F(2n-2k)*binomial(2n, 2k) where B(2k) is the (2k)-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 a(n) = -a(n-1) + 11*a(n-2) - 4*a(n-3), this formula (which is one of two 3rd-order linear recurrence relations given for this sequence) is a result of the generating floretion Z = X*Y with X = 1.5'i + 0.5i' + .25(ii + jj + kk + ee) and Y = 0.5'i + 1.5i' + .25(ii + jj + kk + ee). - _Creighton Dement_, Jan 02 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 a(n) = Fibonacci(2*n+2) mod Fibonacci(2*n), n > 1. - _Gary Detlefs_, Nov 22 2010

%F a(n) = (Fibonacci(n-1)^2 + Fibonacci(n)^2 + Fibonacci(2n-1))/2. - _Gary Detlefs_, Nov 22 2010

%F INVERT transform is A007051. 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) = (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 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. - _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

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

%e G.f. = 1 + x + 2*x^2 + 5*x^3 + 13*x^4 + 34*x^5 + 89*x^6 + 233*x^7 + ...

%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 xrange(0, 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.

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 21:36 EST 2019. Contains 319336 sequences. (Running on oeis4.)