A048996 -id:A048996 - cp's OEIS frontend

A001906 F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).

0, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, 4807526976, 12586269025, 32951280099, 86267571272, 225851433717, 591286729879, 1548008755920

Offset: 0

N. J. A. Sloane

Apart from initial term, same as A088305.
Second column of array A102310 and of A028412.
Numbers k such that 5*k^2 + 4 is a square. - Gregory V. Richardson, Oct 13 2002
Apart from initial terms, also Pisot sequences E(3,8), P(3,8), T(3,8). See A008776 for definitions of Pisot sequences.
Binomial transform of A000045. - Paul Barry, Apr 11 2003
Number of walks of length 2n+1 in the path graph P_4 from one end to the other one. Example: a(2)=3 because in the path ABCD we have ABABCD, ABCBCD and ABCDCD. - Emeric Deutsch, Apr 02 2004
Simplest example of a second-order recurrence with the sixth term a square.
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) = 3. - Lekraj Beedassy, Jun 11 2004
a(n) (for n > 0) is the smallest positive integer that cannot be created by summing at most n values chosen among the previous terms (with repeats allowed). - Andrew Weimholt, Jul 20 2004
All nonnegative integer solutions of Pell equation b(n)^2 - 5*a(n)^2 = +4 together with b(n) = A005248(n), n >= 0. - Wolfdieter Lang, Aug 31 2004
a(n+1) is a Chebyshev transform of 3^n (A000244), where the sequence with g.f. G(x) is sent to the sequence with g.f. (1/(1+x^2))G(x/(1+x^2)). - Paul Barry, Oct 25 2004
a(n) is the number of distinct products of matrices A, B, C, in (A+B+C)^n where commutator [A,B] = 0 but C does not commute with A or B. - Paul D. Hanna and Max Alekseyev, Feb 01 2006
Number of binary words with exactly k-1 strictly increasing runs. Example: a(3)=F(6)=8 because we have 0|0,1|0,1|1,0|01,01|0,1|01,01|1 and 01|01. Column sums of A119900. - Emeric Deutsch, Jul 23 2006
See Table 1 on page 411 of Lukovits and Janezic paper. - Parthasarathy Nambi, Aug 22 2006
Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5) a(n) + sqrt(5 a(n)^2 + 4))/2) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007
[1,3,8,21,55,144,...] is the Hankel transform of [1,1,4,17,75,339,1558,...](see A026378). - Philippe Deléham, Apr 13 2007
The Diophantine equation a(n) = m has a solution (for m >= 1) if and only if floor(arcsinh(sqrt(5)*m/2)/log(phi)) <> floor(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130259(m) = A130260(m). - Hieronymus Fischer, May 25 2007
a(n+1) = AB^(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., 1=`1`, 3=`10`, 8=`100`, 21=`1000`, ..., in Wythoff code.
Equals row sums of triangles A140069, A140736 and A140737. - Gary W. Adamson, May 25 2008
a(n) is also the number of idempotent order-preserving partial transformations (of an n-element chain) of width n (width(alpha) = max(Im(alpha))). Equivalently, it is the number of idempotent order-preserving full transformations (of an n-element chain). - Abdullahi Umar, Sep 08 2008
a(n) is the number of ways that a string of 0,1 and 2 of size (n-1) can be arranged with no 12-pairs. - Udita Katugampola, Sep 24 2008
Starting with offset 1 = row sums of triangle A175011. - Gary W. Adamson, Apr 03 2010
As a fraction: 1/71 = 0.01408450... or 1/9701 = 0.0001030821.... - Mark Dols, May 18 2010
Sum of the products of the elements in the compositions of n (example for n=3: the compositions are 1+1+1, 1+2, 2+1, and 3; a(3) = 1*1*1 + 1*2 + 2*1 + 3 = 8). - Dylon Hamilton, Jun 20 2010, Geoffrey Critzer, Joerg Arndt, Dec 06 2010
a(n) relates to regular polygons with even numbers of edges such that Product_{k=1..(n-2)/2} (1 + 4*cos^2 k*Pi/n) = even-indexed Fibonacci numbers with a(n) relating to the 2*n-gons. The constants as products = roots to even-indexed rows of triangle A152063. For example: a(5) = 55 satisfies the product formula relating to the 10-gon. - Gary W. Adamson, Aug 15 2010
Alternatively, product of roots to x^4 - 12x^3 + 51x^2 - 90x + 55, (10th row of triangle A152063) = (4.618...)*(3.618...)*(2.381...)*(1.381...) = 55. - Gary W. Adamson, Aug 15 2010
a(n) is the number of generalized compositions of n when there are i different types of i, (i=1,2,...). - Milan Janjic, Aug 26 2010
Starting with "1" = row sums of triangle A180339, and eigensequence of triangle A137710. - Gary W. Adamson, Aug 28 2010
a(2) = 3 is the only prime.
Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n > 0, with exactly 2 elements of each rank level above 0. (Uniform used in the sense of Retakh, Serconek, and Wilson.  Graded used in Stanley's sense that every maximal chain has the same length n.) - David Nacin, Feb 13 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
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 1. - Michel Lagneau, Feb 01 2014
For n >= 1, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,2}. - Milan Janjic, Jan 25 2015
With a(0) = 0, for n > 1, a(n) is the smallest number not already in the sequence such that a(n)^2 - a(n-1)^2 is a Fibonacci number. - Derek Orr, Jun 08 2015
Let T be the tree generated by these rules: 0 is in T, and if p is in T, then p + 1 is in T and x*p is in T and y*p is in T. The n-th generation of T consists of A001906(n) polynomials, for n >= 0. - Clark Kimberling, Nov 24 2015
For n > 0, a(n) = exactly the maximum area of a quadrilateral with sides in order of lengths F(n), F(n), L(n), and L(n) with L(n)=A000032(n). - J. M. Bergot, Jan 20 2016
a(n) = twice the area of a triangle with vertices at (L(n+1), L(n+2)), (F(n+1), F(n+1)), and (L(n+2), L(n+1)), with L(n)=A000032(n). - J. M. Bergot, Apr 20 2016
Except for the initial 0, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S - S^2; see A291000. - Clark Kimberling, Aug 24 2017
a(n+1) is the number of spanning trees of the graph T_n, where T_n is a sequence of n triangles, where adjacent triangles share an edge. - Kevin Long, May 07 2018
a(n) is the number of ways to partition [n] such that each block is a run of consecutive numbers, and each block has a fixed point, e.g., for n=3, 12|3 with 1 and 3 as fixed points is valid, but 13|2 is not valid as 1 and 3 do not form a run. Consequently, a(n) also counts the spanning trees of the graph given by taking a path with n vertices and adding another vertex adjacent to all of them. - Kevin Long, May 11 2018
From Wolfdieter Lang, May 31 2018: (Start)
The preceding comment can be paraphrased as follows. a(n) is the row sum of the array A305309 for n >= 1. The array A305309(n, k) gives the sum of the products of the block lengths of the set partition of [n] := {1, 2, ..., n} with A048996(n, k) blocks of consecutive numbers, corresponding to the compositions obtained from the k-th partition of n in Abramowitz-Stegun order. See the comments and examples at A305309.
{a(n)} also gives the infinite sequence of nonnegative numbers k for which k * ||k*phi|| < 1/sqrt(5), where the irrational number phi = A001622 (golden section), and ||x|| is the absolute value of the difference between x and the nearest integer. See, e.g., the Havil reference, pp. 171-172. (End)
This Chebyshev sequence a(n) = S(n-1, 3) (see a formula below) is related to the bisection of Fibonacci sequences {F(a,b;n)}{n>=0} with input F(a,b;0) = a and F(a,b;1) = b, by F(a,b;2*k) = (a+b)*S(k-1, 3) - a*S(k-2, 3) and F(a,b;2*k+1) = b*S(k, 3) + (a-b)*S(k-1, 3), for k >= 0, and S(-2, 3) = -1. Proof via the o.g.f.s GFeven(a,b,t) = (a - t*(2*a-b))/(1 - 3*t + t^2) and GFodd(a,b,t) = (b + t*(a-b))/(1 - 3*t + t^2). The special case a = 0, b = 1 gives back F(2*k) = S(k-1, 3) = a(k). - _Wolfdieter Lang, Jun 07 2019
a(n) is the number of tilings of two n X 1 rectangles joined orthogonally at a common end-square (so to have 2n-1 squares in a right-angle V shape) with only 1 X 1 and 2 X 1 tiles. This is a consequence of F(2n) = F(n+1)*F(n) + F(n)*F(n-1). - Nathaniel Gregg, Oct 10 2021
These are the denominators of the upper convergents to the golden ratio, tau; they are also the numerators of the lower convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - Clark Kimberling, Jan 02 2022
For n > 1, a(n) is the smallest Fibonacci number of unit equilateral triangle tiles needed to make an isosceles trapezoid of height F(n) triangles. - Kiran Ananthpur Bacche, Sep 01 2024

			G.f. = x + 3*x^2 + 8*x^3 + 21*x^4 + 55*x^5 + 144*x^6 + 377*x^7 + 987*x^8 + ...
a(3) = 8 because there are exactly 8 idempotent order-preserving full transformations on a 3-element chain, namely: (1,2,3)->(1,1,1),(1,2,3)->(2,2,2),(1,2,3)->(3,3,3),(1,2,3)->(1,1,3),(1,2,3)->(2,2,3),(1,2,3)->(1,2,2),(1,2,3)->(1,3,3),(1,2,3)->(1,2,3)-mappings are coordinate-wise. - _Abdullahi Umar_, Sep 08 2008

Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 2,5,6,14,33,55.
R. J. Douglas, Tournaments that admit exactly one Hamiltonian cycle, Proc. London Math. Soc., 21 (1970), 716-730.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
A. Gerardin, Reply to Query 4389, L'Intermédiaire des Mathématiciens, 22 (1915), 23.
Julian Havil, The Irrationals, Princeton University Press, Princeton and Oxford, 2012, pp. 171-172.
Howie, J. M. Combinatorial and probabilistic results in transformation semigroups. Words, languages and combinatorics, II (Kyoto, 1992), 200--206, World Sci. Publ., River Edge, NJ, (1994).
Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving full transformations. Semigroup Forum 72 (2006), 51-62.
I. Lukovits, A. Graovac, E. Kalman, G. Kaptay, P. Nagy, S. Nikolic, J. Sytchev and N. Trinajstich, "Nanotubes: Number of Kekulé Structures and Aromaticity", J. Chem. Inf. Comput. Sci, vol. 43 (2003), pp. 609-614. See Equation 6 on page 611.
T. Mansour, M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.
H. Mathieu, Query 3932, L'Intermédiaire des Mathématiciens, 18 (1911), 222. - N. J. A. Sloane, Mar 08 2022
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 101.
Paulo Ribenboim, Primes in Lucas sequences (Chap 4), in 'My Numbers, My Friends', Springer-Verlag 2000 NY, page 27.
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.

Indranil Ghosh, Table of n, a(n) for n = 0..2388 (terms 0..200 from T. D. Noe)
Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", Discrete Math. 335 (2014), 1--7. MR3248794.
Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, Polynomial sequences on quadratic curves, Integers, Vol. 15, 2015, #A38.
K. Andersen, L. Carbone, and D. Penta, Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields, Journal of Number Theory and Combinatorics, Vol 2, No. 3 pp 245-278, 2011. See Section 9.
Andrei Asinowski and Michaela A. Polley, Patterns in rectangulations. Part I: T-like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths, arXiv:2501.11781 [math.CO], 2025. See p. 26.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Paul Barry, The Triple Riordan Group, arXiv:2412.05461 [math.CO], 2024. See pp. 5, 10.
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.
Raghavendra Bhat, Cristian Cobeli, and Alexandru Zaharescu, Filtered rays over iterated absolute differences on layers of integers, arXiv:2309.03922 [math.NT], 2023. See page 16.
Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, Honeycombs in the Pascal triangle and beyond, arXiv:2203.13205 [math.HO], 2022. See p. 5.
Zbigniew R. Bogdanowicz, Formulas for the Number of Spanning Trees in a Fan, Appl. Math. Sci. (2008) Vol. 2, No. 16, 781-786.
A. Bremner and N. Tzanakis, Lucas sequences whose 12th or 9th term is a square, arXiv:math/0405306 [math.NT], 2004.
David Broadhurst, Multiple Landen values and the tribonacci numbers, arXiv:1504.05303 [hep-th], 2015.
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
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.
Marc Chamberland and Christopher French, Generalized Catalan Numbers and Generalized Hankel Transformations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.1.
A. Collins et al., Binary words, n-color compositions and bisection of the Fibonacci numbers, Fib. Quarterly, 51 (2013), 130-136.
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
Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607. See Cor. 3.7(e).
Sergio Falcon, Relationships between Some k-Fibonacci Sequences, Applied Mathematics, 2014, 5, 2226-2234.
Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832. doi:10.4134/CKMS.2013.28.4.827.
Sergio Falcon, Iterated Binomial Transforms of the k-Fibonacci Sequence, British Journal of Mathematics & Computer Science, 4 (22): 2014.
R. Flórez, R. A. Higuita, and A. Mukherjee, Alternating Sums in the Hosoya Polynomial Triangle, Article 14.9.5 Journal of Integer Sequences, Vol. 17 (2014).
Achille Frigeri, A note on Fibonacci number of even index, arXiv:1705.08305 [math.NT], 2017.
M. R. Garey, On enumerating tournaments that admit exactly one Hamiltonian circuit, J. Combin. Theory, B 13 (1972), 266-269.
Dale Gerdemann, Fractal images from (3,-1) recursion, YouTube Video, Oct 30 2014.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013), 13.4.5.
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.
Y-h. Guo, Some n-Color Compositions, J. Int. Seq. 15 (2012) 12.1.2, eq (2).
Edyta Hetmaniok, Bozena Piatek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Math. 15 (2017), 477-485.
A. F. Horadam, Special Properties of the Sequence W(n){a,b; p,q}, Fib. Quart., Vol. 5, No. 5 (1967), pp. 424-434. Case a=0,b=1; p=3, q=-1.
J. M. Howie, Products of idempotents in certain semigroups of transformations, Proc. Edinburgh Math. Soc. 17 (1971), 223-236.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 147 [broken link].
Milan Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
J. Jina and P. Trojovsky, On determinants of some tridiagonal matrices connected with Fibonacci numbers, International Journal of Pure and Applied Mathematics 88:4 (2013), 569-575.
Tanya Khovanova, Recursive Sequences
E. Kilic, Y. T. Ulutas, and N. Omur, A Formula for the Generating Functions of Powers of Horadam's Sequence with Two Additional Parameters, J. Int. Seq. 14 (2011) #11.5.6, Table 1, k=t=1.
Seong Ju Kim, R. Stees, and L. Taalman, Sequences of Spiral Knot Determinants, Journal of Integer Sequences, Vol. 19 (2016), #16.1.4.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
Markus Kuba and Alois Panholzer, Enumeration formulas for pattern restricted Stirling permutations, Discrete Math. 312(21) (2012), 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419. Eq. (44) lhs, m=5.
Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
I. Lukovits and D. Janezic, Enumeration of conjugated circuits in nanotubes, J. Chem. Inf. Comput. Sci., vol. 44 (2004) pp. 410-414.
G. Narang and A. K. Agarwal, Lattice paths and n-color compositions, Discr. Math., 308 (2008), 1732-1740.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee, and Jung Hoon Han, Proposal of a spin-one chain model with competing dimer and trimer interactions, arXiv:1709.01344 [cond-mat.str-el], 2017.
J. Pan, Multiple Binomial Transforms and Families of Integer Sequences, J. Int. Seq. 13 (2010), 10.4.2. Absolute values of F^(-2).
C. Pita, On s-Fibonomials, J. Int. Seq. 14 (2011) # 11.3.7.
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
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.
John 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.
J. Salas and A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279-373, arXiv:0711.1738. Mentions this sequence.
Luigi Santocanale, On discrete idempotent paths, arXiv:1906.05590 [math.LO], 2019.
N. J. A. Sloane, Transforms
Michael Somos, In the Elliptic Realm.
Ryan Stees, Sequences of Spiral Knot Determinants, Senior Honors Projects, Paper 84, James Madison Univ., May 2016.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
Eric Weisstein's World of Mathematics, Fibonacci Hyperbolic Functions.
Roman Witula, Binomials transformation formulae of scaled Lucas numbers, Demonstratio Math. 46 (2013), 15-27.
Roman Witula and Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math 3 (2009) 310-329, MR2555042
Index entries for "core" sequences
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (3,-1).
Index entries for two-way infinite sequences

Fibonacci A000045 = union of this sequence and A001519.
Cf. A000041, A000032, A001622, A048996, A052529, A055991, A078812, A305309, A058038 (pairwise products), A153386.
Inverse sequences A130259 and A130260.
Cf. A033888, A033890, A249450, A344212.

a001906 n = a001906_list !! n
a001906_list =
   0 : 1 : zipWith (-) (map (* 3) $ tail a001906_list) a001906_list
-- Reinhard Zumkeller, Oct 03 2011

[Fibonacci(2*n): n in [0..30]]; // Vincenzo Librandi, Sep 10 2014

with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S, card > 0), S=Sequence(U, card > 1), U=Sequence(Z, card >0)}, unlabeled]: seq(count(SeqSeqSeqL, size=n+1), n=0..28); # Zerinvary Lajos, Apr 04 2009
H := (n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4):
a := n -> `if`(n = 0, 0, H(2*n, 1, 1/2)):
seq(simplify(a(n)), n=0..30); # Peter Luschny, Sep 03 2019
A001906 := proc(n)
    combinat[fibonacci](2*n) ;
