A002212 -id:A002212 - cp's OEIS frontend

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

1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025, 196418, 514229, 1346269, 3524578, 9227465, 24157817, 63245986, 165580141, 433494437, 1134903170, 2971215073, 7778742049, 20365011074, 53316291173, 139583862445, 365435296162, 956722026041

Offset: 0

N. J. A. Sloane

This is a bisection of the Fibonacci sequence A000045. a(n) = F(2*n-1), with F(n) = A000045(n) and F(-1) = 1.
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
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
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
The fractional part of tau*a(n) decreases monotonically to zero. - Benoit Cloitre, Feb 01 2003
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
Number of leftist horizontally convex polyominoes with area n+1.
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
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
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
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
Essentially same as Pisot sequence E(2,5).
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
Number of 1324-avoiding circular permutations on [n+1].
A subset of the Markoff numbers (A002559). - Robert G. Wilson v, Oct 05 2005
(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
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
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
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)
  |..|
  .\/.
  which has two such vertices. - David Callan, Mar 02 2005
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
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
Number of free generators of degree n of symmetric polynomials in 3-noncommuting variables. - Mike Zabrocki, Oct 24 2006
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
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
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
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.
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
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
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
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
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
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
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).
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
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
The number of permutations for which length equals reflection length. - Bridget Tenner, Feb 22 2012
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.)
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
The number of Dyck paths of length 2n and height at most 3. - Ira M. Gessel, Aug 06 2012
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
Primes in the sequence are 2, 5, 13, 89, 233, 1597, 28657, ... (apparently A005478 without the 3). - R. J. Mathar, May 09 2013
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
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
Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - Colin Barker, Feb 04 2014
Except for the initial term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 64 = 0. - Colin Barker, Feb 16 2014
Positive values of x such that there is a y satisfying x^2 - xy - y^2 - 1 = 0. - Ralf Stephan, Jun 30 2014
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
(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
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
Number of vertices of degree n-2 (n >= 3) in all Fibonacci cubes, see Klavzar, Mollard, & Petkovsek. - Emeric Deutsch, Jun 22 2015
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
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
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
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
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
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
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
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
Number of permutations of [n] that avoid the patterns 321 and 2341. - Colin Defant, May 11 2018
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
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
From Wolfdieter Lang, Mar 30 2020: (Start)
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].
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.
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)
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
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
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
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
a(n+1) is the number of subgraphs of the path graph on n vertices. - Leen Droogendijk, Jun 17 2023
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.
     _   _   _   _  
  |||_|||_|||_|||_|||
  || _  |_|  _   _ ||
  |||_|||_|||_|||_|||. - Greg Dresden and Ruishan Wu, Aug 25 2024
a(n+1) is the number of integer sequences a_1, ..., a_n such that for any number 1 <= k <= n, (a_1 + ... + a_k)^2 = a_1^3 + ... + a_k^3. - Yifan Xie, Dec 07 2024

			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.

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 13,15.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 188.
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.
GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 92.
Jurgen Groh, Computerimprovisation mit Markoffketten und "kognitiven Algorithmen", Studienarbeit, Technische Hochschule Darmstadt, 1987.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 39.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. Stanley, Enumerative combinatorics, Vol. 1. Cambridge University Press, Cambridge, 1997, pp. 96-100.
H. S. Wilf, Generatingfunctionology, 3rd ed., A K Peters Ltd., Wellesley, MA, 2006, p. 41.

T. D. Noe, Table of n, a(n) for n = 0..200
H. Acan and P. Hitczenko, On random trees obtained from permutation graphs, arXiv:1406.3958 [math.CO], 2014-2016.
N. Allegra, Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics, arXiv preprint arXiv:1410.4131 [cond-mat.stat-mech], 2014. See Table 1.
R. C. Alperin, A family of nonlinear recurrences and their linear solutions, Fib. Q., 57:4 (2019), 318-321.
W. K. Alt, Enumeration of Domino Tilings on the Projective Grid Graph, A Thesis Presented to The Division of Mathematics and Natural Sciences, Reed College, May 2013.
Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38, 2012, pp. 1871-1876.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
E. Barcucci, A. Del Lungo, R. Pinzani, and R. Sprugnoli, La hauteur des polyominos dirigés verticalement convexes, Séminaire Lotharingien de Combinatoire, B31d (1993), 11 pp.
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.
J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, Rooted planar maps modulo some patterns, Preprint 2016.
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
J.-L. Baril and A. Petrossian, Equivalence classes of Dyck paths modulo some statistics, 2014.
Jean-Luc Baril, José L. Ramírez, and Lina M. Simbaqueba, Equivalence Classes of Skew Dyck Paths Modulo some Patterns, 2021.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
A. M. Baxter and L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014.
C. Bean, M. Tannock, and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.
Nicolas Bělohoubek and Antonín Slavík, L-Tetromino Tilings and Two-Color Integer Compositions, Univ. Karlova (Czechia, 2025). See p. 9.
N. Bergeron, C. Reutenauer, M. Rosas, and M. Zabrocki, Invariants and coinvariants of the symmetric group in noncommuting variables, arXiv:math/0502082 [math.CO], 2005; Canadian Journal of Mathematics 60:2 (2008), pp. 266-296.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
A. Blecher, C. Brennan, and A. Knopfmacher, Peaks in bargraphs, Trans. Royal Soc. South Africa, 71, No. 1, 2016, 97-103.
T. Boothby, J. Burkert, M. Eichwald, D. C. Ernst, R. M. Green, and M. Macauley, On the cyclically fully commutative elements of Coxeter groups, J. Algebr. Comb. 36, No. 1, 123-148 (2012), Table 1 CFC A,B,F.
S. Brlek, E. Duchi, E. Pergola, and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.
Yurii S. Bystryk, Vitalii L. Denysenko, and Volodymyr I. Ostryk, Lune and Lens Sequences, ResearchGate preprint, 2024. See pp. 44, 56.
Jakub Byszewski and Jakub Konieczny, Sparse generalised polynomials, arXiv:1612.00073 [math.NT], 2016.
David Callan, Pattern avoidance in circular permutations, arXiv:math/0210014 [math.CO], 2002.
David Callan, Pattern avoidance in "flattened" partitions , arXiv:0802.2275 [math.CO], 2008.
David Callan and Toufik Mansour, Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 62-97.
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
Lapo Cioni, Luca Ferrari, and Rebecca Smith, Pop Stacks with a Bypass, arXiv:2406.16399 [cs.DM], 2024. See pp. 73-74.
Tyler Clark and Tom Richmond, Collections of Mutually Disjoint Convex Subsets of a Totally Ordered Set, Fib. Q., 48 (No. 1, 2010), 77-80.
Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, Patterns in Inversion Sequences I, arXiv:1510.05434 [math.CO], 2015.
Aleksandar Cvetkovic, Predrag Rajkovic, and Milos Ivkovic, Catalan Numbers, the Hankel Transform and Fibonacci Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.3.
Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, 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
Emeric Deutsch and Helmut Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.
Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, Exhaustive generation for permutations avoiding a (colored) regular sets of patterns, arXiv:1809.00742 [cs.DM], 2018.
Enrica Duchi, Andrea Frosini, Renzo Pinzani, and Simone Rinaldi, A Note on Rational Succession Rules, J. Integer Seqs., Vol. 6, 2003.
J.-P. Ehrmann et al., POLYA003: Integers of the form a/(bc) + b/(ca) + c/(ab).
S. B. Ekhad and D. Zeilberger, How To Generate As Many Somos-Like Miracles as You Wish, arXiv preprint arXiv:1303.5306 [math.CO], 2013.
C. Elsner, Series of Error Terms for Rational Approximations of Irrational Numbers, J. Int. Seq. 14 (2011) # 11.1.4.
Henrik Eriksson and Markus Jonsson, Level sizes of the Bulgarian solitaire game tree, Fib. Q., 35:3 (2017), 243-251.
Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.
Sergio Falcon, Relationships between Some k-Fibonacci Sequences, Applied Mathematics, 2014, 5, 2226-2234.
S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
Margherita Maria Ferrari and Norma Zagaglia Salvi, Aperiodic Compositions and Classical Integer Sequences, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.8.
Alex Fink, Richard K. Guy, and Mark Krusemeyer, Partitions with parts occurring at most thrice, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114. See Section 13.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
Juan B. Gil, Felix H. Xu, and William Y. Zhu, Odd-indexed Fibonacci numbers via pattern-avoiding permutations, arXiv:2506.15800 [math.CO], 2025.
A. Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding Part 1 Part 2, Fib. Quart., 9 (1971), 277-295, 298.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
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 Universität Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
Edyta Hetmaniok, Bożena Piątek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Mathematics, 15(1) (2017), 477-485.
M. Hyatt and J. Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 127
Milan Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - From _N. J. A. Sloane_, Sep 16 2012
I. Jensen, Series expansions for self-avoiding polygons
O. Khadir, K. Liptai, and L. Szalay, On the Shifted Product of Binary Recurrences, J. Int. Seq. 13 (2010), 10.6.1.
Tanya Khovanova, Recursive Sequences
S. Kitaev, J. Remmel, and M. Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)
S. Klavzar, M. Mollard, and M. Petkovsek, The degree sequence of Fibonacci and Lucas cubes, Discrete Math., 311, 2011, 1310-1322.
Ron Knott, Pi and the Fibonacci numbers
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.
Giovanni Lucca, Integer Sequences and Circle Chains Inside a Hyperbola, Forum Geometricorum (2019) Vol. 19, 11-16.
I. Lukovits and D. Janezic, Enumeration of conjugated circuits in nanotubes, J. Chem. Inf. Comput. Sci., vol. 44 (2004) pp. 410-414.
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.
Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
M. D. McIlroy, The number of states of a dynamic storage system, Computer J., 25 (No. 3, 1982), 388-392. (Annotated scanned copy)
Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
W. H. Mills, A system of quadratic Diophantine equations. Pacific J. Math. 3:1 (1953), 209-220, available from Project Euclid.
D. Nacin, The Minimal Non-Koszul A(Gamma), arXiv preprint arXiv:1204.1534 [math.QA], 2012. - From _N. J. A. Sloane_, Oct 05 2012
D. Necas and 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.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
J. G. Penaud and O. Roques, Génération de chemins de Dyck à pics croissants, Discrete Mathematics, Vol. 246, no. 1-3 (2002), 255-267.
Permutation Pattern Avoidance Library (PermPAL), Av(123,1432)
T. K. Petersen and Bridget Eileen Tenner, The depth of a permutation, arXiv:1202.4765 [math.CO], 2012-2014.
T. Kyle Petersen and Bridget Eileen Tenner, How to write a permutation as a product of involutions (and why you might care), arXiv:1202.5319 [math.CO], 2012.
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
Helmut Prodinger, Words, Dyck paths, Trees, and Bijections, arXiv:1910.11808 [math.CO], 2019.
L. Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012.
L. Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
L. Pudwell, A. Baxter, Ascent sequences avoiding pairs of patterns, 2014.
Dun Qiu and Jeffery Remmel, Patterns in words of ordered set partitions, arXiv:1804.07087 [math.CO], 2018.
M. Renault, Dissertation
V. Retakh, S. Serconek, and R. Wilson, Hilbert Series of Algebras Associated to Directed Graphs and Order Homology, arXiv:1010.6295 [math.RA], 2010-2011.
Simone Rinaldi and D. G. Rogers, Indecomposability: polyominoes and polyomino tilings, The Mathematical Gazette 92.524 (2008): 193-204.
J. Riordan, Letter to N. J. A. Sloane, Jul. 1968
J. Riordan, Letter to N. J. A. Sloane, Nov. 1970
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
Luigi Santocanale, On discrete idempotent paths, arXiv:1906.05590 [math.LO], 2019.
N. J. A. Sloane, Letter to J. Riordan, Nov. 1970
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
B. E. Tenner, Interval structures in the Bruhat and weak orders, arXiv:2001.05011 [math.CO], 2020.
Eric Weisstein's World of Mathematics, Fibonacci Hyperbolic Functions
R. Witula and Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math 3 (2009) 310-329, MR2555042
M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.
D. Zeilberger, Automated counting of LEGO towers, arXiv:math/9801016 [math.CO], 1998.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (3,-1).
Index entries for "core" sequences
Index entries for two-way infinite sequences

