This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A001003 M2898 N1163 #744 Aug 24 2025 11:34:38
%S A001003 1,1,3,11,45,197,903,4279,20793,103049,518859,2646723,13648869,
%T A001003 71039373,372693519,1968801519,10463578353,55909013009,300159426963,
%U A001003 1618362158587,8759309660445,47574827600981,259215937709463,1416461675464871
%N A001003 Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers.
%C A001003 If you are looking for the Schroeder numbers (a.k.a. large Schroder numbers, or big Schroeder numbers), see A006318.
%C A001003 Yang & Jiang (2021) call these the small 2-Schroeder numbers. - _N. J. A. Sloane_, Mar 28 2021
%C A001003 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.
%C A001003 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.
%C A001003 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
%C A001003 Stanley gives several other interpretations for these numbers.
%C A001003 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
%C A001003 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
%C A001003 Number of possible schedules for n time slots in the first-come first-served (FCFS) printer policy.
%C A001003 Also row sums of A086810, A033282, A126216. - _Philippe Deléham_, May 09 2004
%C A001003 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
%C A001003 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
%C A001003 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
%C A001003 Shifts left when INVERT transform applied twice. - _Alois P. Heinz_, Apr 01 2009
%C A001003 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
%C A001003 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
%C A001003 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
%C A001003 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
%C A001003 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
%C A001003 REVERT transform of A225883. - _Vladimir Reshetnikov_, Oct 25 2015
%C A001003 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
%C A001003 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
%C A001003 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
%C A001003 a(n) is the number of parking functions of size n avoiding the patterns 132 and 213. - _Lara Pudwell_, Apr 10 2023
%C A001003 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
%D A001003 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.
%D A001003 Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
%D A001003 N. Bernasconi et al., On properties of random dissections and triangulations, Combinatorica, 30 (6) (2010), 627-654.
%D A001003 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 618.
%D A001003 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
%D A001003 C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
%D A001003 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 57.
%D A001003 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
%D A001003 Emeric Deutsch, A bijective proof of an equation linking the Schroeder numbers, large and small, Discrete Math., 241 (2001), 235-240.
%D A001003 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
%D A001003 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
%D A001003 I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
%D A001003 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.
%D A001003 P. Flajolet and M. Noy, Analytic combinatorics of non-crossing permutations, Discrete Math., 204 (1999), 203-229, Section 3.1.
%D A001003 D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.
%D A001003 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
%D A001003 Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
%D A001003 D. Gouyou-Beauchamps and B. Vauquelin, Deux propriétés combinatoires des nombres de Schroeder, Theor. Inform. Appl., 22 (1988), 361-388.
%D A001003 N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
%D A001003 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.
%D A001003 M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
%D A001003 D. E. Knuth, The Art of Computer Programming, Vol. 1, various sections (e.g. p. 534 of 2nd ed.).
%D A001003 D. E. Knuth, The Art of Computer Programming, Vol. 1, (p. 539 of 3rd ed.).
%D A001003 D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.2.1.6, Problem 66, p. 479.
%D A001003 J. S. Lew, Polynomial enumeration of multidimensional lattices, Math. Systems Theory, 12 (1979), 253-270.
%D A001003 Ana Marco and J.-J. Martinez, A total positivity property of the Marchenko-Pastur Law, Electronic Journal of Linear Algebra, 30 (2015), #7.
%D A001003 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.
%D A001003 L. Ozsvart, Counting ordered graphs that avoid certain subgraphs, Discr. Math., 339 (2016), 1871-1877.
%D A001003 R. C. Read, On general dissections of a polygon, Aequat. Mathem. 18 (1978) 370-388, Table 6
%D A001003 J. Riordan, Combinatorial Identities, Wiley, 1968, p. 168.
%D A001003 E. Schroeder, Vier combinatorische Probleme, Zeit. f. Math. Phys., 15 (1870), 361-376.
%D A001003 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001003 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001003 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 178; see page 239, Exercise 6.39b.
%D A001003 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.
%D A001003 I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 198.
%D A001003 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.
%H A001003 Seiichi Manyama, <a href="/A001003/b001003.txt">Table of n, a(n) for n = 0..1312</a> (first 200 terms from T. D. Noe)
%H A001003 J. Abate and W. Whitt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Whitt/whitt2.html">Integer Sequences from Queueing Theory</a>, J. Int. Seq. 13 (2010), 10.5.5, p_n(1).
%H A001003 M. Abramowitz and I. A. Stegun, eds., <a href="https://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H A001003 Ayomikun Adeniran and Lara Pudwell, <a href="https://doi.org/10.54550/ECA2023V3S3R17">Pattern avoidance in parking functions</a>, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
%H A001003 Marcelo Aguiar and Walter Moreira, <a href="https://arxiv.org/abs/math/0510169">Combinatorics of the free Baxter algebra</a>, arXiv:math/0510169 [math.CO], 2005-2007, see Corollary 3.3.iii.
%H A001003 Yu Hin Au, <a href="https://arxiv.org/abs/1912.00555">Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers</a>, arXiv:1912.00555 [math.CO], 2019.
%H A001003 Axel Bacher, <a href="https://arxiv.org/abs/1301.1365">Directed and multi-directed animals on the king's lattice</a>, arXiv preprint arXiv:1301.1365 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 04 2013
%H A001003 Axel Bacher, <a href="https://arxiv.org/abs/1802.06030">Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths</a>, arXiv:1802.06030 [cs.DS], 2018.
%H A001003 C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="https://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating functions for generating trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
%H A001003 C. Banderier and D. Merlini, <a href="https://igm.univ-mlv.fr/~fpsac/FPSAC02/ARTICLES/Banderier.pdf">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.
%H A001003 E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, <a href="https://www.mat.univie.ac.at/~slc/wpapers/s46rinaldi.html">ECO method and hill-free generalized Motzkin paths</a>, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.
%H A001003 Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo and Matteo Silimbani, <a href="https://doi.org/10.26493/1855-3974.1679.ad3">Ascending runs in permutations and valued Dyck paths</a>, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 445-463.
%H A001003 Paul Barry, <a href="https://www.cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, J. Integer Sequ., Vol. 9 (2006), Article 06.2.4.
%H A001003 Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry1/barry95r.html">Generalized Catalan Numbers, Hankel Transforms and Somos-4 Sequences </a>, J. Int. Seq. 13 (2010) #10.7.2.
%H A001003 Paul Barry, <a href="https://arxiv.org/abs/1311.7161">Comparing two matrices of generalized moments defined by continued fraction expansions</a>, arXiv preprint arXiv:1311.7161 [math.CO], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Barry3/barry291.html">J. Int. Seq. 17 (2014) # 14.5.1</a>.
%H A001003 Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.
%H A001003 Paul Barry, <a href="https://arxiv.org/abs/1910.00875">Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials</a>, arXiv:1910.00875 [math.CO], 2019.
%H A001003 Paul Barry and Aoife Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry2/barry190r.html">Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths</a>, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8.
%H A001003 Karin Baur and P. P. Martin, <a href="https://arxiv.org/abs/1601.05080">The fibres of the Scott map on polygon tilings are the flip equivalence classes</a>, arXiv preprint arXiv:1601.05080 [math.CO], 2016.
%H A001003 Karin Baur and Paul P. Martin, <a href="https://arxiv.org/abs/1711.04986">A generalised Euler-Poincaré formula for associahedra</a>, arXiv:1711.04986 [math.CO], 2017.
%H A001003 Arkady Berenstein, Vladimir Retakh, Christophe Reutenauer and Doron Zeilberger, <a href="https://arxiv.org/abs/1206.4225">The Reciprocal of Sum_{n >= 0} a^n b^n for non-commuting a and b, Catalan numbers and non-commutative quadratic equations</a>, arXiv preprint arXiv:1206.4225 [math.CO], 2012.
%H A001003 Julia E. Bergner, Cedric Harper, Ryan Keller and Mathilde Rosi-Marshall, <a href="https://arxiv.org/abs/1807.03005">Action graphs, planar rooted forests, and self-convolutions of the Catalan numbers</a>, arXiv:1807.03005 [math.CO], 2018.
%H A001003 F. R. Bernhart & N. J. A. Sloane, <a href="/A006343/a006343.pdf">Emails, April-May 1994</a>
%H A001003 D. Birmajer, J. B. Gil and M. D. Weiner, <a href="https://arxiv.org/abs/1503.05242">Colored partitions of a convex polygon by noncrossing diagonals</a>, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
%H A001003 Daniel Birmajer and Juan B. Gil, Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.
%H A001003 Natasha Blitvić and Einar Steingrímsson, <a href="https://arxiv.org/abs/2001.00280">Permutations, moments, measures</a>, arXiv:2001.00280 [math.CO], 2020.
%H A001003 J. Bloom and A, Burstein, <a href="https://arxiv.org/abs/1410.0230">Egge triples and unbalanced Wilf-equivalence</a>, arXiv preprint arXiv:1410.0230 [math.CO], 2014.
%H A001003 Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, <a href="https://arxiv.org/abs/1310.7003">Pattern-avoiding involutions: exact and asymptotic enumeration</a>, arxiv:1310.7003 [math.CO], 2013.
%H A001003 Henry Bottomley, <a href="/A001003/a001003.gif">Illustration of initial terms</a>
%H A001003 Mathilde Bouvel, Cedric Chauve, Marni Mishna and Dominique Rossin, <a href="https://arxiv.org/abs/1201.0940">Average-case analysis of perfect sorting by reversals</a>, arXiv preprint arXiv:1201.0940 [cs.DM], 2012.
%H A001003 M. Bouvel, L. Cioni and B. Izart, <a href="https://arxiv.org/abs/2110.10000">The interval posets of permutations seen from the decomposition tree perspective</a>, arXiv:2110.10000 [math.CO], 2021. See Theorem 17 p. 13.
%H A001003 Kevin Brown, <a href="https://www.mathpages.com/home/kmath397/kmath397.htm">Hipparchus on Compound Statements</a>, 1994-2010.
%H A001003 Alexander Burstein and Opel Jones, <a href="https://arxiv.org/abs/2002.12189">Enumeration of Dumont permutations avoiding certain four-letter patterns</a>, arXiv:2002.12189 [math.CO], 2020.
%H A001003 Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%H A001003 Freddy Cachazo, Karen Yeats and Samuel Yusim, <a href="https://arxiv.org/abs/1907.12661">Compatible Cycles and CHY Integrals</a>, arXiv:1907.12661 [math-ph], 2019.
%H A001003 Fangfang Cai, Qing-Hu Hou, Yidong Sun and Arthur L.B. Yang, <a href="https://arxiv.org/abs/1808.05736">Combinatorial identities related to 2X2 submatrices of recursive matrices</a>, arXiv:1808.05736 [math.CO], 2018.
%H A001003 H. Cambazard and N. Catusse, <a href="https://arxiv.org/abs/1512.06649">Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the Plane</a>, arXiv preprint arXiv:1512.06649 [cs.DS], 2015.
%H A001003 David Callan, <a href="https://arxiv.org/abs/2112.05241">Some bijections for lattice paths</a>, arXiv:2112.05241 [math.CO], 2021.
%H A001003 Naiomi T. Cameron and Asamoah Nkwanta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html">On Some (Pseudo) Involutions in the Riordan Group</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
%H A001003 P. J. Cameron, <a href="https://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102.
%H A001003 P. J. Cameron, <a href="https://dx.doi.org/10.1016/S0167-5060(08)70569-7">Some sequences of integers</a>, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
%H A001003 F. Cazals, <a href="https://algo.inria.fr/libraries/autocomb/NCC-html/NCC.html">Combinatorics of Non-Crossing Configurations</a>, Studies in Automatic Combinatorics, Volume II (1997).
%H A001003 Grégory Chatel, Vincent Pilaud and Viviane Pons, <a href="https://arxiv.org/abs/1701.07995">The weak order on integer posets</a>, arXiv:1701.07995 [math.CO], 2017.
%H A001003 W. Y. C. Chen, T. Mansour and S. H. F. Yan, <a href="https://arxiv.org/abs/math/0504342">Matchings avoiding partial patterns</a>, arXiv:math/0504342 [math.CO], 2005.
%H A001003 William Y. C. Chen and Carol J. Wang, <a href="https://arxiv.org/abs/1009.0176">Noncrossing Linked Partitions and Large (3, 2)-Motzkin Paths</a>, Discrete Math., 312 (2012), 1918-1922. - _N. J. A. Sloane_, Jun 08 2012
%H A001003 Z. Chen and H. Pan, <a href="https://arxiv.org/abs/1608.02448">Identities involving weighted Catalan, Schröder and Motzkin Paths</a>, arXiv:1608.02448 [math.CO] (2016), eq (1.13) a=1, b=2.
%H A001003 J. Cigler, <a href="https://arxiv.org/abs/1210.0372">Ramanujan's q-continued fractions and Schröder-like numbers</a>, arXiv:1210.0372 [math.HO], 2012. - _N. J. A. Sloane_, Dec 29 2012
%H A001003 J. Cigler, <a href="https://arxiv.org/abs/1211.0816">Hankel determinants of some polynomial sequences</a>, arXiv:1211.0816 [math.CO], 2012.
%H A001003 Dennis E. Davenport, Louis W. Shapiro and Leon C. Woodson, <a href="https://math.colgate.edu/~integers/u8/u8.pdf">A bijection between the triangulations of convex polygons and ordered trees</a>, Integers (2020) Vol. 20, Article #A8.
%H A001003 D. Drake, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Drake/drake.html">Bijections from Weighted Dyck Paths to Schröder Paths</a>, J. Int. Seq. 13 (2010) # 10.9.2.
%H A001003 Vesselin Drensky, <a href="https://arxiv.org/abs/2004.05596">Graded Algebras, Algebraic Functions, Planar Trees, and Elliptic Integrals</a>, arXiv:2004.05596 [math.RA], 2020, see p. 20.
%H A001003 Rosena R. X. Du, Xiaojie Fan and Yue Zhao, <a href="https://arxiv.org/abs/1803.01590">Enumeration on row-increasing tableaux of shape 2 X n</a>, arXiv:1803.01590 [math.CO], 2018.
%H A001003 I. M. H. Etherington, <a href="https://www.jstor.org/stable/3605743">Non-associate powers and a functional equation</a>, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
%H A001003 I. M. H. Etherington, <a href="/A000108/a000108_14.pdf">Some problems of non-associative combinations (I)</a>, 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.
%H A001003 S.-P. Eu and T.-S. Fu, <a href="https://arxiv.org/abs/math/0412041">A simple proof of the Aztec diamond problem</a>, arXiv:math/0412041 [math.CO], 2004.
%H A001003 P. Flajolet and R. Sedgewick, <a href="https://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see pages 69, 474-475, etc.
%H A001003 Oisín Flynn-Connolly, <a href="https://flynncoo.github.io/pdfs/papers/En_coalgebras_in_simplicial_sets%20(1).pdf">E_n-coalgebras in simplicial sets</a>, GitHub, Leiden Univ. (Netherlands, 2025). See p. 24.
%H A001003 D. Foata and D. Zeilberger, <a href="https://arxiv.org/abs/math/9805015">A Classic Proof of a Recurrence for a Very Classical Sequence</a>, arXiv:math/9805015 [math.CO], 1998.
%H A001003 D. Foata and D. Zeilberger, <a href="https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/classic.pdf">A classic proof of a recurrence for a very classical sequence</a>
%H A001003 Shishuo Fu and Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.
%H A001003 N. Gabriel, K. Peske, L. Pudwell and S. Tay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Pudwell/pudwell.html">Pattern Avoidance in Ternary Trees</a>, J. Int. Seq. 15 (2012) # 12.1.5.
%H A001003 W. Gatterbauer and D. Suciu, <a href="https://arxiv.org/abs/1412.1069">Approximate Lifted Inference with Probabilistic Databases</a>, arXiv preprint arXiv:1412.1069 [cs.DB], 2014.
%H A001003 Joël Gay and Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.
%H A001003 Evangelos Georgiadis, Akihiro Munemasa and Hajime Tanaka, <a href="https://arxiv.org/abs/1101.1579">A note on super Catalan numbers</a>, arXiv:1101.1579 [math.CO], 2011-2012.
%H A001003 Olivier Gérard, <a href="/A001003/a001003a.pdf">Illustration of initial terms (a)</a>
%H A001003 Olivier Gérard, <a href="/A001003/a001003b.pdf">Illustration of initial terms (b)</a>
%H A001003 Étienne Ghys, <a href="https://arxiv.org/abs/1612.06373">A Singular Mathematical Promenade</a>, arXiv:1612.06373, 2016, also, The Mathematical Intelligencer (2018) 40.2, 85-88.
%H A001003 Samuele Giraudo, <a href="https://arxiv.org/abs/1603.01394">Pluriassociative algebras II: The polydendriform operad and related operads</a>, arXiv:1603.01394 [math.CO], 2016.
%H A001003 Samuele Giraudo, <a href="https://arxiv.org/abs/1903.00677">Tree series and pattern avoidance in syntax trees</a>, arXiv:1903.00677 [math.CO], 2019.
%H A001003 Li Guo and Jun Pei, <a href="https://arxiv.org/abs/1401.7386">Averaging algebras, Schröder numbers, rooted trees and operads</a>, arXiv preprint arXiv:1401.7386 [math.RA], 2014.
%H A001003 Guo-Niu Han, <a href="https://www.mat.univie.ac.at/~slc/wpapers/s85han.pdf">Enumeration of Standard Puzzles</a>
%H A001003 Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a> [Cached copy]
%H A001003 Aoife Hennessy, <a href="https://www.researchgate.net/publication/277227420_A_Study_of_Riordan_Arrays_with_Applications_to_Continued_Fractions_Orthogonal_Polynomials_and_Lattice_Paths">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H A001003 Cheyne Homberger, <a href="https://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint 1410.2657 [math.CO], 2014.
%H A001003 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=42">Encyclopedia of Combinatorial Structures 42</a> [Dead link]
%H A001003 St. John Kettle, <a href="/A001003/a001003_5.pdf">Letter to N. J. A. Sloane</a>, 1982.
%H A001003 Anton Khoroshkin and Thomas Willwacher, <a href="https://arxiv.org/abs/1905.04499">Real moduli space of stable rational curves revised</a>, arXiv:1905.04499 [math.AT], 2019.
%H A001003 A. Kirillov, <a href="https://arxiv.org/abs/1502.00426">On Some Quadratic Algebras I 1/2: Combinatorics of Dunkl and Gaudin Elements, Schubert, Grothendieck, Fuss-Catalan, Universal Tutte and Reduced Polynomials</a>, arXiv preprint arXiv:1502.00426 [math.RT], 2016.
%H A001003 E. Krasko and A. Omelchenko, <a href="https://doi.org/10.37236/4129">Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees</a>, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.
%H A001003 G. Kreweras, <a href="https://www.numdam.org/item/?id=BURO_1973__20__3_0">Sur les hiérarchies de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973).
%H A001003 G. Kreweras, <a href="/A001844/a001844.pdf">Sur les hiérarchies de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)
%H A001003 G. Kreweras, <a href="https://www.numdam.org/item/?id=MSH_1976__53__5_0">Les préordres totaux compatibles avec un ordre partiel</a>, Math. Sci. Humaines No. 53 (1976), 5-30.
%H A001003 G. Kreweras, <a href="/A001003/a001003_1.pdf">Letter to N. J. A. Sloane</a>, 1978.
%H A001003 V. V. Kruchinin and D. V. Kruchinin, <a href="https://arxiv.org/abs/1206.0877">A Method for Obtaining Generating Function for Central Coefficients of Triangles</a>, arXiv preprint arXiv:1206.0877 [math.CO], 2012, and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Kruchinin/kruchinin5.html">J. Int. Seq. 15 (2012) #12.9.3</a>
%H A001003 V. Kurauskas, <a href="https://arxiv.org/abs/1504.08107">On graphs containing few disjoint excluded minors. Asymptotic number and structure of graphs containing few disjoint minors K_4</a>, arXiv preprint arXiv:1504.08107 [math.CO], 2015. See Section 8.1.
%H A001003 J. S. Lew, <a href="/A001003/a001003_4.pdf">Letter to N. J. A. Sloane, Sep 05 1978</a>
%H A001003 Huyile Liang, Jeffrey Remmel and Sainan Zheng, <a href="https://arxiv.org/abs/1710.05795">Stieltjes moment sequences of polynomials</a>, arXiv:1710.05795 [math.CO], 2017, see page 11.
%H A001003 Peter Luschny, <a href="https://oeis.org/wiki/User:Peter_Luschny/TheLostCatalanNumbers">The Lost Catalan Numbers And The Schröder Tableaux</a>.
%H A001003 A. Marco and J.-J. Martinez, <a href="https://journals.uwyo.edu/index.php/ela/article/view/1513">A total positivity property of the Marchenko-Pastur Law</a>, Electronic Journal of Linear Algebra, Volume 30 (2015), pp. 106-117.
%H A001003 Peter McCalla and Asamoah Nkwanta, <a href="https://arxiv.org/abs/1901.07092">Catalan and Motzkin Integral Representations</a>, arXiv:1901.07092 [math.NT], 2019.
%H A001003 D. Merlini, R. Sprugnoli and M. C. Verri, <a href="https://doi.org/10.1016/j.dam.2003.11.012">Waiting patterns for a printer</a>, Discrete Applied Mathematics, Volume 144, Issue 3, 2004, pp. 359-373, ISSN 0166-218X.
%H A001003 W. Mlotkowski and K. A. Penson, <a href="https://arxiv.org/abs/1304.6544">The probability measure corresponding to 2-plane trees</a>, ArXiv preprint arXiv:1304.6544 [math.PR], 2013.
%H A001003 T. Motzkin, <a href="https://dx.doi.org/10.1090/S0002-9904-1945-08486-9">The hypersurface cross ratio</a>, Bull. Amer. Math. Soc., 51 (1945), 976-984.
%H A001003 T. S. Motzkin, <a href="https://dx.doi.org/10.1090/S0002-9904-1948-09002-4">Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products</a>, Bull. Amer. Math. Soc., 54 (1948), 352-360.
%H A001003 Hanna Mularczyk, <a href="https://arxiv.org/abs/1908.04025">Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations</a>, arXiv:1908.04025 [math.CO], 2019.
%H A001003 G. Muntingh, <a href="https://arxiv.org/abs/1204.2709">Implicit Divided Differences, Little Schröder Numbers, and Catalan Numbers</a>, arXiv preprint arXiv:1204.2709 [math.CO], 2012, and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Muntingh/muntingh2.html">J. Int. Seq. 15 (2012) #12.6.5</a>.
%H A001003 Jean-Christophe Novelli and Jean-Yves Thibon, <a href="https://arxiv.org/abs/1209.5959">Duplicial algebras and Lagrange inversion</a>, arXiv preprint arXiv:1209.5959 [math.CO], 2012.
%H A001003 J.-C. Novelli and J.-Y. Thibon, <a href="https://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
%H A001003 P. Peart and W.-J. Woan, <a href="https://www.cs.uwaterloo.ca/journals/JIS/VOL3/PEART/peart1.html">Generating Functions via Hankel and Stieltjes Matrices</a>, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
%H A001003 O. Pechenik, <a href="https://arxiv.org/abs/1209.1355">Cyclic sieving of increasing tableaux and small Schröder paths</a>, arXiv:1209.1355 [math.CO], 2012-2014.
%H A001003 O. Pechenik, <a href="https://dx.doi.org/10.1016/j.jcta.2014.04.002">Cyclic sieving of increasing tableaux and small Schröder paths</a>, J. Combin. Theory A, 125 (2014), 357-378.
%H A001003 R. A. Perez, <a href="https://www.ams.org/notices/201104/rtx110400558p.pdf">A brief but historic article of Siegel</a>, Notices AMS, 58 (2011), 558-566.
%H A001003 E. Pergola and R. A. Sulanke, <a href="https://cs.uwaterloo.ca/journals/JIS/PergolaSulanke/">Schroeder Triangles, Paths, and Parallelogram Polyominoes</a>, J. Integer Sequences, 1 (1998), #98.1.7.
%H A001003 Vincent Pilaud, <a href="https://arxiv.org/abs/2205.06686">Pebble trees</a>, arXiv:2205.06686 [math.CO], 2022.
%H A001003 Vincent Pilaud and V. Pons, <a href="https://arxiv.org/abs/1606.09643">Permutrees</a>, arXiv preprint arXiv:1606.09643 [math.CO], 2016.
%H A001003 L. Pudwell, <a href="https://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees (slides from a talk, mentions many sequences)</a>, 2012.
%H A001003 Feng Qi, Xiao-Ting Shi, and Bai-Ni Guo, <a href="https://www.researchgate.net/profile/Feng_Qi/publication/294259300">Integral representations of the large and little Schröder numbers</a>, Preprint, 2016.
%H A001003 Feng Qi and Bai-Ni Guo, <a href="https://doi.org/10.1016/j.ajmsc.2016.06.002">Some explicit and recursive formulas of the large and little Schröder numbers</a>, Arab Journal of Mathematical Sciences, June 2016.
%H A001003 Marko Riedel, <a href="/A001003/a001003_6.pdf">Computation of the asymptotic by elementary means</a>
%H A001003 E. Schröder, <a href="/A000108/a000108_9.pdf">Vier combinatorische Probleme</a>, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]
%H A001003 L. W. Shapiro & N. J. A. Sloane, <a href="/A006318/a006318_1.pdf">Correspondence, 1976</a>
%H A001003 M. Shattuck, <a href="https://ami.uni-eszterhazy.hu/uploads/papers/finalpdf/AMI_42_from93to101.pdf">On the zeros of some polynomials with combinatorial coefficients</a>, Annales Mathematicae et Informaticae, 42 (2013) pp. 93-101.
%H A001003 N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0312448">The On-Line Encyclopedia of Integer Sequences</a>, arXiv:math/0312448 [math.CO], 2003.
%H A001003 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A001003 N. J. A. Sloane, <a href="/A001003/a001003_2.pdf">Illustrations of rooted planar trees with 2, 3, and 4 endpoints, illustrating a(1)=1, a(2)=3, a(4)=11.</a>
%H A001003 L. M. Smiley, <a href="https://arxiv.org/abs/math/9907057">Variants of Schroeder Dissections</a>, arXiv:math/9907057 [math.CO], 1999.
%H A001003 Michael Z. Spivey and Laura L. Steil, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html">The k-Binomial Transforms and the Hankel Transform</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
%H A001003 R. P. Stanley, <a href="https://math.mit.edu/~rstan/papers.html">Hipparchus, Plutarch, Schröder and Hough</a>, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
%H A001003 R. P. Stanley, <a href="https://www.jstor.org/stable/2974582">Hipparchus, Plutarch, Schröder, and Hough</a>, Amer. Math. Monthly, 104, 1997, 344-350.
%H A001003 Y. Sun and Z. Wang, <a href="https://dx.doi.org/10.1007/s00373-010-0950-9">Consecutive pattern avoidances in non-crossing trees</a>, Graph. Combinat. 26 (2010) 815-832
%H A001003 Anthony Van Duzer, <a href="https://arxiv.org/abs/1904.05525">Subtrees of a Given size in Schroeder Trees</a>, arXiv:1904.05525 [math.CO], 2019.
%H A001003 Elena L. Wang and Guoce Xin, <a href="https://arxiv.org/abs/2507.15654">On Ward Numbers and Increasing Schröder Trees</a>, arXiv:2507.15654 [math.CO], 2025. See p. 12.
%H A001003 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Bracketing.html">Bracketing</a>
%H A001003 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SuperCatalanNumber.html">Super Catalan Number</a>
%H A001003 Wen-jin Woan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Woan/woan11.html">A Recursive Relation for Weighted Motzkin Sequences</a> Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6.
%H A001003 Wen-jin Woan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Woan/woan206.html">A Relation Between Restricted and Unrestricted Weighted Motzkin Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.7.
%H A001003 Wikipedia, <a href="https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Hipparchus_number">Schroeder-Hipparchus numbers</a>.
%H A001003 E. X. W. Xia and O. X. M. Yao, <a href="https://doi.org/10.37236/3412">A Criterion for the Log-Convexity of Combinatorial Sequences</a>, The Electronic Journal of Combinatorics, 20 (2013), #P3.
%H A001003 <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%H A001003 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A001003 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.
%F A001003 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
%F A001003 a(n+1) = -a(n) + 2*Sum_{k=1..n} a(k)*a(n+1-k). - _Philippe Deléham_, Jan 27 2004
%F A001003 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
%F A001003 G.f.: (1 + x - sqrt(1 - 6*x + x^2) )/(4*x) = 2/(1 + x + sqrt(1 - 6*x + x^2)).
%F A001003 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
%F A001003 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
%F A001003 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
%F A001003 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
%F A001003 From _Paul Barry_, May 24 2005: (Start)
%F A001003 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].
%F A001003 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].
%F A001003 a(n) = Sum_{k=0..n} (1/(k+1))*C(n, k)*C(n+k, k)*(-1)^(n-k)*2^k [with offset 0].
%F A001003 a(n) = Sum_{k=0..n} A088617(n, k)*(-1)^(n-k)*2^k [with offset 0]. (End)
%F A001003 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
%F A001003 Reversion of (x-2*x^2)/(1-x) is g.f. offset 1.
%F A001003 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.]
%F A001003 a(n) = Sum_{k=0..n} A088617(n, k)*2^k*(-1)^(n-k). - _Philippe Deléham_, Jan 21 2004
%F A001003 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
%F A001003 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.)
%F A001003 From _Wolfdieter Lang_, Sep 12 2005: (Start)
%F A001003 a(n) = (1/n)*Sum_{k=1..n} binomial(n, k)*binomial(n+k, k-1).
%F A001003 a(n) = hypergeom([1-n, n+2], [2], -1), n>=1. (End)
%F A001003 a(n) = hypergeom([1-n, -n], [2], 2) for n>=0. - _Peter Luschny_, Sep 22 2014
%F A001003 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
%F A001003 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
%F A001003 Starting (1, 3, 11, 45, ...), = row sums of triangle A126216 = A001263 * [1, 2, 4, 8, 16, ...]. - _Gary W. Adamson_, Nov 30 2007
%F A001003 From _Paul Barry_, May 15 2009: (Start)
%F A001003 G.f.: 1/(1+x-2x/(1+x-2x/(1+x-2x/(1+x-2x/(1-.... (continued fraction).
%F A001003 G.f.: 1/(1-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction).
%F A001003 G.f.: 1/(1-x-2x^2/(1-3x-2x^2/(1-3x-2x^2/(1-... (continued fraction). (End)
%F A001003 G.f.: 1 / (1 - x / (1 - 2*x / (1 - x / (1 - 2*x / ... )))). - _Michael Somos_, May 19 2013
%F A001003 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]
%F A001003 From _Gary W. Adamson_, Jul 08 2011: (Start)
%F A001003 a(n) = upper left term in M^n, where M is the production matrix:
%F A001003 1, 1, 0, 0, 0, 0, ...
%F A001003 2, 2, 2, 0, 0, 0, ...
%F A001003 1, 1, 1, 1, 0, 0, ...
%F A001003 2, 2, 2, 2, 2, 0, ...
%F A001003 1, 1, 1, 1, 1, 1, ...
%F A001003 ... (End)
%F A001003 From _Gary W. Adamson_, Aug 23 2011: (Start)
%F A001003 a(n) is the sum of top row terms of Q^(n-1), where Q is the infinite square production matrix:
%F A001003 1, 2, 0, 0, 0, ...
%F A001003 1, 1, 2, 0, 0, ...
%F A001003 1, 1, 1, 2, 0, ...
%F A001003 1, 1, 1, 1, 2, ...
%F A001003 ... (End)
%F A001003 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
%F A001003 A006318(n) = 2*a(n) if n>0. - _Michael Somos_, Mar 31 2007
%F A001003 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
%F A001003 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
%F A001003 a(n) = A144944(n,n) = A186826(n,0). - _Reinhard Zumkeller_, May 11 2013
%F A001003 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
%F A001003 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
%F A001003 G.f.: 1 + x/G(x) with G(x) = 1 - 3*x - 2*x^2/G(x) (continued fraction). - _Nikolaos Pantelidis_, Dec 17 2022
%e A001003 G.f. = 1 + x + 3*x^2 + 11*x^3 + 45*x^4 + 197*x^5 + 903*x^6 + 4279*x^7 + ...
%e A001003 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.
%e A001003 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.
%e A001003 a(4) = 45 since the top row of Q^3 = (11, 14, 12, 8, 0, 0, 0, ...); (11 + 14 + 12 + 8) = 45.
%p A001003 t1 := (1/(4*x))*(1+x-sqrt(1-6*x+x^2)); series(t1,x,40);
%p A001003 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
%p A001003 # Computes n -> [a[0],a[1],..,a[n]]
%p A001003 A001003_list := proc(n) local j,a,w; a := array(0..n); a[0] := 1;
%p A001003 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;
%p A001003 convert(a,list) end: A001003_list(100); # _Peter Luschny_, May 17 2011
%t A001003 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]
%t A001003 (* Second program: *)
%t A001003 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_ *)
%t A001003 a[ n_] := SeriesCoefficient[ (1 + x - Sqrt[1 - 6 x + x^2]) / (4 x), {x, 0, n}]; (* _Michael Somos_, Aug 26 2015 *)
%t A001003 Table[(KroneckerDelta[n] - GegenbauerC[n+1, -1/2, 3])/4, {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 25 2015 *)
%t A001003 a[n_] := -LegendreP[n, -1, 2, 3] I / Sqrt[2]; a[0] = 1;
%t A001003 Table[a[n], {n, 0, 23}] (* _Jean-François Alcover_, Feb 16 2019 *)
%t A001003 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 *)
%t A001003 CoefficientList[InverseSeries[Series[x/(Series[(1 - x)/(1 - 2 x), {x, 0, 24}]), {x, 0, 24}]]/x, x] (* _Mats Granvik_, Jun 30 2025 *)
%o A001003 (PARI) {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 */
%o A001003 (PARI) {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 */
%o A001003 (PARI) {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 */
%o A001003 (PARI) N=30; x='x+O('x^N); Vec( (1+x-(1-6*x+x^2)^(1/2))/(4*x) ) \\ _Hugo Pfoertner_, Nov 19 2018
%o A001003 (Python) # The objective of this implementation is efficiency.
%o A001003 # n -> [a(0), a(1), ..., a(n)]
%o A001003 def A001003_list(n):
%o A001003 a = [0 for i in range(n)]
%o A001003 a[0] = 1
%o A001003 for w in range(1, n):
%o A001003 s = 0
%o A001003 for j in range(1, w):
%o A001003 s += a[j]*a[w-j-1]
%o A001003 a[w] = a[w-1]+2*s
%o A001003 return a
%o A001003 # _Peter Luschny_, May 17 2011
%o A001003 (Python)
%o A001003 from gmpy2 import divexact
%o A001003 A001003 = [1, 1]
%o A001003 for n in range(3,10**3):
%o A001003 A001003.append(divexact(A001003[-1]*(6*n-9)-(n-3)*A001003[-2],n))
%o A001003 # _Chai Wah Wu_, Sep 01 2014
%o A001003 (Sage) # Generalized algorithm of L. Seidel
%o A001003 def A001003_list(n) :
%o A001003 D = [0]*(n+1); D[1] = 1/2
%o A001003 b = True; h = 2; R = [1]
%o A001003 for i in range(2*n-2) :
%o A001003 if b :
%o A001003 for k in range(h,0,-1) : D[k] += D[k-1]
%o A001003 h += 1;
%o A001003 else :
%o A001003 for k in range(1,h, 1) : D[k] += D[k-1]
%o A001003 R.append(D[h-1]);
%o A001003 b = not b
%o A001003 return R
%o A001003 A001003_list(24) # _Peter Luschny_, Jun 02 2012
%o A001003 (Haskell)
%o A001003 a001003 = last . a144944_row -- _Reinhard Zumkeller_, May 11 2013
%o A001003 (Magma)
%o A001003 R<x>:=PowerSeriesRing(Rationals(), 50);
%o A001003 Coefficients(R!( (1+x -Sqrt(1-6*x+x^2) )/(4*x) )); // _G. C. Greubel_, Oct 27 2024
%Y A001003 See A000081, A000108, A001190, A001699, for other ways to count parentheses.
%Y A001003 Row sums of A033282, A033877, A086810, A126216.
%Y A001003 Right-hand column 1 of convolution triangle A011117.
%Y A001003 Column 1 of A336573. Column 0 of A104219.
%Y A001003 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
%Y A001003 Cf. A000041, A000311, A001263, A003480, A006125, A010683, A025240, A035011.
%Y A001003 Cf. A048996, A054726, A059435, A065096, A080243, A085403, A086456, A086616.
%Y A001003 Cf. A086810, A088617, A104858, A110440, A111785, A114710, A118376, A126216.
%Y A001003 Cf. A139685, A144156, A144944, A153881, A186826.
%Y A001003 Cf. A006318 (Schroeder numbers).
%K A001003 nonn,easy,nice,core,changed
%O A001003 0,3
%A A001003 _N. J. A. Sloane_