end proc:
seq(A001906(n),n=0..20) ; # R. J. Mathar, Jan 11 2024

f[n_] := Fibonacci[2n]; Array[f, 28, 0] (* or *)
LinearRecurrence[{3, -1}, {0, 1}, 28] (* Robert G. Wilson v, Jul 13 2011 *)
Take[Fibonacci[Range[0,60]],{1,-1,2}] (* Harvey P. Dale, May 23 2012 *)
Table[ ChebyshevU[n-1, 3/2], {n, 0, 30}] (* Jean-François Alcover, Jan 25 2013, after Michael Somos *)
CoefficientList[Series[(x)/(1 - 3x + x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Sep 10 2014 *)

makelist(fib(2*n),n,0,30); /* Martin Ettl, Oct 21 2012 */

numlib::fibonacci(2*n) $ n = 0..35; // Zerinvary Lajos, May 09 2008

{a(n) = fibonacci(2*n)}; /* Michael Somos, Dec 06 2002 */

{a(n) = subst( poltchebi(n+1)*4 - poltchebi(n)*6, x, 3/2)/5}; /* Michael Somos, Dec 06 2002 */

{a(n) = polchebyshev( n-1, 2, 3/2)}; /* Michael Somos Jun 18 2011 */

Vec(x/(1-3*x+x^2)+O(x^99)) \\ Charles R Greathouse IV, Oct 24 2012

def a(n, adict={0:0, 1:1}):
    if n in adict:
        return adict[n]
    adict[n]=3*a(n-1) - a(n-2)
    return adict[n] # David Nacin, Mar 04 2012

[lucas_number1(n,3,1) for n in range(27)] # Zerinvary Lajos, Jun 25 2008

[fibonacci(2*n) for n in range(0, 28)] # Zerinvary Lajos, May 15 2009

G.f.: x / (1 - 3*x + x^2). -  Simon Plouffe in his 1992 dissertation
a(n) = 3*a(n-1) - a(n-2) = A000045(2*n).
a(n) = -a(-n).
a(n) = A060921(n-1, 0), n >= 1.
a(n) = sqrt((A005248(n)^2 - 4)/5).
a(n) = A007598(n) - A007598(n-2), n > 1.
a(n) = (ap^n - am^n)/(ap-am), with ap := (3+sqrt(5))/2, am := (3-sqrt(5))/2.
Invert transform of natural numbers: a(n) = Sum_{k=1..n} k*a(n-k), a(0) = 1. - Vladeta Jovovic, Apr 27 2001
a(n) = S(n-1, 3) with S(n, x) = U(n, x/2) Chebyshev's polynomials of the 2nd kind, see A049310.
a(n) = Sum_{k=0..n} binomial(n, k)*F(k). - Benoit Cloitre, Sep 03 2002
Limit_{n->infinity} a(n)/a(n-1) = 1 + phi = (3 + sqrt(5))/2. This sequence includes all of the elements of A033888 combined with A033890.
a(0)=0, a(1)=1, a(2)=3, a(n)*a(n-2) + 1 = a(n-1)^2. - Benoit Cloitre, Dec 06 2002
a(n) = n + Sum_{k=0..n-1} Sum_{i=0..k} a(i) = n + A054452(n). - Benoit Cloitre, Jan 26 2003
a(n) = Sum_{k=1..n} binomial(n+k-1, n-k). - Vladeta Jovovic, Mar 23 2003
E.g.f.: (2/sqrt(5))*exp(3*x/2)*sinh(sqrt(5)*x/2). - Paul Barry, Apr 11 2003
Second 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
a(n) = F(n)*L(n) = A000045(n)*A000032(n). - Lekraj Beedassy, Nov 17 2003
F(2n+2) = 1, 3, 8, ... is the binomial transform of F(n+2). - Paul Barry, Apr 24 2004
Partial sums of A001519(n). - Lekraj Beedassy, Jun 11 2004
a(n) = Sum_{i=0..n-1} binomial(2*n-1-i, i)*5^(n-i-1)*(-1)^i. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n) = Sum_{k=0..n} binomial(n+k, n-k-1) = Sum_{k=0..n} binomial(n+k, 2k+1).
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*3^(n-2*k). - Paul Barry, Oct 25 2004
a(n) = (n*L(n) - F(n))/5 = Sum_{k=0..n-1} (-1)^n*L(2*n-2*k-1).
The i-th term of the sequence is the entry (1, 2) in the i-th power of the 2 X 2 matrix M = ((1, 1), (1, 2)). - Simone Severini, Oct 15 2005
Computation suggests that this sequence is the Hankel transform of A005807. The Hankel transform of {a(n)} is Det[{{a(1), ..., a(n)}, {a(2), ..., a(n+1)}, ..., {a(n), ..., a(2n-1)}}]. - John W. Layman, Jul 21 2000
a(n+1) = (A005248(n+1) - A001519(n))/2. - Creighton Dement, Aug 15 2004
a(n+1) = Sum_{i=0..n} Sum_{j=0..n} binomial(n-i, j)*binomial(n-j, i). - N. J. A. Sloane, Feb 20 2005
a(n) = (2/sqrt(5))*sinh(2*n*psi), where psi:=log(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, Apr 24 2007
a(n) = ((phi+1)^n - A001519(n))/phi with phi=(1+sqrt(5))/2. - Reinhard Zumkeller, Nov 22 2007
Row sums of triangle A135871. - Gary W. Adamson, Dec 02 2007
a(n)^2 = Sum_{k=1..n} a(2*k-1). This is a property of any sequence S(n) such that S(n) = B*S(n-1) - S(n-2) with S(0) = 0 and S(1) = 1 including {0,1,2,3,...} where B = 2. - Kenneth J Ramsey, Mar 23 2008
a(n) = 1/sqrt(5)*(phi^(2*n+2) - phi^(-2*n-2)), where phi = (1+sqrt(5))/2, the golden ratio. - Udita Katugampola (SIU), Sep 24 2008
If p[i] = i and if A is Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i<=j), A[i,j] = -1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, May 02 2010
If p[i] = Stirling2(i,2) and if A is the Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i<=j), A[i,j] = -1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = det(A). - Milan Janjic, May 08 2010
a(n) = F(2*n+10) mod F(2*n+5).
a(n) = 1 + a(n-1) + Sum_{i=1..n-1} a(i), with a(0)=0. - Gary W. Adamson, Feb 19 2011
a(n) is equal to the permanent of the (n-1) X (n-1) Hessenberg matrix with 3's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - John M. Campbell, Jun 09 2011
a(n), n > 1 is equal to the determinant of an (n-x) X (n-1) tridiagonal matrix with 3's in the main diagonal, 1's in the super and subdiagonals, and the rest 0's. - Gary W. Adamson, Jun 27 2011
a(n) = b such that Integral_{x=0..Pi/2} sin(n*x)/(3/2-cos(x)) dx = c + b*log(3). - Francesco Daddi, Aug 01 2011
a(n+1) = Sum_{k=0..n} A101950(n,k)*2^k. - Philippe Deléham, Feb 10 2012
G.f.: A(x) = x/(1-3*x+x^2) = G(0)/sqrt(5); where G(k)= 1 -(a^k)/(1 - b*x/(b*x - 2*(a^k)/G(k+1))), a = (7-3*sqrt(5))/2, b = 3+sqrt(5), if |x|<(3-sqrt(5))/2 = 0.3819660...; (continued fraction 3 kind, 3-step ). - Sergei N. Gladkovskii, Jun 25 2012
a(n) = 2^n*b(n;1/2) = -b(n;-1), where b(n;d), n=0,1,...,d, denote the delta-Fibonacci numbers defined in comments to A000045 (see also Witula's et al. papers). - Roman Witula, Jul 12 2012
Product_{n>=1} (1 + 1/a(n)) = 1 + sqrt(5). - Peter Bala, Dec 23 2012
Product_{n>=2} (1 - 1/a(n)) = (1/6)*(1 + sqrt(5)). - Peter Bala, Dec 23 2012
G.f.: x/(1-2*x) + x^2/(1-2*x)/(Q(0)-x) where Q(k) = 1 - x/(x*k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Feb 23 2013
G.f.: G(0)/2 - 1, where G(k) = 1 + 1/( 1 - x/(x + (1-x)^2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013
G.f.: 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 17 2013
Sum_{n>=1} 1/(a(n) + 1/a(n)) = 1. Compare with A001519, A049660 and A049670. - Peter Bala, Nov 29 2013
a(n) = U(n-1,3/2) where U(n-1,x) is Chebyshev polynomial of the second kind. - Milan Janjic, Jan 25 2015
The o.g.f. A(x) satisfies A(x) + A(-x) + 6*A(x)*A(-x) = 0. The o.g.f. for A004187 equals -A(sqrt(x))*A(-sqrt(x)). - Peter Bala, Apr 02 2015
For n > 1, a(n) = (3*F(n+1)^2 + 2*F(n-2)*F(n+1) - F(n-2)^2)/4. - J. M. Bergot, Feb 16 2016
For n > 3, a(n) = floor(MA) - 4 for n even and floor(MA) + 5 for n odd.  MA is the maximum area of a quadrilateral with lengths of sides in order L(n), L(n), F(n-3), F(n+3), with L(n)=A000032(n). The ratio of the longer diagonal to the shorter approaches 5/3. - J. M. Bergot, Feb 16 2016
a(n+1) = Sum_{j=0..n} Sum_{k=0..j} binomial(n-j,k)*binomial(j,k)*2^(j-k). - Tony Foster III, Sep 18 2017
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i,k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n) = Sum_{k=1..A000041(n)} A305309(n, k), n >= 1. Also row sums of triangle A078812.- Wolfdieter Lang, May 31 2018
a(n) = H(2*n, 1, 1/2) for n > 0 where H(n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4). - Peter Luschny, Sep 03 2019
Sum_{n>=1} 1/a(n) = A153386. - Amiram Eldar, Oct 04 2020
a(n) = A249450(n) + 2. - Leo Tavares, Oct 10 2021
a(n) = -2/(sqrt(5)*tan(2*arctan(phi^(2*n)))), where phi = A001622 is the golden ratio. - Diego Rattaggi, Nov 21 2021
a(n) = sinh(2*n*arcsinh(1/2))/sqrt(5/4). - Peter Luschny, May 21 2022
From Amiram Eldar, Dec 02 2024: (Start)
Product_{n>=1} (1 - (-1)^n/a(n)) = 1 + 1/sqrt(5) (A344212).
Product_{n>=2} (1 + (-1)^n/a(n)) = (5/6) * (1 + 1/sqrt(5)). (End)
a(n) = Sum_{k>=0} Fibonacci(2*n*k)/(Lucas(2*n)^(k+1)). - Diego Rattaggi, Jan 12 2025
Sum_{n>=0} a(n)/3^n = 3. - Diego Rattaggi, Jan 20 2025

A001003 Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers.

Original entry on oeis.org

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859, 2646723, 13648869, 71039373, 372693519, 1968801519, 10463578353, 55909013009, 300159426963, 1618362158587, 8759309660445, 47574827600981, 259215937709463, 1416461675464871

Offset: 0

N. J. A. Sloane

If you are looking for the Schroeder numbers (a.k.a. large Schroder numbers, or big Schroeder numbers), see A006318.
Yang & Jiang (2021) call these the small 2-Schroeder numbers. - N. J. A. Sloane, Mar 28 2021
There are two schools of thought about the index for the first term. I prefer the indexing a(0) = a(1) = 1, a(2) = 3, a(3) = 11, etc.
a(n) is the number of ways to insert parentheses in a string of n+1 symbols. The parentheses must be balanced but there is no restriction on the number of pairs of parentheses. The number of letters inside a pair of parentheses must be at least 2. Parentheses enclosing the whole string are ignored.
Also length of list produced by a variant of the Catalan producing iteration: replace each integer k with the list 0,1,..,k,k+1,k,...,1,0 and get the length a(n) of the resulting (flattened) list after n iterations. - Wouter Meeussen, Nov 11 2001
Stanley gives several other interpretations for these numbers.
Number of Schroeder paths of semilength n (i.e., lattice paths from (0,0) to (2n,0), with steps H=(2,0), U=(1,1) and D(1,-1) and not going below the x-axis) with no peaks at level 1. Example: a(2)=3 because among the six Schroeder paths of semilength two HH, UHD, UUDD, HUD, UDH and UDUD, only the first three have no peaks at level 1. - Emeric Deutsch, Dec 27 2003
a(n+1) is the number of Dyck n-paths in which the interior vertices of the ascents are colored white or black. - David Callan, Mar 14 2004
Number of possible schedules for n time slots in the first-come first-served (FCFS) printer policy.
Also row sums of A086810, A033282, A126216. - Philippe Deléham, May 09 2004
a(n+1) is the number of pairs (u,v) of same-length compositions of n, 0's allowed in u but not in v and u dominates v (meaning u_1 >= v_1, u_1 + u_2 >= v_1 + v_2 and so on). For example, with n=2, a(3) counts (2,2), (1+1,1+1), (2+0,1+1). - David Callan, Jul 20 2005
The big Schroeder number (A006318) is the number of Schroeder paths from (0,0) to (n,n) (subdiagonal paths with steps (1,0) (0,1) and (1,1)). These paths fall in two classes: those with steps on the main diagonal and those without. These two classes are equinumerous and the number of paths in either class is the little Schroeder number a(n) (half the big Schroeder number). - Marcelo Aguiar (maguiar(AT)math.tamu.edu), Oct 14 2005
With offset 0, a(n) = number of (colored) Motzkin (n-1)-paths with each upstep U getting one of 2 colors and each flatstep F getting one of 3 colors. Example. With their colors immediately following upsteps/flatsteps, a(2) = 3 counts F1, F2, F3 and a(3)=11 counts U1D, U2D, F1F1, F1F2, F1F3, F2F1, F2F2, F2F3, F3F1, F3F2, F3F3. - David Callan, Aug 16 2006
Shifts left when INVERT transform applied twice. - Alois P. Heinz, Apr 01 2009
Number of increasing tableaux of shape (n,n). An increasing tableau is a semistandard tableaux with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 3 because of the three tableaux (12)(34), (13)(24), (12)(23). - Oliver Pechenik, Apr 22 2014
Number of ordered trees with no vertex of outdegree 1 and having n+1 leaves (called sometimes Schröder trees). - Emeric Deutsch, Dec 13 2014
Number of dissections of a convex (n+2)-gon by nonintersecting diagonals. Example: a(2)=3 because for a square ABCD we have (i) no diagonal, (ii) dissection with diagonal AC, and (iii) dissection with diagonal BD. - Emeric Deutsch, Dec 13 2014
The little Schroeder numbers are the moments of the Marchenko-Pastur law for the case c=2 (although the moment m0 is 1/2 instead of 1): 1/2, 1, 3, 11, 45, 197, 903, ...  - Jose-Javier Martinez, Apr 07 2015
Number of generalized Motzkin paths with no level steps at height 0, from (0,0) to (2n,0), and consisting of steps U=(1,1), D=(1,-1) and H2=(2,0). For example, for n=3, we have the 11 paths: UDUDUD, UUDDUD, UDUUDD, UH2DUD, UDUH2D, UH2H2D, UUDUDD, UUUDDD, UUH2DD, UUDH2D, UH2UDD. - José Luis Ramírez Ramírez, Apr 20 2015
REVERT transform of A225883. - Vladimir Reshetnikov, Oct 25 2015
Total number of (nonempty) faces of all dimensions in the associahedron K_{n+1} of dimension n-1. For example, K_4 (a pentagon) includes 5 vertices and 5 edges together with K_4 itself (5 + 5 + 1 = 11), while K_5 includes 14 vertices, 21 edges and 9 faces together with K_5 itself (14 + 21 + 9 + 1 = 45). - Noam Zeilberger, Sep 17 2018
a(n) is the number of interval posets of permutations with n minimal elements that have exactly two realizers, up to a shift by 1 in a(4). See M. Bouvel, L. Cioni, B. Izart, Theorem 17 page 13. - Mathilde Bouvel, Oct 21 2021
a(n) is the number of sequences of nonnegative integers (u_1, u_2, ..., u_n) such that (i) u_1 = 1, (ii) u_i <= i for all i, (iii) the nonzero u_i are weakly increasing. For example, a(2) = 3 counts 10, 11, 12, and a(3) = 11 counts 100, 101, 102, 103, 110, 111, 112, 113, 120, 122, 123. See link below. - David Callan, Dec 19 2021
a(n) is the number of parking functions of size n avoiding the patterns 132 and 213. - Lara Pudwell, Apr 10 2023
a(n+1) is the number of Schroeder paths from (0,0) to (2n,0) in which level steps at height 0 come in 2 colors. - Alexander Burstein, Jul 23 2023

			G.f. = 1 + x + 3*x^2 + 11*x^3 + 45*x^4 + 197*x^5 + 903*x^6 + 4279*x^7 + ...
a(2) = 3: abc, a(bc), (ab)c; a(3) = 11: abcd, (ab)cd, a(bc)d, ab(cd), (ab)(cd), a(bcd), a(b(cd)), a((bc)d), (abc)d, (a(bc))d, ((ab)c)d.
Sum over partitions formula: a(3) = 2*a(0)*a(2) + 1*a(1)^2 + 3*(a(0)^2)*a(1) + 1*a(0)^4 = 6 + 1 + 3 + 1 = 11.
a(4) = 45 since the top row of Q^3 = (11, 14, 12, 8, 0, 0, 0, ...); (11 + 14 + 12 + 8) = 45.

D. Arques and A. Giorgetti, Une bijection géometrique entre une famille d'hypercartes et une famille de polygones énumérées par la série de Schroeder, Discrete Math., 217 (2000), 17-32.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
N. Bernasconi et al., On properties of random dissections and triangulations, Combinatorica, 30 (6) (2010), 627-654.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 618.
Peter J. Cameron, Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See p. 155, also p. 179, line -9. - N. J. A. Sloane, Apr 18 2014
C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 57.
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
Emeric Deutsch, A bijective proof of an equation linking the Schroeder numbers, large and small, Discrete Math., 241 (2001), 235-240.
Tomislav Doslic and Darko Veljan, Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From N. J. A. Sloane, May 01 2012
Michael Drmota, Anna de Mier, and Marc Noy, Extremal statistics on non-crossing configurations. Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (2). - N. J. A. Sloane, May 18 2014
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing permutations, Discrete Math., 204 (1999), 203-229, Section 3.1.
D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.
Wolfgang Gatterbauer and Dan Suciu, Dissociation and propagation for approximate lifted inference with standard relational database management systems, The VLDB Journal, February 2017, Volume 26, Issue 1, pp. 5-30; DOI 10.1007/s00778-016-0434-5
Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
D. Gouyou-Beauchamps and B. Vauquelin, Deux propriétés combinatoires des nombres de Schroeder, Theor. Inform. Appl., 22 (1988), 361-388.
N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
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.
M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
D. E. Knuth, The Art of Computer Programming, Vol. 1, various sections (e.g. p. 534 of 2nd ed.).
D. E. Knuth, The Art of Computer Programming, Vol. 1, (p. 539 of 3rd ed.).
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.2.1.6, Problem 66, p. 479.
J. S. Lew, Polynomial enumeration of multidimensional lattices, Math. Systems Theory, 12 (1979), 253-270.
Ana Marco and J.-J. Martinez, A total positivity property of the Marchenko-Pastur Law, Electronic Journal of Linear Algebra, 30 (2015), #7.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
L. Ozsvart, Counting ordered graphs that avoid certain subgraphs, Discr. Math., 339 (2016), 1871-1877.
R. C. Read, On general dissections of a polygon, Aequat. Mathem. 18 (1978) 370-388, Table 6
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 168.
E. Schroeder, Vier combinatorische Probleme, Zeit. f. Math. Phys., 15 (1870), 361-376.
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. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 178; see page 239, Exercise 6.39b.
H. N. V. Temperley and D. G. Rogers, A note on Baxter's generalization of the Temperley-Lieb operators, pp. 324-328 of Combinatorial Mathematics (Canberra, 1977), Lect. Notes Math. 686, 1978.
I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 198.
Sheng-Liang Yang and Mei-yang Jiang, The m-Schröder paths and m-Schröder numbers, Disc. Math. (2021) Vol. 344, Issue 2, 112209. doi:10.1016/j.disc.2020.112209. See Table 1.

Seiichi Manyama, Table of n, a(n) for n = 0..1312 (first 200 terms from T. D. Noe)
J. Abate and W. Whitt, Integer Sequences from Queueing Theory, J. Int. Seq. 13 (2010), 10.5.5, p_n(1).
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Marcelo Aguiar and Walter Moreira, Combinatorics of the free Baxter algebra, arXiv:math/0510169 [math.CO], 2005-2007, see Corollary 3.3.iii.
Yu Hin Au, Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers, arXiv:1912.00555 [math.CO], 2019.
Axel Bacher, Directed and multi-directed animals on the king's lattice, arXiv preprint arXiv:1301.1365 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 04 2013
Axel Bacher, Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths, arXiv:1802.06030 [cs.DS], 2018.
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.
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo and Matteo Silimbani, Ascending runs in permutations and valued Dyck paths, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 445-463.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, J. Integer Sequ., Vol. 9 (2006), Article 06.2.4.
Paul Barry, Generalized Catalan Numbers, Hankel Transforms and Somos-4 Sequences , J. Int. Seq. 13 (2010) #10.7.2.
Paul Barry, Comparing two matrices of generalized moments defined by continued fraction expansions, arXiv preprint arXiv:1311.7161 [math.CO], 2013 and J. Int. Seq. 17 (2014) # 14.5.1.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8.
Karin Baur and P. P. Martin, The fibres of the Scott map on polygon tilings are the flip equivalence classes, arXiv preprint arXiv:1601.05080 [math.CO], 2016.
Karin Baur and Paul P. Martin, A generalised Euler-Poincaré formula for associahedra, arXiv:1711.04986 [math.CO], 2017.
Arkady Berenstein, Vladimir Retakh, Christophe Reutenauer and Doron Zeilberger, The Reciprocal of Sum_{n >= 0} a^n b^n for non-commuting a and b, Catalan numbers and non-commutative quadratic equations, arXiv preprint arXiv:1206.4225 [math.CO], 2012.
Julia E. Bergner, Cedric Harper, Ryan Keller and Mathilde Rosi-Marshall, Action graphs, planar rooted forests, and self-convolutions of the Catalan numbers, arXiv:1807.03005 [math.CO], 2018.
F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
D. Birmajer, J. B. Gil and M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
Daniel Birmajer and Juan B. Gil, Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
Natasha Blitvić and Einar Steingrímsson, Permutations, moments, measures, arXiv:2001.00280 [math.CO], 2020.
J. Bloom and A, Burstein, Egge triples and unbalanced Wilf-equivalence, arXiv preprint arXiv:1410.0230 [math.CO], 2014.
Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003 [math.CO], 2013.
Henry Bottomley, Illustration of initial terms
Mathilde Bouvel, Cedric Chauve, Marni Mishna and Dominique Rossin, Average-case analysis of perfect sorting by reversals, arXiv preprint arXiv:1201.0940 [cs.DM], 2012.
M. Bouvel, L. Cioni and B. Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021. See Theorem 17 p. 13.
Kevin Brown, Hipparchus on Compound Statements, 1994-2010.
Alexander Burstein and Opel Jones, Enumeration of Dumont permutations avoiding certain four-letter patterns, arXiv:2002.12189 [math.CO], 2020.
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
Freddy Cachazo, Karen Yeats and Samuel Yusim, Compatible Cycles and CHY Integrals, arXiv:1907.12661 [math-ph], 2019.
Fangfang Cai, Qing-Hu Hou, Yidong Sun and Arthur L.B. Yang, Combinatorial identities related to 2X2 submatrices of recursive matrices, arXiv:1808.05736 [math.CO], 2018.
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.
David Callan, Some bijections for lattice paths, arXiv:2112.05241 [math.CO], 2021.
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.
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
Grégory Chatel, Vincent Pilaud and Viviane Pons, The weak order on integer posets, arXiv:1701.07995 [math.CO], 2017.
W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns, arXiv:math/0504342 [math.CO], 2005.
William Y. C. Chen and Carol J. Wang, Noncrossing Linked Partitions and Large (3, 2)-Motzkin Paths, Discrete Math., 312 (2012), 1918-1922. - _N. J. A. Sloane_, Jun 08 2012
Z. Chen and H. Pan, Identities involving weighted Catalan, Schröder and Motzkin Paths, arXiv:1608.02448 [math.CO] (2016), eq (1.13) a=1, b=2.
J. Cigler, Ramanujan's q-continued fractions and Schröder-like numbers, arXiv:1210.0372 [math.HO], 2012. - _N. J. A. Sloane_, Dec 29 2012
J. Cigler, Hankel determinants of some polynomial sequences, arXiv:1211.0816 [math.CO], 2012.
Dennis E. Davenport, Louis W. Shapiro and Leon C. Woodson, A bijection between the triangulations of convex polygons and ordered trees, Integers (2020) Vol. 20, Article #A8.
D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths, J. Int. Seq. 13 (2010) # 10.9.2.
Vesselin Drensky, Graded Algebras, Algebraic Functions, Planar Trees, and Elliptic Integrals, arXiv:2004.05596 [math.RA], 2020, see p. 20.
Rosena R. X. Du, Xiaojie Fan and Yue Zhao, Enumeration on row-increasing tableaux of shape 2 X n, arXiv:1803.01590 [math.CO], 2018.
I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
S.-P. Eu and T.-S. Fu, A simple proof of the Aztec diamond problem, arXiv:math/0412041 [math.CO], 2004.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see pages 69, 474-475, etc.
Oisín Flynn-Connolly, E_n-coalgebras in simplicial sets, GitHub, Leiden Univ. (Netherlands, 2025). See p. 24.
D. Foata and D. Zeilberger, A Classic Proof of a Recurrence for a Very Classical Sequence, arXiv:math/9805015 [math.CO], 1998.
D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence
Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
N. Gabriel, K. Peske, L. Pudwell and S. Tay, Pattern Avoidance in Ternary Trees, J. Int. Seq. 15 (2012) # 12.1.5.
W. Gatterbauer and D. Suciu, Approximate Lifted Inference with Probabilistic Databases, arXiv preprint arXiv:1412.1069 [cs.DB], 2014.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
Evangelos Georgiadis, Akihiro Munemasa and Hajime Tanaka, A note on super Catalan numbers, arXiv:1101.1579 [math.CO], 2011-2012.
Olivier Gérard, Illustration of initial terms (a)
Olivier Gérard, Illustration of initial terms (b)
Étienne Ghys, A Singular Mathematical Promenade, arXiv:1612.06373, 2016, also, The Mathematical Intelligencer (2018) 40.2, 85-88.
Samuele Giraudo, Pluriassociative algebras II: The polydendriform operad and related operads, arXiv:1603.01394 [math.CO], 2016.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Li Guo and Jun Pei, Averaging algebras, Schröder numbers, rooted trees and operads, arXiv preprint arXiv:1401.7386 [math.RA], 2014.
Guo-Niu Han, Enumeration of Standard Puzzles
Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]
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.
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 42 [Dead link]
St. John Kettle, Letter to N. J. A. Sloane, 1982.
Anton Khoroshkin and Thomas Willwacher, Real moduli space of stable rational curves revised, arXiv:1905.04499 [math.AT], 2019.
A. Kirillov, On Some Quadratic Algebras I 1/2: Combinatorics of Dunkl and Gaudin Elements, Schubert, Grothendieck, Fuss-Catalan, Universal Tutte and Reduced Polynomials, arXiv preprint arXiv:1502.00426 [math.RT], 2016.
E. Krasko and A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.
G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973).
G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Letter to N. J. A. Sloane, 1978.
V. V. Kruchinin and D. V. Kruchinin, A Method for Obtaining Generating Function for Central Coefficients of Triangles, arXiv preprint arXiv:1206.0877 [math.CO], 2012, and J. Int. Seq. 15 (2012) #12.9.3
V. Kurauskas, On graphs containing few disjoint excluded minors. Asymptotic number and structure of graphs containing few disjoint minors K_4, arXiv preprint arXiv:1504.08107 [math.CO], 2015. See Section 8.1.
J. S. Lew, Letter to N. J. A. Sloane, Sep 05 1978
Huyile Liang, Jeffrey Remmel and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 11.
Peter Luschny, The Lost Catalan Numbers And The Schröder Tableaux.
A. Marco and J.-J. Martinez, A total positivity property of the Marchenko-Pastur Law, Electronic Journal of Linear Algebra, Volume 30 (2015), pp. 106-117.
Peter McCalla and Asamoah Nkwanta, Catalan and Motzkin Integral Representations, arXiv:1901.07092 [math.NT], 2019.
D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, Discrete Applied Mathematics, Volume 144, Issue 3, 2004, pp. 359-373, ISSN 0166-218X.
W. Mlotkowski and K. A. Penson, The probability measure corresponding to 2-plane trees, ArXiv preprint arXiv:1304.6544 [math.PR], 2013.
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
G. Muntingh, Implicit Divided Differences, Little Schröder Numbers, and Catalan Numbers, arXiv preprint arXiv:1204.2709 [math.CO], 2012, and J. Int. Seq. 15 (2012) #12.6.5.
Jean-Christophe Novelli and Jean-Yves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959 [math.CO], 2012.
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
O. Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, arXiv:1209.1355 [math.CO], 2012-2014.
O. Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory A, 125 (2014), 357-378.
R. A. Perez, A brief but historic article of Siegel, Notices AMS, 58 (2011), 558-566.
E. Pergola and R. A. Sulanke, Schroeder Triangles, Paths, and Parallelogram Polyominoes, J. Integer Sequences, 1 (1998), #98.1.7.
Vincent Pilaud, Pebble trees, arXiv:2205.06686 [math.CO], 2022.
Vincent Pilaud and V. Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016.
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012.
Feng Qi, Xiao-Ting Shi, and Bai-Ni Guo, Integral representations of the large and little Schröder numbers, Preprint, 2016.
Feng Qi and Bai-Ni Guo, Some explicit and recursive formulas of the large and little Schröder numbers, Arab Journal of Mathematical Sciences, June 2016.
Marko Riedel, Computation of the asymptotic by elementary means
E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]
L. W. Shapiro & N. J. A. Sloane, Correspondence, 1976
M. Shattuck, On the zeros of some polynomials with combinatorial coefficients, Annales Mathematicae et Informaticae, 42 (2013) pp. 93-101.
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, arXiv:math/0312448 [math.CO], 2003.
N. J. A. Sloane, Transforms
N. J. A. Sloane, Illustrations of rooted planar trees with 2, 3, and 4 endpoints, illustrating a(1)=1, a(2)=3, a(4)=11.
L. M. Smiley, Variants of Schroeder Dissections, arXiv:math/9907057 [math.CO], 1999.
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Hipparchus, Plutarch, Schröder, and Hough, Amer. Math. Monthly, 104, 1997, 344-350.
Y. Sun and Z. Wang, Consecutive pattern avoidances in non-crossing trees, Graph. Combinat. 26 (2010) 815-832
Anthony Van Duzer, Subtrees of a Given size in Schroeder Trees, arXiv:1904.05525 [math.CO], 2019.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See p. 12.
Eric Weisstein's World of Mathematics, Bracketing
Eric Weisstein's World of Mathematics, Super Catalan Number
Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6.
Wen-jin Woan, A Relation Between Restricted and Unrestricted Weighted Motzkin Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.7.
Wikipedia, Schroeder-Hipparchus numbers.
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.
Index entries for sequences related to parenthesizing
Index entries for "core" sequences