Fibonacci A000045 = union of this sequence and A001906.
Cf. A001653, A055105, A055106, A055107, A074664, A101368, A124292, A124293, A124294, A124295, A140069, A153463, A153266, A153267, A144257, A211216, A002559, A082582.
a(n)= A060920(n, 0).
Row 3 of array A094954.
Equals A001654(n+1) - A001654(n-1), n > 0.
A122367 is another version. Inverse sequences A130255 and A130256. Row sums of A140068, A152251, A153342, A179806, A179745, A213948.
Cf. A001622, A001906, A104457, A153387, A322602.

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

a001519 n = a001519_list !! n
a001519_list = 1 : zipWith (-) (tail a001906_list) a001906_list
-- Reinhard Zumkeller, Jan 11 2012
a001519_list = 1 : f a000045_list where f (_:x:xs) = x : f xs
-- Reinhard Zumkeller, Aug 09 2013

[1] cat [(Lucas(2*n) - Fibonacci(2*n))/2: n in [1..50]]; // Vincenzo Librandi, Jul 02 2014

A001519:=-(-1+z)/(1-3*z+z**2); # Simon Plouffe in his 1992 dissertation; gives sequence without an initial 1
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

Fibonacci /@ (2Range[29] - 1) (* Robert G. Wilson v, Oct 05 2005 *)
LinearRecurrence[{3, -1}, {1, 1}, 29] (* Robert G. Wilson v, Jun 28 2012 *)
a[ n_] := With[{c = Sqrt[5]/2}, ChebyshevT[2 n - 1, c]/c]; (* Michael Somos, Jul 08 2014 *)
CoefficientList[ Series[(1 - 2x)/(1 - 3x + x^2), {x, 0, 30}], x] (* Robert G. Wilson v, Feb 01 2015 *)

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

{a(n) = fibonacci(2*n - 1)}; /* Michael Somos, Jul 19 2003 */

{a(n) = real( quadgen(5) ^ (2*n))}; /* Michael Somos, Jul 19 2003 */

{a(n) = subst( poltchebi(n) + poltchebi(n - 1), x, 3/2) * 2/5}; /* Michael Somos, Jul 19 2003 */

[lucas_number1(n,3,1)-lucas_number1(n-1,3,1) for n in range(30)] # Zerinvary Lajos, Apr 29 2009

G.f.: (1-2*x)/(1-3*x+x^2).
G.f.: 1 / (1 - x / (1 - x / (1 - x))). - Michael Somos, May 03 2012
a(n) = A001906(n+1) - 2*A001906(n).
a(n) = a(1-n) for all n in Z.
a(n+2) = (a(n+1)^2+1)/a(n) with a(1)=1, a(2)=2. - Benoit Cloitre, Aug 29 2002
a(n) = (phi^(2*n-1) + phi^(1-2*n))/sqrt(5) where phi=(1+sqrt(5))/2. - Michael Somos, Oct 28 2002
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
a(n) = Sum_{k=0..n} binomial(n+k, 2*k). - Len Smiley, Dec 09 2001
a(n) ~ (1/5)*sqrt(5)*phi^(2*n+1). - Joe Keane (jgk(AT)jgk.org), May 15 2002
a(n) = Sum_{k=0..n} C(n, k)*F(k+1). - Benoit Cloitre, Sep 03 2002
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
a(n) = (1/2)*(3*a(n-1) + sqrt(5*a(n-1)^2-4)). - Benoit Cloitre, Apr 12 2003
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
Hankel transform of A002212. E.g., Det([1, 1, 3;1, 3, 10;3, 10, 36]) = 5. - Philippe Deléham, Jan 25 2004
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
a(n) = Sum_{i=0..n} binomial(n+i, n-i). - Jon Perry, Mar 08 2004
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
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
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
a(n) = L(n,3), where L is defined as in A108299; see also A002878 for L(n,-3). - Reinhard Zumkeller, Jun 01 2005
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
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
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
a(n) = A055105(n,1) + A055105(n,2) + A055105(n,3) = A055106(n,1) + A055106(n,2). - Mike Zabrocki, Oct 24 2006
a(n) = (2/sqrt(5))*cosh((2n-1)*psi), where psi=log(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, Apr 24 2007
a(n) = (phi+1)^n - phi*A001906(n) with phi=(1+sqrt(5))/2. - Reinhard Zumkeller, Nov 22 2007
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
a(n) = A147703(n,0). - Philippe Deléham, Nov 29 2008
Sum_{n>=0} atan(1/a(n)) = (3/4)*Pi. - Jaume Oliver Lafont, Feb 27 2009
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
From Gary Detlefs, Nov 22 2010: (Start)
a(n) = Fibonacci(2*n+2) mod Fibonacci(2*n), n > 1.
a(n) = (Fibonacci(n-1)^2 + Fibonacci(n)^2 + Fibonacci(2*n-1))/2. (End)
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
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
a(n) = (Fibonacci(n+2)^2 + Fibonacci(n-3)^2)/5. - Gary Detlefs, Dec 14 2012
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
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
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
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
Sum_{n>=2} 1/(a(n) - 1/a(n)) = 1. Compare with A001906, A007805 and A097843. - Peter Bala, Nov 29 2013
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
a(n) = A238731(n,0). - Philippe Deléham, Mar 05 2014
1 = a(n)*a(n+2) - a(n+1)*a(n+1) for all n in Z. - Michael Somos, Jul 08 2014
a(n) = (L(2*n+4) + L(2*n-6))/25 for L(n)=A000032(n). - J. M. Bergot, Dec 30 2014
a(n) = (L(n-1)^2 + L(n)^2)/5 with L(n)=A000032(n). - J. M. Bergot, Dec 31 2014
a(n) = (L(n-2)^2 + L(n+1)^2)/10 with L(n)=A000032(n). - J. M. Bergot, Oct 23 2015
a(n) = 3*F(n-1)^2 + F(n-3)*F(n) - 2*(-1)^n. - J. M. Bergot, Feb 17 2016
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
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
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
Sum_{n>=1} 1/a(n) = A153387. - Amiram Eldar, Oct 05 2020
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
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
a(n) = cosh((2*n-1)*arcsinh(1/2))/sqrt(5/4). - Peter Luschny, May 21 2022
From J. M. Bergot, May 27 2022: (Start)
a(n) = F(n-1)*L(n) - (-1)^n where L(n)=A000032(n) and F(n)=A000045(n).
a(n) = (L(n-1)^2 + L(n-1)*L(n+1))/5 + (-1)^n.
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)
a(n) = A059929(n-1)+A059929(n-2), n>1. - R. J. Mathar, Jul 09 2024