See A000081, A000108, A001190, A001699, for other ways to count parentheses.
Row sums of A033282, A033877, A086810, A126216.
Right-hand column 1 of convolution triangle A011117.
Column 1 of A336573. Column 0 of A104219.
The sequences listed in Yang-Jiang's Table 1 appear to be A006318, this sequence, A027307, A034015, A144097, A243675, A260332, A243676. - N. J. A. Sloane, Mar 28 2021
Cf. A000041, A000311, A001263, A003480, A006125, A010683, A025240, A035011.
Cf. A048996, A054726, A059435, A065096, A080243, A085403, A086456, A086616.
Cf. A086810, A088617, A104858, A110440, A111785, A114710, A118376, A126216.
Cf. A139685, A144156, A144944, A153881, A186826.
Cf. A006318 (Schroeder numbers).

a001003 = last . a144944_row  -- Reinhard Zumkeller, May 11 2013

R:=PowerSeriesRing(Rationals(), 50);
Coefficients(R!( (1+x -Sqrt(1-6*x+x^2) )/(4*x) )); // G. C. Greubel, Oct 27 2024

t1 := (1/(4*x))*(1+x-sqrt(1-6*x+x^2)); series(t1,x,40);
invtr:= proc(p) local b; b:= proc(n) option remember; local i; `if`(n<1, 1, add(b(n-i) *p(i-1), i=1..n+1)) end end: a:='a': f:= (invtr@@2)(a): a:= proc(n) if n<0 then 1 else f(n-1) fi end: seq(a(n), n=0..30); # Alois P. Heinz, Apr 01 2009
# Computes n -> [a[0],a[1],..,a[n]]
A001003_list := proc(n) local j,a,w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := a[w-1]+2*add(a[j]*a[w-j-1],j=1..w-1) od;
convert(a,list) end: A001003_list(100); # Peter Luschny, May 17 2011