Entry revised by N. J. A. Sloane, Aug 24 2006, May 13 2008

A007317 Binomial transform of Catalan numbers.

Original entry on oeis.org

1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, 223191, 974427, 4302645, 19181100, 86211885, 390248055, 1777495635, 8140539950, 37463689775, 173164232965, 803539474345, 3741930523740, 17481709707825, 81912506777200, 384847173838501, 1812610804416698

Offset: 1

N. J. A. Sloane, Mira Bernstein

Partial sums of A002212 (the restricted hexagonal polyominoes with n cells). Number of Schroeder paths (i.e., consisting of steps U=(1,1),D=(1,-1),H=(2,0) and never going below the x-axis) from (0,0) to (2n-2,0), with no peaks at even level. Example: a(3)=5 because among the six Schroeder paths from (0,0) to (4,0) only UUDD has a peak at an even level. - Emeric Deutsch, Dec 06 2003
Number of binary trees of weight n where leaves have positive integer weights. Non-commutative Non-associative version of partitions of n. - Michael Somos, May 23 2005
Appears also as the number of Euler trees with total weight n (associated with even switching class of matrices of order 2n). - David Garber, Sep 19 2005
Number of symmetric hex trees with 2n-1 edges; also number of symmetric hex trees with 2n-2 edges. A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read reference). A hex tree is symmetric if it is identical with its reflection in a bisector through the root. - Emeric Deutsch, Dec 19 2006
The Hankel transform of [1, 2, 5, 15, 51, 188, ...] is [1, 1, 1, 1, 1, ...], see A000012 ; the Hankel transform of [2, 5, 15, 51, 188, 731, ...] is [2, 5, 13, 34, 89, ...], see A001519. - Philippe Deléham, Dec 19 2006
a(n) = number of 321-avoiding partitions of [n]. A partition is 321-avoiding if the permutation obtained from its canonical form (entries in each block listed in increasing order and blocks listed in increasing order of their first entries) is 321-avoiding. For example, the only partition of [5] that fails to be 321-avoiding is 15/24/3 because the entries 5,4,3 in the permutation 15243 form a 321 pattern. - David Callan, Jul 22 2008
The sequence 1,1,2,5,15,51,188,... has Hankel transform A001519. - Paul Barry, Jan 13 2009
From Gary W. Adamson, May 17 2009: (Start)
  Equals INVERT transform of A033321: (1, 1, 2, 6, 21, 79, 311, ...).
  Equals INVERTi transform of A002212: (1, 3, 10, 36, 137, ...).
  Convolved with A026378, (1, 4, 17, 75, 339, ...) = A026376: (1, 6, 30, 144, ...)
(End)
a(n) is the number of vertices of the composihedron CK(n). The composihedra are a sequence of convex polytopes used to define maps of certain homotopy H-spaces. They are cellular quotients of the multiplihedra and cellular covers of the cubes. - Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009
a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps at level 0 come in 2 colors and those at a higher level come in 3 colors. Example: a(4)=15 because we have 2^3 = 8 paths of shape UHD, 2 paths of shape HUD, 2 paths of shape UDH, and 3 paths of shape UHD; here U=(1,1), H=(1,0), and D=(1,-1). - Emeric Deutsch, May 02 2011
REVERT transform of (1, 2, -3, 5, -8, 13, -21, 34, ... ) where the entries are Fibonacci numbers, A000045. Equivalently, coefficients in the series reversion of x(1-x)/(1+x-x^2). This means that the substitution of the gf (1-x-(1-6x+5x^2)^(1/2))/(2(1-x)) for x in x(1-x)/(1+x-x^2) will simplify to x. - David Callan, Nov 11 2012
The number of plane trees with nodes that have positive integer weights and whose total weight is n. - Brad R. Jones, Jun 12 2014
From Tom Copeland, Nov 02 2014: (Start)
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x)= [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)].
Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)] = (x-x^2) / (1 + x - x^2).
Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1].
(End)
Starting with offset 0, a(n) is also the number of Schröder paths of semilength n avoiding UH (an up step directly followed by a long horizontal step). Example: a(2)=5 because among the six possible Schröder paths of semilength 2 only UHD contains UH. - Valerie Roitner, Jul 23 2020

			a(3)=5 since {3, (1+2), (1+(1+1)), (2+1), ((1+1)+1)} are the five weighted binary trees of weight 3.
G.f. = x + 2*x^2 + 5*x^3 + 15*x^4 + 51*x^5 + 188*x^6 + 731*x^7 + 2950*x^8 + 12235*x^9 + ... _Michael Somos_, Jan 17 2018

J. Brunvoll et al., Studies of some chemically relevant polygonal systems: mono-q-polyhexes, ACH Models in Chem., 133 (3) (1996), 277-298, Eq. 15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..200
Roland Bacher and David Garber, Spindle-configurations of skew lines, arXiv:math/0205245 [math.GT], 2002-2005.
Christopher Bao, Yunseo Choi, Katelyn Gan, and Owen Zhang, On a Conjecture by Baril, Cerbai, Khalil, and Vajnovszki on Two Restricted Stacks, arXiv:2308.09344 [math.CO], 2023.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Paul Barry, On the Central Antecedents of Integer (and Other) Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.3.
Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010) # 10.8.2.
Andrew M. Baxter and Lara K. Pudwell, Ascent sequences avoiding pairs of patterns, 2015.
Janusz Brzozowski and Marek Szykula, Large Aperiodic Semigroups, arXiv preprint arXiv:1401.0157 [cs.FL], 2013-2014.
David Callan, Pattern avoidance in "flattened" partitions , arXiv:0802.2275 [math.CO], 2008.
H. Cambazard and N. Catusse, Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the Plane, arXiv preprint arXiv:1512.06649 [cs.DS], 2015-2017.
Giulio Cerbai, Pattern-avoiding modified ascent sequences, arXiv:2401.10027 [math.CO], 2024. See p. 17.
Giulio Cerbai, Anders Claesson, Luca Ferrari, and Einar Steingrímsson, Sorting with pattern-avoiding stacks: the 132-machine, arXiv:2006.05692 [math.CO], 2020.
Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
Harry Crane, Left-right arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.
S. J. Cyvin et al., Enumeration and classification of benzenoid systems. 32. Normal perifusenes with two internal vertices, J. Chem. Inform. Comput. Sci., 32 (1992), 532-540.
S. J. Cyvin et al., Graph-theoretical studies on fluoranthenoids and fluorenoids:enumeration of some catacondensed systems, J. Molec. Struct. (Theochem), 285 (1993), 179-185.
S. J. Cyvin et al., Enumeration and Classification of Certain Polygonal Systems Representing Polycyclic Conjugated Hydrocarbons: Annelated Catafusenes, J. Chem. Inform. Comput. Sci., 34 (1994), 1174-1180.
Dennis E. Davenport, Louis W. Shapiro, and Leon C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Rui Duarte and António Guedes de Oliveira, Generating functions of lattice paths, Univ. do Porto (Portugal 2023).
Paul Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Francesc Fite, Kiran S. Kedlaya, Victor Rotger, and Andrew V. Sutherland, Sato-Tate distributions and Galois endomorphism modules in genus 2, arXiv preprint arXiv:1110.6638 [math.NT], 2011-2012.
S. Forcey, Quotients of the multiplihedron as categorified associahedra,Homotopy, Homology and Applications, vol. 10(2), 227-256, 2008. [From Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009]
Ira M. Gessel and Jang Soo Kim, A note on 2-distant noncrossing partitions and weighted Motzkin paths, arXiv:1003.5301 [math.CO], 2010.
Ira M. Gessel and Jang Soo Kim, A note on 2-distant noncrossing partitions and weighted Motzkin paths, Discrete Math. 310 (2010), no. 23, 3421--3425. MR2721104 (2011j:05350). See Eq. (1). - _N. J. A. Sloane_, Jul 05 2014
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018. Also Discrete Mathematics (2019) Article 111705. doi:10.1016/j.disc.2019.111705
Juan B. Gil and Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See pp. 18-19.
U. Grude, Java ist eine Sprache: Rekursive Unterprogramme. See page 4.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Frank Harary and Ronald C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 124
Bradley Robert Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Hana Kim and R. P. Stanley, A refined enumeration of hex trees and related polynomials, Preprint 2015.
Jang Soo Kim, Bijections on two variations of noncrossing partitions, Discrete Math., 311 (2011), 1057-1063.
John W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.
Toufik Mansour and Mark Shattuck, Some enumerative results related to ascent sequences, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 22 2012
Igor Pak, Partition identities and geometric bijections, Proc. Amer. Math. Soc. 132 (2004), 3457-3462.
Lara K. Pudwell, Ascent sequences and the binomial convolution of Catalan numbers, arXiv:1408.6823 [math.CO], 2014.
Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, 2014.
Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
Valerie Roitner, The vectorial kernel method for walks with longer steps, arXiv:2008.02240 [math.CO], 2020.
N. J. A. Sloane, Transforms
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
Makhin Thitsa and W. Steven Gray, On the Radius of Convergence of Interconnected Analytic Nonlinear Input-Output Systems, SIAM Journal on Control and Optimization, Vol. 50, No. 5, 2012, pp. 2786-2813. - From _N. J. A. Sloane_, Dec 26 2012
S. H. F. Yan, Schröder paths and Pattern Avoiding Partitions, Int. J. Contemp. Math. Sciences, Vol. 4, no. 20, pp. 979-986, 2009.

See A181768 for another version. - N. J. A. Sloane, Nov 12 2010
First column of triangle A104259. Row sums of absolute values of A091699.
Number of vertices of multiplihedron A121988.
m-th binomial transform of the Catalan numbers: A126930 (m = -2), A005043 (m = -1), A000108 (m = 0), A064613 (m = 2), A104455 (m = 3), A104498 (m = 4) and A154623 (m = 5).
Cf. A055879, A033321, A026376, A026378, A059346, A000045, A000957, A057078,  A091867, A104597, A249548, A162326.

G := (1-sqrt(1-4*z/(1-z)))*1/2: Gser := series(G, z = 0, 30): seq(coeff(Gser, z, n), n = 1 .. 26); # Emeric Deutsch, Aug 12 2007
seq(round(evalf(JacobiP(n-1,1,-n-1/2,9)/n,99)),n=1..25); # Peter Luschny, Sep 23 2014

Rest@ CoefficientList[ InverseSeries[ Series[(y - y^2)/(1 + y - y^2), {y, 0, 26}], x], x] (* then A(x)=y(x); note that InverseSeries[Series[y-y^2, {y, 0, 24}], x] produces A000108(x) *) (* Len Smiley, Apr 10 2000 *)
Range[0, 25]! CoefficientList[ Series[ Exp[ 3x] (BesselI[0, 2x] - BesselI[1, 2x]), {x, 0, 25}], x] (* Robert G. Wilson v, Apr 15 2011 *)
a[n_] := Sum[ Binomial[n, k]*CatalanNumber[k], {k, 0, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 07 2012 *)
Rest[CoefficientList[Series[3/2 - (1/2) Sqrt[(1 - 5 x)/(1 - x)], {x, 0, 40}], x]] (* Vincenzo Librandi, Nov 03 2014 *)
Table[Hypergeometric2F1[1/2, -n+1, 2, -4], {n, 1, 30}] (* Vaclav Kotesovec, May 12 2022 *)

{a(n) = my(A); if( n<2, n>0, A=vector(n); for(j=1,n, A[j] = 1 + sum(k=1,j-1, A[k]*A[j-k])); A[n])}; /* Michael Somos, May 23 2005 */

{a(n) = if( n<1, 0, polcoeff( serreverse( (x - x^2) / (1 + x - x^2) + x * O(x^n)), n))}; /* Michael Somos, May 23 2005 */

/* Offset = 0: */ {a(n)=local(A=1+x);for(i=1,n, A=sum(m=0,n, x^m*sum(k=0,m,A^k)+x*O(x^n))); polcoeff(A,n)} \\ Paul D. Hanna

(n+2)*a(n+2) = (6n+4)*a(n+1) - 5n*a(n).
G.f.: 3/2-(1/2)*sqrt((1-5*x)/(1-x)) [Gessel-Kim]. - N. J. A. Sloane, Jul 05 2014
G.f. for sequence doubled: (1/(2*x))*(1+x-(1-x)^(-1)*(1-x^2)^(1/2)*(1-5*x^2)^(1/2)).
a(n) = hypergeom([1/2, -n], [2], -4), n=0, 1, 2...; Integral representation as n-th moment of a positive function on a finite interval of the positive half-axis: a(n)=int(x^n*sqrt((5-x)/(x-1))/(2*Pi), x=1..5), n=0, 1, 2... This representation is unique. - Karol A. Penson, Sep 24 2001
a(1)=1, a(n)=1+sum(i=1, n-1, a(i)*a(n-i)). - Benoit Cloitre, Mar 16 2004
a(n) = Sum_{k=0..n} (-1)^k*3^(n-k)*binomial(n, k)*binomial(k, floor(k/2)) [offset 0]. - Paul Barry, Jan 27 2005
G.f. A(x) satisfies 0=f(x, A(x)) where f(x, y)=x-(1-x)(y-y^2). - Michael Somos, May 23 2005
G.f. A(x) satisfies 0=f(x, A(x), A(A(x))) where f(x, y, z)=x(z-z^2)+(x-1)y^2 . - Michael Somos, May 23 2005
G.f. (for offset 0): (-1+x+(1-6*x+5*x^2)^(1/2))/(2*(-x+x^2)).
G.f. =z*c(z/(1-z))/(1-z) = 1/2 - (1/2)sqrt(1-4z/(1-z)), where c(z)=(1-sqrt(1-4z))/(2z) is the Catalan function (follows from Michael Somos' first comment). - Emeric Deutsch, Aug 12 2007
G.f.: 1/(1-2x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-.... (continued fraction). - Paul Barry, Apr 19 2009
a(n) = Sum_{k, 0<=k<=n} A091965(n,k)*(-1)^k. - Philippe Deléham, Nov 28 2009
E.g.f.: exp(3x)*(I_0(2x)-I_1(2x)), where I_k(x) is a modified Bessel function of the first kind. - Emanuele Munarini, Apr 15 2011
If we prefix sequence with an additional term a(0)=1, g.f. is (3-3*x-sqrt(1-6*x+5*x^2))/(2*(1-x)). [See Kim, 2011] - N. J. A. Sloane, May 13 2011
From Gary W. Adamson, Jul 21 2011: (Start)
a(n) = upper left term in M^(n-1), M = an infinite square production matrix as follows:
  2, 1, 0, 0, 0, 0, ...
  1, 2, 1, 0, 0, 0, ...
  1, 1, 2, 1, 0, 0, ...
  1, 1, 1, 2, 1, 0, ...
  1, 1, 1, 1, 2, 1, ...
  1, 1, 1, 1, 1, 2, ...
  ... (End)
G.f. satisfies: A(x) = Sum_{n>=0} x^n * (1 - A(x)^(n+1))/(1 - A(x)); offset=0. - Paul D. Hanna, Nov 07 2011
G.f.: 1/x - 1/x/Q(0), where Q(k)= 1 + (4*k+1)*x/((1-x)*(k+1) - x*(1-x)*(2*k+2)*(4*k+3)/(x*(8*k+6)+(2*k+3)*(1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
G.f.: (1-x - (1-5*x)*G(0))/(2*x*(1-x)), where G(k)= 1 + 4*x*(4*k+1)/( (4*k+2)*(1-x) - 2*x*(1-x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1-x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 25 2013
Asymptotics (for offset 0): a(n) ~ 5^(n+3/2)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 28 2013
G.f.: G(0)/(1-x), where G(k) = 1 + (4*k+1)*x/((k+1)*(1-x) - 2*x*(1-x)*(k+1)*(4*k+3)/(2*x*(4*k+3) + (2*k+3)*(1-x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 29 2014
a(n) = JacobiP(n-1,1,-n-1/2,9)/n. - Peter Luschny, Sep 23 2014
0 = +a(n)*(+25*a(n+1) -50*a(n+2) +15*a(n+3)) +a(n+1)*(-10*a(n+1) +31*a(n+2) -14*a(n+3)) +a(n+2)*(+2*a(n+2) +a(n+3)) for all n in Z. - Michael Somos, Jan 17 2018
a(n+1) = (2/Pi) * Integral_{x = -1..1} (m + 4*x^2)^n*sqrt(1 - x^2) dx at m = 1. In general, the integral, qua sequence in n, gives the m-th binomial transform of the Catalan numbers. - Peter Bala, Jan 26 2020

A026375 a(n) = Sum_{k=0..n} binomial(n,k)binomial(2k,k).

Original entry on oeis.org

1, 3, 11, 45, 195, 873, 3989, 18483, 86515, 408105, 1936881, 9238023, 44241261, 212601015, 1024642875, 4950790605, 23973456915, 116312293305, 565280386625, 2751474553575, 13411044301945, 65448142561035, 319756851757695

Offset: 0

Clark Kimberling

nonn

a(n) is the number of integer strings s(0),...,s(n) counted by array T in A026374 that have s(n)=0; also a(n)=T(2n,n).
Partial sums of A085362. Number of bilateral Schroeder paths (i.e., lattice paths consisting of steps U=(1,1), D=(1,-1) and H=(2,0)) from (0,0) to (2n,0) and with no H-steps at odd (positive or negative) levels. Example: a(2)=11 because we have HUD, UDH, UDUD, UUDD, UDDU, their reflections in the x-axis and HH. - Emeric Deutsch, Jan 30 2004
Largest coefficient of (1+3*x+x^2)^n; row sums of triangle in A124733. - Philippe Deléham, Oct 02 2007
Also number of paths from (0,0) to (n,0) using steps U=(1,1), H=(1,0) and D=(1,-1), the H steps come in three colors. - N-E. Fahssi, Feb 05 2008
Equals INVERT transform of A109033: (1, 2, 6, 22, 88, ...), INVERTi transform of A111966, binomial transform of A000984, and inverse Binomial transform of A081671. Convolved with A002212: (1, 3, 10, 36, ...) = A026376: (1, 6, 30, 144, ...). Equals convolution square root of A003463: (1, 6, 31, 156, 781, 3906, ...). - Gary W. Adamson, May 17 2009
Diagonal of array with rational generating function 1/(1 - (x^2 + 3*x*y + y^2)). - Gheorghe Coserea, Jul 29 2018
a(n) == 0 (mod 3) if and only if n is in A081606. - Fabio Visonà, Aug 03 2023

			G.f. = 1 + 3*x + 11*x^2 + 45*x^3 + 195*x^4 + 873*x^5 + 3989*x^6 + ...

Seiichi Manyama, Table of n, a(n) for n = 0..1000 (terms 0..200 from Vincenzo Librandi)
Hacène Belbachir, Abdelghani Mehdaoui, and László Szalay, Diagonal Sums in the Pascal Pyramid, II: Applications, J. Int. Seq., Vol. 22 (2019), Article 19.3.5.
David Callan, A combinatorial interpretation for an identity of Barrucand, JIS 11 (2008) 08.3.4.
Shu-Chiuan Chang and Robert Shrock, Structure of the Partition Function and transfer matrices for the Potts model in a magnetic field on lattice strips, J. Stat. Phys. 137 (2009) 667.
D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Rui Duarte and António Guedes de Oliveira, Generating functions of lattice paths, Univ. do Porto (Portugal 2023).
Francesc Fite, Kiran S. Kedlaya, Victor Rotger and Andrew V. Sutherland, Sato-Tate distributions and Galois endomorphism modules in genus 2, arXiv preprint arXiv:1110.6638 [math.NT], 2011-2012.
Francesc Fite and Andrew V. Sutherland, Sato-Tate distributions of twists of y^2= x^5-x and y^2= x^6+1, arXiv preprint arXiv:1203.1476 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 14 2012
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Mathematics Stack Exchange, Proof that a(n) == 0 (mod 3) if and only if n is in A081606.
László Németh, Tetrahedron trinomial coefficient transform, arXiv:1905.13475 [math.CO], 2019.
H. D. Nguyen and D. Taggart, Mining the OEIS: Ten Experimental Conjectures, 2013. Mentions this sequence. - From _N. J. A. Sloane_, Mar 16 2014
Tony D. Noe, On the Divisibility of Generalized Central Trinomial Coefficients, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.7.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 96.

Column 3 of A292627. Column 1 of A110165. Central column of A272866.
Cf. A002893, A084610, A000172, A002212.
First differences are in A085362. Bisection of A026380.
m-th binomial transforms of A000984: A126869 (m = -2), A002426 (m = -1 and m = -3 for signed version), A000984 (m = 0 and m = -4 for signed version), A026375 (m = 1 and m = -5 for signed version), A081671 (m = 2 and m = -6 for signed version), A098409 (m = 3 and m = -7 for signed version), A098410 (m = 4 and m = -8 for signed version), A104454 (m = 5 and m = -9 for signed version).

List([0..25],n->Sum([0..n],k->Binomial(n,k)*Binomial(2*k,k))); # Muniru A Asiru, Jul 29 2018

a026375 n = a026374 (2 * n) n  -- Reinhard Zumkeller, Feb 22 2014

seq( add(binomial(n,k)*binomial(2*k,k), k=0..n), n=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 08 2001
a := n -> simplify(GegenbauerC(n, -n, -3/2)):
seq(a(n), n=0..22); # Peter Luschny, May 09 2016

Table[SeriesCoefficient[1/Sqrt[1-6*x+5*x^2],{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 08 2012 *)
(* From Michael Somos, May 11 2014: (Start) *)
a[ n_] := Sum[ Binomial[n, k] Binomial[2 k, k], {k, 0, n}];
a[ n_] := If[ n < 0, 0, Hypergeometric2F1[-n, 1/2, 1, -4]];
a[ n_] := If[ n < 0, 0, Coefficient[(1 + 3 x + x^2)^n, x, n]];
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[Exp[3 x] BesselI[0,2 x], {x, 0, n}]];
(* (End) *)

A026375(n):=coeff(expand((1+3*x+x^2)^n),x,n);
makelist(A026375(n),n,0,12); /* Emanuele Munarini, Mar 02 2011 */

{a(n) = if( n<0, 0, polcoeff( (1 + 3*x + x^2)^n, n))}; /* Michael Somos, Sep 09 2002 */

a(n)={my(v=Vec((1-x-x^2)^n)); sum(k=1,#v, v[k]^2);} \\ Joerg Arndt, Jul 06 2011

{a(n) = sum(k=0, n, 5^(n-k)*(-1)^k*binomial(n, k)*binomial(2*k, k))} \\ Seiichi Manyama, Apr 22 2019

{a(n) = sum(k=0, n\2, 3^(n-2*k)*binomial(n, 2*k)*binomial(2*k, k))} \\ Seiichi Manyama, May 04 2019

Representation by Gauss's hypergeometric function, in Maple notation: a(n)=hypergeom([ -n, 1/2 ], [ 1 ], -4). - Karol A. Penson, Apr 20 2001
This sequence is the binomial transform of A000984. - John W. Layman, Aug 11 2000; proved by Emeric Deutsch, Oct 26 2002
E.g.f.: exp(3*x)*I_0(2x), where I_0 is Bessel function. - Michael Somos, Sep 17 2002
G.f.: 1/sqrt(1-6*x+5*x^2). - Emeric Deutsch, Oct 26 2002
D-finite with recurrence: n*a(n)-3*(2*n-1)*a(n-1)+5*(n-1)*a(n-2)=0 for n > 1. - Emeric Deutsch, Jan 24 2004
From Emeric Deutsch, Jan 30 2004: (Start)
a(n) = [t^n](1+3*t+t^2)^n;
a(n) = Sum_{j=ceiling(n/2)..n} 3^(2*j-n)*binomial(n, j)*binomial(j, n-j). (End)
a(n) = A026380(2*n-1) (n>0). - Emeric Deutsch, Feb 18 2004
G.f.: 1/(1-x-2*x/(1-x/(1-x-x/(1-x/(1-x-x/(1-x/(1-x-x/(1-x... (continued fraction). - Paul Barry, Jan 06 2009
a(n) = sum of squared coefficients of (1+x-x^2)^n - see triangle A084610. - Paul D. Hanna, Jul 18 2009
a(n) = sum of squares of coefficients of (1-x-x^2)^n. - Joerg Arndt, Jul 06 2011
a(n) = (1/Pi)*Integral_{x=-2..2} ((3+x)^n/sqrt((2-x)*(2+x))) dx. - Peter Luschny, Sep 12 2011
a(n) ~ 5^(n+1/2)/(2*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 08 2012
G.f.: G(0)/(1-x), where G(k) = 1 + 4*x*(4*k+1)/( (4*k+2)*(1-x) - 2*x*(1-x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1-x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 24 2013
0 = a(n)*(+25*a(n+1) - 45*a(n+2) + 10*a(n+3)) + a(n+1)*(-15*a(n+1) + 36*a(n+2) - 9*a(n+3)) + a(n+2)*(-3*a(n+2) + a(n+3)) for all n in Z. - Michael Somos, May 11 2014
a(n) = GegenbauerC(n, -n, -3/2). - Peter Luschny, May 09 2016
a(n) = Sum_{k=0..n} 5^(n-k) * (-1)^k * binomial(n,k) * binomial(2*k,k). - Seiichi Manyama, Apr 22 2019
a(n) = Sum_{k=0..floor(n/2)} 3^(n-2*k) * binomial(n,2*k) * binomial(2*k,k). - Seiichi Manyama, May 04 2019
a(n) = (1/Pi) * Integral_{x = -1..1} (1 + 4*x^2)^n/sqrt(1 - x^2) dx = (1/Pi) * Integral_{x = -1..1} (5 - 4*x^2)^n/sqrt(1 - x^2) dx. - Peter Bala, Jan 27 2020
From Peter Bala, Jan 10 2022: (Start)
1 + x*exp(Sum_{n >= 1} a(n)*x^n/n) = 1 + x + 3*x^2 + 10*x^3 + 36*x^4 + ... is the o.g.f. of A002212.
The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. (End)
a(n) = (1/4)^n * Sum_{k=0..n} 5^k * binomial(2*k,k) * binomial(2*(n-k),n-k). - Seiichi Manyama, Aug 18 2025

Definition simplified by N. J. A. Sloane, Feb 16 2012

A079523 Utterly odd numbers: numbers whose binary representation ends in an odd number of ones.

Original entry on oeis.org

1, 5, 7, 9, 13, 17, 21, 23, 25, 29, 31, 33, 37, 39, 41, 45, 49, 53, 55, 57, 61, 65, 69, 71, 73, 77, 81, 85, 87, 89, 93, 95, 97, 101, 103, 105, 109, 113, 117, 119, 121, 125, 127, 129, 133, 135, 137, 141, 145, 149, 151, 153, 157, 159, 161, 165, 167, 169, 173, 177, 181

Offset: 1

Benoit Cloitre, Jan 21 2003

Also, n such that A010060(n) = A010060(n+1) where A010060 is the Thue-Morse sequence.
Sequence of n such that a(n) = 3n begins 7, 23, 27, 29, 31, 39, 71, 87, 91, 93, 95, ...
Values of k such that the Motzkin number A001006(2k) is even. Values of k such that the number of restricted hexagonal polyominoes with 2k+1 cells is even (see A002212). Values of k such that the number of directed animals of size k+1 is even (see A005773). Values of k such that the Riordan number A005043(k) is even. - Emeric Deutsch and Bruce E. Sagan, Apr 02 2003
a(n) = A036554(n)-1 = A072939(n)-2. - Ralf Stephan, Jun 09 2003
Odious and evil terms alternate. - Vladimir Shevelev, Jun 22 2009
The sequence has the following fractal property: remove terms of the form 4k+1 from the sequence, and the remaining terms are of the form 4k+3: 7, 23, 31, 39, 55, 71, 87, ...; then subtract 3 from each of these terms and divide by 4 and you get the original sequence: 1, 5, 7, 9, 13, ... - Benoit Cloitre, Apr 06 2010
A035263(a(n)) = 0. - Reinhard Zumkeller, Mar 01 2012

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
J.-P. Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, arXiv preprint arXiv:1401.3727 [math.NT], 2014.
J.-P. Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, J. de Théorie des Nombres de Bordeaux, 27, no. 2 (2015), 375-388.
J.-P. Allouche, A. Arnold, J. Berstel, S. Brlek, W. Jockusch, Simon Plouffe, and B. E. Sagan, A relative of the Thue-Morse sequence, Discrete Math., 139, 1995, 455-461.
Narad Rampersad and Manon Stipulanti, The Formal Inverse of the Period-Doubling Sequence, arXiv:1807.11899 [math.CO], 2018.
Thomas Zaslavsky, Anti-Fibonacci Numbers: A Formula, Sep 26 2016 [Introduces the name "utterly odd". - _N. J. A. Sloane_, Sep 27 2016]
Index entries for 2-automatic sequences.

Cf. A003159, A003157, A003158, A075326, A131323.

import Data.List (elemIndices)
a079523 n = a079523_list !! (n-1)
a079523_list = elemIndices 0 a035263_list
-- Reinhard Zumkeller, Mar 01 2012

[n: n in [0..200] | Valuation(n+1, 2) mod 2 eq 0 + 1]; // Vincenzo Librandi, Apr 16 2015

Select[ Range[200], MatchQ[ IntegerDigits[#, 2], {b : (1) ..} | {_, 0, b : (1) ..} /; OddQ[ Length[{b}]]] & ] (* Jean-François Alcover, Jun 17 2013 *)

is(n)=valuation(n+1,2)%2 \\ Charles R Greathouse IV, Mar 07 2013

from itertools import count, islice
def A079523_gen(startvalue=1): return filter(lambda n:(~(n+1)&n).bit_length()&1,count(max(startvalue,1))) # generator of terms >= startvalue
A079523_list = list(islice(A079523_gen(),30)) # Chai Wah Wu, Jul 05 2022

def A079523(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x):
        c, s = n+x, bin(x)[2:]
        l = len(s)
        for i in range(l&1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    return bisection(f,n,n)-1 # Chai Wah Wu, Jan 29 2025

a(n) is asymptotic to 3n.
a(n) = 2*A003159(n) - 1. a(1)=1, a(n) = a(n-1) + 2 if (a(n-1)+1)/2 does not belong to the sequence and a(n) = a(n-1) + 4 otherwise. - Emeric Deutsch and Bruce E. Sagan, Apr 02 2003
a(n) = (1/2)*A081706(2n-1).
a(n) = A003158(n) - n = A003157(n) - n - 1. - Philippe Deléham, Feb 22 2004
Values of k such that A091297(k) = 0. - Philippe Deléham, Feb 25 2004

A091965 Triangle read by rows: T(n,k) = number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0) (left factors of 3-Motzkin steps).

Original entry on oeis.org

1, 3, 1, 10, 6, 1, 36, 29, 9, 1, 137, 132, 57, 12, 1, 543, 590, 315, 94, 15, 1, 2219, 2628, 1629, 612, 140, 18, 1, 9285, 11732, 8127, 3605, 1050, 195, 21, 1, 39587, 52608, 39718, 19992, 6950, 1656, 259, 24, 1, 171369, 237129, 191754, 106644, 42498, 12177, 2457

Offset: 0

Emeric Deutsch, Mar 13 2004

T(n,0) = A002212(n+1), T(n,1) = A045445(n+1); row sums give A026378.
The inverse is A207815. - Gary W. Adamson, Dec 17 2006 [corrected by Philippe Deléham, Feb 22 2012]
Reversal of A084536. - Philippe Deléham, Mar 23 2007
Triangle T(n,k), 0 <= k <= n, read by rows given by T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = 3*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 3*T(n-1,k) + T(n-1,k+1) for k >= 1. - Philippe Deléham, Mar 27 2007
This triangle belongs to the family of triangles defined by T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k >= 1. Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007
5^n = (n-th row terms) dot (first n+1 terms in (1,2,3,...)). Example for row 4: 5^4 = 625 = (137, 132, 57, 12, 1) dot (1, 2, 3, 4, 5) = (137 + 264 + 171 + 48 + 5) = 625. - Gary W. Adamson, Jun 15 2011
Riordan array ((1-3*x-sqrt(1-6*x+5*x^2))/(2*x^2), (1-3*x-sqrt(1-6*x+5*x^2))/(2*x)). - Philippe Deléham, Feb 19 2012

			Triangle begins:
     1;
     3,    1;
    10,    6,    1;
    36,   29,    9,    1;
   137,  132,   57,   12,    1;
   543,  590,  315,   94,   15,    1;
  2219, 2628, 1629,  612,  140,   18,    1;
T(3,1)=29 because we have UDU, UUD, 9 HHU paths, 9 HUH paths and 9 UHH paths.
Production matrix begins
  3, 1;
  1, 3, 1;
  0, 1, 3, 1;
  0, 0, 1, 3, 1;
  0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 1;
- _Philippe Deléham_, Nov 07 2011

A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.

Vincenzo Librandi, Rows n = 0..100, flattened
Shu-Chiuan Chang and Robert Shrock, Structure of the Partition Function and Transfer Matrices for the Potts Model in a Magnetic Field on Lattice Strips, J. Stat. Physics 137 (2009) 667, table 5.
Helmut Prodinger, The amplitude of Motzkin paths, arXiv:2104.07596 [math.CO], 2021. Mentions this sequence.
Helmut Prodinger, Multi-edge trees and 3-coloured Motzkin paths: bijective issues, arXiv:2105.03350 [math.CO], 2021.
Helmut Prodinger, Weighted unary-binary trees, Hex-trees, marked ordered trees, and related structures, arXiv:2106.14782 [math.CO], 2021.

Cf. A002212, A045445, A026378.

Cf. A123965.

nmax = 9; t[n_, k_] := ((k+1)*n!*Hypergeometric2F1[k+3/2, k-n, 2k+3, -4]) / ((k+1)!*(n-k)!); Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)
T[0, 0, x_, y_] := 1; T[n_, 0, x_, y_] := x*T[n - 1, 0, x, y] + T[n - 1, 1, x, y]; T[n_, k_, x_, y_] := T[n, k, x, y] = If[k < 0 || k > n, 0,
T[n - 1, k - 1, x, y] + y*T[n - 1, k, x, y] + T[n - 1, k + 1, x, y]];
Table[T[n, k, 3, 3], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, May 22 2017 *)

T(n,k):=(k+1)*sum((binomial(2*(m+1),m-k)*binomial(n,m))/(m+1),m,k,n); /* Vladimir Kruchinin, Oct 08 2011 */

@CachedFunction
def A091965(n,k):
    if n==0 and k==0: return 1
    if k<0 or k>n: return 0
    if k==0: return 3*A091965(n-1,0)+A091965(n-1,1)
    return A091965(n-1,k-1)+3*A091965(n-1,k)+A091965(n-1,k+1)
for n in (0..7):
    [A091965(n,k) for k in (0..n)] # Peter Luschny, Nov 05 2012

G.f.: G = 2/(1 - 3*z - 2*t*z + sqrt(1-6*z+5*z^2)). Alternatively, G = M/(1 - t*z*M), where M = 1 + 3*z*M + z^2*M^2.
Sum_{k>=0} T(m, k)*T(n, k) = T(m+n, 0) = A002212(m+n+1). - Philippe Deléham, Sep 14 2005
The triangle may also be generated from M^n * [1,0,0,0,...], where M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [3,3,3,...] in the main diagonal. - Gary W. Adamson, Dec 17 2006
Sum_{k=0..n} T(n,k)*(k+1) = 5^n. - Philippe Deléham, Mar 27 2007
Sum_{k=0..n} T(n,k)*x^k = A117641(n), A033321(n), A007317(n), A002212(n+1), A026378(n+1) for x = -3, -2, -1, 0, 1 respectively. - Philippe Deléham, Nov 28 2009
T(n,k) = (k+1)*Sum_{m=k..n} binomial(2*(m+1),m-k)*binomial(n,m)/(m+1). - Vladimir Kruchinin, Oct 08 2011
The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 - x^2)*(1 + 3*x + x^2)^n expanded about the point x = 0. - Peter Bala, Sep 06 2022

A005572 Number of walks on cubic lattice starting and finishing on the xy plane and never going below it.

Original entry on oeis.org

1, 4, 17, 76, 354, 1704, 8421, 42508, 218318, 1137400, 5996938, 31940792, 171605956, 928931280, 5061593709, 27739833228, 152809506582, 845646470616, 4699126915422, 26209721959656, 146681521121244, 823429928805936

Offset: 0

N. J. A. Sloane

Also number of paths from (0,0) to (n,0) in an n X n grid using only Northeast, East and Southeast steps and the East steps come in four colors. - Emeric Deutsch, Nov 03 2002
Number of skew Dyck paths of semilength n+1 with the left steps coming in two colors. - David Scambler, Jun 21 2013
Number of 2-colored Schroeder paths from (0,0) to (2n+2,0) with no level steps H=(2,0) at an even level. There are two ways to color an H-step at an odd level. Example: a(1)=4 because we have UUDD, UHD (2 choices) and UDUD. - José Luis Ramírez Ramírez, Apr 27 2015

			a(3) = 76 = sum of top row terms of M^3; i.e., (37 + 29 + 9 + 1).

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

T. D. Noe, Table of n, a(n) for n = 0..200
Rodrigo De Castro, Andrés Ramírez, and José L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449 [cs.DM], 2013. See also Sci. Annals Comp. Sci. (2014) Vol. XXIV, Issue 1, 137-171. See p. 157.
Y. Cha, Closed form solutions of difference equations, (2011) PhD Thesis, Florida State University, example 5.1.2.
Isaac DeJager, Madeleine Naquin and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.
Rigoberto Flórez, Leandro Junes and José L. Ramírez, Further Results on Paths in an n-Dimensional Cubic Lattice, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2.
R. K. Guy, Letter to N. J. A. Sloane, May 1990
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
P.-Y. Huang, S.-C. Liu and Y.-N. Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 153
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Lily L. Liu, Positivity of three-term recurrence sequences, Electronic J. Combinatorics, 17 (2010), #R57.
Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
N. J. A. Sloane, Transforms
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
E. X. W. Xia and O. X. M. Yao, A Criterion for the Log-Convexity of Combinatorial Sequences, The Electronic Journal of Combinatorics, 20 (2013), #P3.

Binomial transform of A002212. Sequence shifted right twice is A025228.

Cf. A001006, A025228, A025230, A108198, A129400, A182401.

a := n -> simplify(2^n*hypergeom([3/2, -n], [3], -2)):
seq(a(n), n=0..21); # Peter Luschny, Feb 03 2015
a := n -> simplify(GegenbauerC(n, -n-1, -2))/(n+1):
seq(a(n), n=0..21); # Peter Luschny, May 09 2016

RecurrenceTable[{a[0]==1,a[1]==4,a[n]==((2n+1)a[n-1]-3(n-1)a[n-2]) 4/(n+2)}, a[n],{n,30}] (* Harvey P. Dale, Oct 04 2011 *)
a[n_]:=If[n==0,1,Coefficient[(1+4x+x^2)^(n+1),x^n]/(n+1)]
Table[a[n],{n,0,40}] (* Emanuele Munarini, Apr 06 2012 *)

a(n):=coeff(expand((1+4*x+x^2)^(n+1)),x^n)/(n+1); makelist(a(n),n,0,12); /* Emanuele Munarini, Apr 06 2012 */

a(n)=polcoeff((1-4*x-sqrt(1-8*x+12*x^2+x^3*O(x^n)))/2,n+2)

{ A005572(n) = sum(k=0,n\2, binomial(n,2*k) * binomial(2*k,k) * 4^(n-2*k) / (k+1) ) } /* Max Alekseyev, Feb 02 2015 */

{a(n)=sum(k=0,n, binomial(n,k) * 2^(n-k) * binomial(2*k+2, k)/(k+1) )}
for(n=0,30,print1(a(n),", ")) \\ Paul D. Hanna, Feb 02 2015

def A005572(n):
    A108198 = lambda n,k: (-1)^k*catalan_number(k+1)*rising_factorial(-n,k)/factorial(k)
    return sum(A108198(n,k)*2^(n-k) for k in (0..n))
[A005572(n) for n in range(22)] # Peter Luschny, Feb 05 2015

Generating function A(x) satisfies 1 + (xA)^2 = A - 4xA.
a(0) = 1 and, for n > 0, a(n) = 4a(n-1) + Sum_{i=1..n-1} a(i-1)*a(n-i-1). - John W. Layman, Jan 07 2000
G.f.: (1 - 4*x - sqrt(1 - 8*x + 12*x^2))/(2*x^2).
D-finite with recurrence: a(n) = ((2*n+1)*a(n-1) - 3*(n-1)*a(n-2))*4/(n+2), n > 0.
a(m+n) = Sum_{k>=0} A052179(m, k)*A052179(n, k) = A052179(m+n, 0). - Philippe Deléham, Sep 15 2005
a(n) = 4*a(n-1) + A052177(n-1) = A052179(n, 0) = 6*A005573(n)-A005573(n-1) = Sum_{j=0..floor(n/2)} 4^(n-2*j)*C(n, 2*j)*C(2*j, j)/(j+1). - Henry Bottomley, Aug 23 2001
a(n) = Sum_{k=0..n} A097610(n,k)*4^k. - Philippe Deléham, Dec 03 2009
Let A(x) be the g.f., then B(x) = 1 + x*A(x) = 1 + 1*x + 4*x^2 + 17*x^3 + ... = 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1-2*x) (continued fraction); more generally B(x) = C(x/(1-2*x)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011
From Gary W. Adamson, Jul 21 2011: (Start)
a(n) = sum of top row terms of M^n, M = an infinite square production matrix as follows:
  3, 1, 0, 0, ...
  1, 3, 1, 0, ...
  1, 1, 3, 1, ...
  1, 1, 1, 3, ...
  ... (End)
a(n) ~ 3*6^(n+1/2)/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Oct 05 2012
a(n) = Sum_{k=0..floor(n/2)} binomial(n,2*k) * binomial(2k,k) * 4^(n-2k) / (k+1). - Max Alekseyev, Feb 02 2015
From Paul D. Hanna, Feb 02 2015: (Start)
a(n) = Sum_{k=0..n} binomial(n,k) * 2^(n-k) * binomial(2*k+2, k)/(k+1).
a(n) = Sum_{k=0..n} binomial(n,k) * 2^(n-k) * A000108(k+1).
a(n) = [x^n] (1 + 4*x + x^2)^(n+1) / (n+1).
G.f.: (1/x) * Series_Reversion( x/(1 + 4*x + x^2) ). (End)
a(n) = 2^n*hypergeom([3/2, -n], [3], -2). - Peter Luschny, Feb 03 2015
a(n) = 4^n*hypergeom([-n/2, (1-n)/2], [2], 1/4). - Robert Israel, Feb 04 2015
a(n) = Sum_{k=0..n} A108198(n,k)*2^(n-k). - Peter Luschny, Feb 05 2015
a(n) = 2*(12^(n/2))*(n!/(n+2)!)*GegenbauerC(n, 3/2,2/sqrt(3)), where GegenbauerC are Gegenbauer polynomials in Maple notation. This is a consequence of Robert Israel's formula. - Karol A. Penson, Feb 20 2015
a(n) = (2^(n+1)*3^((n+1)/2)*P(n+1,1,2/sqrt(3)))/((n+1)*(n+2)) where P(n,u,x) are the associated Legendre polynomials of the first kind. - Peter Luschny, Feb 24 2015
a(n) = -6^(n+1)*sqrt(3)*Integral{t=0..Pi}(cos(t)*(2+cos(t))^(-n-2))/(Pi*(n+2)). - Peter Luschny, Feb 24 2015
From Karol A. Penson and Wojciech Mlotkowski, Mar 16 2015: (Start)
Integral representation as the n-th moment of a positive function defined on a segment x=[2, 6]. This function is the Wigner's semicircle distribution shifted to the right by 4. This representation is unique. In Maple notation,
a(n) = int(x^n*sqrt(4-(x-4)^2)/(2*Pi), x=2..6),
a(n) = 2*6^n*Pochhammer(3/2, n)*hypergeom([-n, 3/2], [-n-1/2], 1/3)/(n+2)!
(End)
a(n) = GegenbauerC(n, -n-1, -2)/(n+1). - Peter Luschny, May 09 2016
E.g.f.: exp(4*x) * BesselI(1,2*x) / x. - Ilya Gutkovskiy, Jun 01 2020
From Peter Bala, Aug 18 2021: (Start)
G.f. A(x) = 1/(1 - 2*x)*c(x/(1 - 2*x))^2, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. Cf. A129400.
Conjecture: a(n) is even except for n of the form 2*(2^k - 1). [added Feb 03: the conjecture follows from the formula a(n) = Sum_{k = 0..n} 2^(n-k)*binomial(n, k)*Catalan(k+1) given above.] (End)
From Peter Bala, Feb 03 2024: (Start)
G.f.: 1/(1 - 2*x) * c(x/(1 - 2*x))^2 = 1/(1 - 6*x) * c(-x/(1 - 6*x))^2, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
a(n) = 6^n * Sum_{k = 0..n} (-6)^(-k)*binomial(n, k)*Catalan(k+1).
a(n) = 6^n * hypergeom([-n, 3/2], [3], 2/3). (End)

Additional comments from Michael Somos, Jun 10 2000

A033321 Binomial transform of Fine's sequence A000957: 1, 0, 1, 2, 6, 18, 57, 186, ...

Original entry on oeis.org

1, 1, 2, 6, 21, 79, 311, 1265, 5275, 22431, 96900, 424068, 1876143, 8377299, 37704042, 170870106, 779058843, 3571051579, 16447100702, 76073821946, 353224531663, 1645807790529, 7692793487307, 36061795278341, 169498231169821

Offset: 0

Emeric Deutsch

nonn

Number of permutations avoiding the patterns {2431,4231,4321}; number of weak sorting class based on 2431. - Len Smiley, Nov 01 2005
Number of permutations avoiding the patterns {2413, 3142, 2143}. - Vincent Vatter, Aug 16 2006
Number of permutations avoiding the patterns {2143, 3142, 4132}. - Alexander Burstein and Jonathan Bloom, Aug 03 2013
Number of unimodal Lehmer codes. Those are exactly the inversion sequences for permutations avoiding the patterns {2143, 3142, 4132}. - Alexander Burstein, Jun 16 2015
Number of skew Dyck paths of semilength n ending with a down step (1,-1). A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. Number of skew Dyck paths of semilength n and ending with a left step is A128714(n). - Emeric Deutsch, May 11 2007
Number of permutations sortable by a pop stack followed directly by a stack. Equivalently, the number of permutations avoiding {2431, 3142, 3241}. - Vincent Vatter, Mar 06 2013
Hankel transform of this sequence gives A000012 = [1,1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
Starting with offset 1, Hankel transform = odd-indexed Fibonacci numbers. - Gary W. Adamson, Dec 27 2008
Starting with offset 1 = INVERT transform of A002212: (1, 1, 3, 10, 36, 137, ...). - Gary W. Adamson, May 19 2009
Equals INVERTi transform of A007317: (1, 2, 5, 15, 51, 188, ...). - Gary W. Adamson, May 17 2009
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.20] - Eric M. Schmidt, Jul 17 2017
From David Callan, Jul 21 2017: (Start)
a(n) is the number of permutations of [n] in which the excedances and subcedances are both increasing. (For example, the 3 permutations of [4] NOT counted by a(4)=21 are 3421, 4312, 4321 with excedances/subcedances 34/21, 43/12, 43/21 respectively.)
Proof. It suffices to show that (*) the number of such permutations of [n] containing k fixed points is binomial(n,k)*F(n-k), where F is the Fine number A000957. Since F(n) is the number of 321-avoiding derangements of [n] and because inserting or deleting a fixed point in a permutation does not change the excedance/fixed point/subcedance status of any other entry, (*) is an immediate consequence of the following claim: The excedances and subcedances of a permutation p are both increasing if and only if p avoids 321. The claim is a nice exercise utilizing the cycles of p for the "if" direction and the pigeonhole principle for the "only if" direction. (End)
Conjectured to be the number of permutations of length n that are sorted to the identity by a consecutive-231-avoiding stack followed by a classical-21-avoiding stack. - Colin Defant, Aug 30 2020
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {3>1, 3>4, 1>2} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the third element is the largest and the first element is larger than the second element. - Sergey Kitaev, Dec 10 2020

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0 to 200 by T. D. Noe)
M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan, and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005) R31.
Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Jean-Luc Baril, José L. Ramírez, and Lina M. Simbaqueba, Counting prefixes of skew Dyck paths, J. Int. Seq., Vol. 24 (2021), Article 21.8.2.
Paul Barry, Series reversion with Jacobi and Thron continued fractions, arXiv:2107.14278 [math.NT], 2021.
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Christian Bean, Émile Nadeau, and Henning Ulfarsson, Enumeration of Permutation Classes and Weighted Labelled Independent Sets, arXiv:1912.07503 [math.CO], 2019.
David Bevan, The permutation class Av(4213,2143), arXiv:1510.06328 [math.CO], 2014.
Jonathan Bloom and Alex Burstein, Egge triples and unbalanced Wilf-equivalence, arXiv:1410.0230 [math.CO], 2014.
Miklos Bona, Long increasing subsequences and non-algebraicity, arXiv:2310.13649 [math.CO], 2023.
Robert Brignall, Sophie Huczynska, and Vincent Vatter, Simple permutations and algebraic generating functions, arXiv:math/0608391 [math.CO], 2006.
Robert Brignall and Jakub Sliacan, Juxtaposing Catalan permutation classes with monotone ones, arXiv:1611.05370 [math.CO], 2016.
Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Emeric Deutsch, Emanuele Munarini, and Simone Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, J. Int. Seq. (2025) Vol. 28, Art. No. 25.1.6. See p. 19.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
John W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Toufik Mansour and Mark Shattuck, Nine classes of permutations enumerated by binomial transform of Fine's sequence, Discrete Applied Mathematics, Vol. 226, 31 July 2017, p. 94-105.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Sam Miner, Enumeration of several two-by-four classes, arXiv preprint arXiv:1610.01908 [math.CO], 2016.
N. J. A. Sloane, Transforms
Rebecca Smith and Vincent Vatter, A stack and a pop stack in series, arXiv:1303.1395 [math.CO], 2013.
Index entries for reversions of series

Cf. A000957, A002212, A007317, A128714, A214611.

a[0] := 1: a[1] := 1: a[2] := 2: for n from 3 to 23 do a[n] := ((13*n-5)*a[n-1]-(16*n-23)*a[n-2]+5*(n-2)*a[n-3])/2/(n+1) od;

f[n_] := Sum[Binomial[n, k]*g[n - k], {k, 0, n}]; g[n_] := Sum[(-1)^(m + n)(n + m)!/n!/m!(n - m + 1)/(n + 1), {m, 0, n}]; Table[ f[n], {n, 24}] (* Robert G. Wilson v, Nov 04 2005 *)

a(n):=sum(sum(binomial(n-m-1,k-1)*m/(k+m)*binomial(2*k+m-1,k+m-1),k,1,n-m),m,1,n-1)+1; /* Vladimir Kruchinin, May 12 2011 */

a(n)=1+sum(m=1,n-1,sum(k=1,n-m,binomial(n-m-1,k-1)/(k+m)* binomial(2*k+m-1,k+m-1)*m)) \\ Charles R Greathouse IV, Mar 06 2013

x='x+O('x^50); Vec(2/(1+x+sqrt(1-6*x+5*x^2))) \\ Altug Alkan, Oct 22 2015

Also REVERT transform of x*(2*x-1)/(x^2+x-1). - Olivier Gérard
G.f.: 2/(1 + x + sqrt(1 - 6*x + 5*x^2)).
D-finite with recurrence a(n) = ((13*n-5)*a(n-1) - (16*n-23)*a(n-2) + 5*(n-2)*a(n-3))/(2*(n+1)) (n>=3); a(0)=a(1)=1, a(2)=2. - Emeric Deutsch, Mar 21 2004
Binomial transform of Fine's sequence: a(n) = Sum_{k=0..n} binomial(n, k)*A000957(n-k).
G.f.: 1/(1-x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-... (continued fraction). - Paul Barry, Jun 15 2009
a(n) = Sum_{k=0..n} A091965(n,k)*(-2)^k. - Philippe Deléham, Nov 28 2009
a(n) = 1 + Sum_{m=1..n-1} Sum_{k=1..n-m} binomial(n-m-1, k-1)*(m/(k+m))*binomial(2*k+m-1, k+m-1). - Vladimir Kruchinin, May 12 2011
a(n) = upper left term in M^n, M = the production matrix:
  1, 1, 0, 0, 0, 0, 0, ...
  1, 2, 1, 0, 0, 0, 0, ...
  1, 2, 1, 1, 0, 0, 0, ...
  1, 2, 1, 2, 1, 0, 0, ...
  1, 2, 1, 2, 1, 1, 0, ...
  1, 2, 1, 2, 1, 2, 1, ...
  ...
- Gary W. Adamson, Jul 08 2011
a(n) ~ 5^(n+3/2)/(18*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2013
G.f.: 1/(1-x*C(x/(1-x))), where C(x) = g.f. for A000108(n). - Alexander Burstein, Oct 05 2014

More terms from Robert G. Wilson v, Nov 04 2005

Entry revised by N. J. A. Sloane, Aug 07 2006

cp's OEIS Frontend

A073149 Triangle of numbers arising in recursive computation of A002212.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

Sage

Formula

Extensions

A007317 Binomial transform of Catalan numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A026375 a(n) = Sum_{k=0..n} binomial(n,k)*binomial(2*k,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

Formula

Extensions

A079523 Utterly odd numbers: numbers whose binary representation ends in an odd number of ones.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

A026375 a(n) = Sum_{k=0..n} binomial(n,k)binomial(2k,k).