Table[Length[Flatten[Nest[ #/.a_Integer:> Join[Range[0, a + 1], Range[a, 0, -1]] &, {0}, n]]], {n, 0, 10}]; Sch[ 0 ] = Sch[ 1 ] = 1; Sch[ n_Integer ] := Sch[ n ] = (3(2n - 1)Sch[ n - 1 ] - (n - 2)Sch[ n - 2 ])/(n + 1); Array[ Sch, 24, 0]
(* Second program: *)
a[n_] := Hypergeometric2F1[-n + 1, n + 2, 2, -1]; a[0] = 1; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Nov 09 2011, after Vladeta Jovovic *)
a[ n_] := SeriesCoefficient[ (1 + x - Sqrt[1 - 6 x + x^2]) / (4 x), {x, 0, n}]; (* Michael Somos, Aug 26 2015 *)
Table[(KroneckerDelta[n] - GegenbauerC[n+1, -1/2, 3])/4, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)
a[n_] := -LegendreP[n, -1, 2, 3] I / Sqrt[2]; a[0] = 1;
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 16 2019 *)
a[1]:=1; a[2]:=1; a[n_]:=a[n] = a[n-1]+2 Sum[a[k] a[n-k], {k,2,n-1}]; Map[a, Range[24]] (* Oliver Seipel, Nov 03 2024, after Schröder 1870 *)
CoefficientList[InverseSeries[Series[x/(Series[(1 - x)/(1 - 2  x), {x, 0, 24}]), {x, 0, 24}]]/x, x] (* Mats Granvik, Jun 30 2025 *)

{a(n) = if( n<1, n==0, sum( k=0, n, 2^k * binomial(n, k) * binomial(n, k-1) ) / (2*n))}; /* Michael Somos, Mar 31 2007 */

{a(n) = my(A); if( n<1, n==0, n--; A = x * O(x^n); n! * simplify( polcoef( exp(3*x + A) * besseli(1, 2*x * quadgen(8) + A), n)))}; /* Michael Somos, Mar 31 2007 */

{a(n) = if( n<0, 0, n++; polcoef( serreverse( (x - 2*x^2) / (1 - x) + x * O(x^n)), n))}; /* Michael Somos, Mar 31 2007 */

N=30; x='x+O('x^N); Vec( (1+x-(1-6*x+x^2)^(1/2))/(4*x) ) \\ Hugo Pfoertner, Nov 19 2018

# The objective of this implementation is efficiency.
# n -> [a(0), a(1), ..., a(n)]
def A001003_list(n):
    a = [0 for i in range(n)]
    a[0] = 1
    for w in range(1, n):
        s = 0
        for j in range(1, w):
            s += a[j]*a[w-j-1]
        a[w] = a[w-1]+2*s
    return a
# Peter Luschny, May 17 2011

from gmpy2 import divexact
A001003 = [1, 1]
for n in range(3,10**3):
    A001003.append(divexact(A001003[-1]*(6*n-9)-(n-3)*A001003[-2],n))
# Chai Wah Wu, Sep 01 2014

# Generalized algorithm of L. Seidel
def A001003_list(n) :
    D = [0]*(n+1); D[1] = 1/2
    b = True; h = 2; R = [1]
    for i in range(2*n-2) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1;
        else :
            for k in range(1,h, 1) : D[k] += D[k-1]
            R.append(D[h-1]);
        b = not b
    return R
A001003_list(24) # Peter Luschny, Jun 02 2012

D-finite with recurrence: (n+1) * a(n) = (6*n-3) * a(n-1) - (n-2) * a(n-2) if n>1. a(0) = a(1) = 1.
a(n) = 3*a(n-1) + 2*A065096(n-2) (n>2). If g(x) = 1 + 3*x + 11*x^2 + 45*x^3 + ... + a(n)*x^n + ..., then g(x) = 1 + 3(x*g(x)) + 2(x*g(x))^2, g(x)^2 = 1 + 6*x + 31*x^2 + 156*x^3 + ... + A065096(n)*x^n + ... - Paul D. Hanna, Jun 10 2002
a(n+1) = -a(n) + 2*Sum_{k=1..n} a(k)*a(n+1-k). - Philippe Deléham, Jan 27 2004
a(n-2) = (1/(n-1))*Sum_{k=0..n-3} binomial(n-1,k+1)*binomial(n-3,k)*2^(n-3-k) for n >= 3 [G. Polya, Elemente de Math., 12 (1957), p. 115.] - N. J. A. Sloane, Jun 13 2015
G.f.: (1 + x - sqrt(1 - 6*x + x^2) )/(4*x) = 2/(1 + x + sqrt(1 - 6*x + x^2)).
a(n) ~ W*(3+sqrt(8))^n*n^(-3/2) where W = (1/4)*sqrt((sqrt(18)-4)/Pi) [See Knuth I, p. 534, or Perez. Note that the formula on line 3, page 475 of Flajolet and Sedgewick seems to be wrong - it has to be multiplied by 2^(1/4).] - N. J. A. Sloane, Apr 10 2011
The correct asymptotic for this sequence is a(n) ~ W*(3+sqrt(8))^n*n^(-3/2), where W = (1+sqrt(2))/(2*2^(3/4)*sqrt(Pi)) = 0.404947065905750651736243... Result in book by D. Knuth (p. 539 of 3rd edition, exercise 12) is for sequence b(n), but a(n) = b(n+1)/2. Therefore is asymptotic a(n) ~ b(n) * (3+sqrt(8))/2. - Vaclav Kotesovec, Sep 09 2012
The Hankel transform of this sequence gives A006125 = 1, 1, 2, 8, 64, 1024, ...; example: det([1, 1, 3, 11; 1, 3, 11, 45; 3, 11, 45, 197; 11, 45, 197, 903]) = 2^6 = 64. - Philippe Deléham, Mar 02 2004
a(n+1) = Sum_{k=0..floor((n-1)/2)} 2^k * 3^(n-1-2k) * binomial(n-1, 2k) * Catalan(k). This formula counts colored Dyck paths by the same parameter by which Touchard's identity counts ordinary Dyck paths: number of DDUs (U=up step, D=down step). See also Gouyou-Beauchamps reference. - David Callan, Mar 14 2004
From Paul Barry, May 24 2005: (Start)
a(n) = (1/(n+1))*Sum_{k=0..n} C(n+1, k)*C(2n-k, n)*(-1)^k*2^(n-k) [with offset 0].
a(n) = (1/(n+1))*Sum_{k=0..n} C(n+1, k+1)*C(n+k, k)*(-1)^(n-k)*2^k [with offset 0].
a(n) = Sum_{k=0..n} (1/(k+1))*C(n, k)*C(n+k, k)*(-1)^(n-k)*2^k [with offset 0].
a(n) = Sum_{k=0..n} A088617(n, k)*(-1)^(n-k)*2^k [with offset 0]. (End)
E.g.f. of a(n+1) is exp(3*x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - Vladeta Jovovic, Mar 31 2004
Reversion of (x-2*x^2)/(1-x) is g.f. offset 1.
For n>=1, a(n) = Sum_{k=0..n} 2^k*N(n, k) where N(n, k) = (1/n)*C(n, k)*C(n, k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 10 2003 [This formula counts colored Dyck paths by number of peaks, which is easy to see because the Narayana numbers count Dyck paths by number of peaks and the number of peaks determines the number of interior ascent vertices.]
a(n) = Sum_{k=0..n} A088617(n, k)*2^k*(-1)^(n-k). - Philippe Deléham, Jan 21 2004
For n > 0, a(n) = (1/(n+1)) * Sum_{k = 0 .. n-1} binomial(2*n-k, n) * binomial(n-1, k). This formula counts colored Dyck paths (as above) by number of white vertices. - David Callan, Mar 14 2004
a(n-1) = (d^(n-1)/dx^(n-1))((1-x)/(1-2*x))^n/n!|_{x=0}. (For a proof see the comment on the unsigned row sums of triangle A111785.)
From Wolfdieter Lang, Sep 12 2005: (Start)
a(n) = (1/n)*Sum_{k=1..n} binomial(n, k)*binomial(n+k, k-1).
a(n) = hypergeom([1-n, n+2], [2], -1), n>=1. (End)
a(n) = hypergeom([1-n, -n], [2], 2) for n>=0. - Peter Luschny, Sep 22 2014
a(m+n+1) = Sum_{k>=0} A110440(m, k)*A110440(n, k)*2^k = A110440(m+n, 0). - Philippe Deléham, Sep 14 2005
Sum over partitions formula (reference Schroeder paper p. 362, eq. (1) II). Number the partitions of n according to Abramowitz-Stegun pp. 831-832 (see reference under A105805) with k=1..p(n)= A000041(n). For n>=1: a(n-1) = Sum_{k=2..p(n)} A048996(n,k)*a(1)^e(k, 1)*a(1)^e(k, 2)*...*a(n-2)^e(k, n-1) if the k-th partition of n in the mentioned order is written as (1^e(k, 1), 2^e(k, 2), ..., (n-1)e(k, n-1)). Note that the first (k=1) partition (n^1) has to be omitted. - Wolfdieter Lang, Aug 23 2005
Starting (1, 3, 11, 45, ...), = row sums of triangle A126216 = A001263 * [1, 2, 4, 8, 16, ...]. - Gary W. Adamson, Nov 30 2007
From Paul Barry, May 15 2009: (Start)
G.f.: 1/(1+x-2x/(1+x-2x/(1+x-2x/(1+x-2x/(1-.... (continued fraction).
G.f.: 1/(1-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction).
G.f.: 1/(1-x-2x^2/(1-3x-2x^2/(1-3x-2x^2/(1-... (continued fraction). (End)
G.f.: 1 / (1 - x / (1 - 2*x / (1 - x / (1 - 2*x / ... )))). - Michael Somos, May 19 2013
a(n) = (LegendreP(n+1,3)-3*LegendreP(n,3))/(4*n) for n>0. - Mark van Hoeij, Jul 12 2010 [This formula is mentioned in S.-J. Kettle's 1982 letter - see link. N. J. A. Sloane, Jun 13 2015]
From Gary W. Adamson, Jul 08 2011: (Start)
a(n) = upper left term in M^n, where M is the production matrix:
  1, 1, 0, 0, 0, 0, ...
  2, 2, 2, 0, 0, 0, ...
  1, 1, 1, 1, 0, 0, ...
  2, 2, 2, 2, 2, 0, ...
  1, 1, 1, 1, 1, 1, ...
  ... (End)
From Gary W. Adamson, Aug 23 2011: (Start)
a(n) is the sum of top row terms of Q^(n-1), where Q is the infinite square production matrix:
  1, 2, 0, 0, 0, ...
  1, 1, 2, 0, 0, ...
  1, 1, 1, 2, 0, ...
  1, 1, 1, 1, 2, ...
  ... (End)
Let h(t) = (1-t)^2/(2*(1-t)^2-1) = 1/(1-(2*t+3*t^2+4*t^3+...)), an o.g.f. for A003480, then for A001003 a(n) = (1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=1. (Cf. A086810.) - Tom Copeland, Sep 06 2011
A006318(n) = 2*a(n) if n>0. - Michael Somos, Mar 31 2007
BINOMIAL transform is A118376 with offset 0. REVERT transform is A153881. INVERT transform is A006318. INVERT transform of A114710. HANKEL transform is A139685. PSUM transform is A104858. - Michael Somos, May 19 2013
G.f.: 1 + x/(Q(0) - x) where Q(k) = 1 + k*(1-x) - x - x*(k+1)*(k+2)/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013
a(n) = A144944(n,n) = A186826(n,0). - Reinhard Zumkeller, May 11 2013
a(n)=(-1)^n*LegendreP(n,-1,-3)/sqrt(2), n > 0, LegendreP(n,a,b) is the Legendre function. - Karol A. Penson, Jul 06 2013
Integral representation as n-th moment of a positive weight function W(x) = W_a(x) + W_c(x), where W_a(x) = Dirac(x)/2, is the discrete (atomic) part, and W_c(x) = sqrt(8-(x-3)^2)/(4*Pi*x) is the continuous part of W(x) defined on (3 sqrt(8),3+sqrt(8)): a(n) = int( x^n*W_a(x), x=-eps..eps ) + int( x^n*W_c(x), x = 3-sqrt(8)..3+sqrt(8) ), for any eps>0, n>=0. W_c(x) is unimodal, of bounded variation and W_c(3-sqrt(8)) = W_c(3+sqrt(8)) = 0. Note that the position of the Dirac peak (x=0) lies outside support of W_c(x). - Karol A. Penson and Wojciech Mlotkowski, Aug 05 2013
G.f.: 1 + x/G(x) with G(x) = 1 - 3*x - 2*x^2/G(x) (continued fraction). - Nikolaos Pantelidis, Dec 17 2022

cp's OEIS Frontend

A179972 Irregular table T(n,k) = A178886(n,k)/A048996(n,k) read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A127742 Triangle read by rows with shape A000041 which refines the Catalan triangle A033184 using sequence A048996.

Views

Author

Keywords

Comments

Examples

Extensions

A178802 Multiply, cell by cell, sequence A048996 by A178801.

Views

Author

Keywords

Examples

Crossrefs

Formula

A178883 Multiply, cell by cell, the sequences A096162, A048996 and A178886.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A305309 Array read by rows: a(n, k) = A048996(n, k) * A118851(n, k), n >= 1, k = 1..A000041(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A179236 Irregular triangle T(n,k) = A096162(n,k)* A036040(n,k)* A048996(n,k)*A098546(n,k)* A178886(n,k) read by rows, 1<=k<=A000041(n).

Views

Author

Keywords

Examples

Crossrefs

A179318 Triangle T(n,k) = A127742(n,k)/A048996(n,k) read by rows, k=1..A000041(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A001906 F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

MuPAD

PARI

PARI

PARI

PARI

Python

Sage

Sage

Formula

A001003 Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers.

A179236 Irregular triangle T(n,k) = A096162(n,k)* A036040(n,k)* A048996(n,k)A098546(n,k) A178886(n,k) read by rows, 1<=k<=A000041(n).