A088617 -id:A088617 - cp's OEIS frontend

A006318 Large Schröder numbers (or large Schroeder numbers, or big Schroeder numbers).

1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738, 142078746, 745387038, 3937603038, 20927156706, 111818026018, 600318853926, 3236724317174, 17518619320890, 95149655201962, 518431875418926, 2832923350929742, 15521467648875090

Offset: 0

N. J. A. Sloane

For the little Schröder numbers (or little Schroeder numbers, or small Schroeder numbers) see A001003.
The number of perfect matchings in a triangular grid of n squares (n = 1, 4, 9, 16, 25, ...). - Roberto E. Martinez II, Nov 05 2001
a(n) is the number of subdiagonal paths from (0, 0) to (n, n) consisting of steps East (1, 0), North (0, 1) and Northeast (1, 1) (sometimes called royal paths). - David Callan, Mar 14 2004
Twice A001003 (except for the first term).
a(n) is the number of dissections of a regular (n+4)-gon by diagonals that do not touch the base. (A diagonal is a straight line joining two nonconsecutive vertices and dissection means the diagonals are noncrossing though they may share an endpoint. One side of the (n+4)-gon is designated the base.) Example: a(1)=2 because a pentagon has only 2 such dissections: the empty one and the one with a diagonal parallel to the base. - David Callan, Aug 02 2004
a(n) is the number of separable permutations, i.e., permutations avoiding 2413 and 3142 (see Shapiro and Stephens). - Vincent Vatter, Aug 16 2006
Eric W. Weisstein comments that the Schröder numbers bear the same relationship to the Delannoy numbers (A001850) as the Catalan numbers (A000108) do to the binomial coefficients. - Jonathan Vos Post, Dec 23 2004
a(n) is the number of lattice paths from (0, 0) to (n+1, n+1) consisting of unit steps north N = (0, 1) and variable-length steps east E = (k, 0), with k a positive integer, that stay strictly below the line y = x except at the endpoints. For example, a(2) = 6 counts 111NNN, 21NNN, 3NNN, 12NNN, 11N1NN, 2N1NN (east steps indicated by their length). If the word "strictly" is replaced by "weakly", the counting sequence becomes the little Schröder numbers, A001003 (offset). - David Callan, Jun 07 2006
a(n) is the number of dissections of a regular (n+3)-gon with base AB that do not contain a triangle of the form ABP with BP a diagonal. Example: a(1) = 2 because the square D-C | | A-B has only 2 such dissections: the empty one and the one with the single diagonal AC (although this dissection contains the triangle ABC, BC is not a diagonal). - David Callan, Jul 14 2006
a(n) is the number of (colored) Motzkin n-paths with each upstep and each flatstep at ground level getting one of 2 colors and each flatstep not at ground level getting one of 3 colors. Example: With their colors immediately following upsteps/flatsteps, a(2) = 6 counts U1D, U2D, F1F1, F1F2, F2F1, F2F2. - David Callan, Aug 16 2006
The Hankel transform of this sequence is A006125(n+1) = [1, 2, 8, 64, 1024, 32768, ...]; example: Det([1, 2, 6, 22; 2, 6, 22, 90; 6, 22, 90, 394; 22, 90, 394, 1806]) = 64. - Philippe Deléham, Sep 03 2006
Triangle A144156 has row sums equal to A006318 with left border A001003. - Gary W. Adamson, Sep 12 2008
a(n) is also the number of order-preserving and order-decreasing partial transformations (of an n-chain). Equivalently, it is the order of the Schröder monoid, PC sub n. - Abdullahi Umar, Oct 02 2008
Sum_{n >= 0} a(n)/10^n - 1 = (9 - sqrt(41))/2. - Mark Dols, Jun 22 2010
1/sqrt(41) = Sum_{n >= 0} Delannoy number(n)/10^n. - Mark Dols, Jun 22 2010
a(n) is also the dimension of the space Hoch(n) related to Hochschild two-cocycles. - Ph. Leroux (ph_ler_math(AT)yahoo.com), Aug 24 2010
Let W = (w(n, k)) denote the augmentation triangle (as at A193091) of A154325; then w(n, n) = A006318(n). - Clark Kimberling, Jul 30 2011
Conjecture: For each n > 2, the polynomial sum_{k = 0}^n a(k)*x^{n-k} is irreducible modulo some prime p < n*(n+1). - Zhi-Wei Sun, Apr 07 2013
From Jon Perry, May 24 2013: (Start)
Consider a Pascal triangle variant where T(n, k) = T(n, k-1) + T(n-1, k-1) + T(n-1, k), i.e., the order of performing the calculation must go from left to right (A033877). This sequence is the rightmost diagonal.
Triangle begins:
  1;
  1,  2;
  1,  4,  6;
  1,  6, 16, 22;
  1,  8, 30, 68, 90;
  ... (End)
a(n) is the number of permutations avoiding 2143, 3142 and one of the patterns among 246135, 254613, 263514, 524361, 546132. - Alexander Burstein, Oct 05 2014
a(n) is the number of semi-standard Young tableaux of shape n x 2 with consecutive entries.  That is, j in P and 1 <= i<= j imply i in P. - Graham H. Hawkes, Feb 15 2015
a(n) is the number of unary-rooted size n unary-binary trees (each node has either 1 or 2 degree out). - John Bodeen, May 29 2017
Conjecturally, a(n) is the number of permutations pi of length n such that s(pi) avoids the patterns 231 and 321, where s denotes West's stack-sorting map. - Colin Defant, Sep 17 2018
a(n) is the number of n X n permutation matrices which percolate under the 2-neighbor bootstrap percolation rule (see Shapiro and Stephens). The number of general n X n matrices of weight n which percolate is given in A146971. - Jonathan Noel, Oct 05 2018
a(n) is the number of permutations of length n+1 which avoid 3142 and 3241. The permutations are precisely the permutations that are sortable by a decreasing stack followed by an increasing stack in series. - Rebecca Smith, Jun 06 2019
a(n) is the number of permutations of length n+1 avoiding the partially ordered pattern (POP) {3>1, 4>1, 1>2} of length 4. That is, the number of length n+1 permutations having no subsequences of length 4 in which the second element is the smallest, and the first element is smaller than the third and fourth elements. - Sergey Kitaev, Dec 10 2020
Named after the German mathematician Ernst Schröder (1841-1902). - Amiram Eldar, Apr 15 2021
a(n) is the number of sequences of nonnegative integers (u_1, u_2, ..., u_n) such that (i) u_i <= i for all i, and (ii) the nonzero u_i are weakly increasing. For example, a(2) = 6 counts 00, 01, 02, 10, 11, 12. See link "Some bijections for lattice paths" at A001003. - David Callan, Dec 18 2021
a(n) is the number of separable elements of the Weyl group of type B_n/C_n (see Gaetz and Gao). - Fern Gossow, Jul 31 2023
The number of domino tilings of an Aztec triangle of order n. Dually, the number perfect matchings of the edges in the cellular graph formed by a triangular grid of n squares (n = 1, 4, 9, 16, 25, ...) as in Ciucu (1996). - Michael Somos, Sep 16 2024
a(n) is the number of dissections of a convex (n+3)-sided polygon by non-intersecting diagonals such that none of the dividing diagonals passes through a chosen vertex. - Muhammed Sefa Saydam, Mar 01 2025
a(n) is the number of dissections of a convex (n+m+1)-sided polygon by non-intersecting diagonals such that the selected m consecutive sides of the polygon will be in the same subpolygon. - Muhammed Sefa Saydam, Jul 02 2025

			a(3) = 22 since the top row of Q^n = (6, 6, 6, 4, 0, 0, 0, ...); where 22 = (6 + 6 + 6 + 4).
G.f. = 1 + 2*x + 6*x^2 + 22*x^3 + 90*x^4 + 394*x^5 + 1806*x^6 + 8858*x^7 + 41586*x^8 + ...

D. Andrica and E. J. Ionascu, On the number of polynomials with coefficients in [n], An. St. Univ. Ovidius Constanta, 2013, to appear.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
O. Bodini, A. Genitrini, F. Peschanski, and N.Rolin, Associativity for binary parallel processes, CALDAM 2015.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 24, 618.
S. Brlek, E. Duchi, E. Pergola, and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.
Xiang-Ke Chang, XB Hu, H Lei, and YN Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
William Y. C. Chen and Carol J. Wang, Noncrossing Linked Partitions and Large (3, 2)-Motzkin Paths, Discrete Math., 312 (2012), 1918-1922.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 81, #21, (4), q_n.
D. E. Davenport, L. W. Shapiro, and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33.
Deng, Eva Y. P.; Dukes, Mark; Mansour, Toufik; and Wu, Susan Y. J.; Symmetric Schröder paths and restricted involutions. Discrete Math. 309 (2009), no. 12, 4108-4115. See p. 4109.
E. Deutsch, A bijective proof of an equation linking the Schroeder numbers, large and small, Discrete Math., 241 (2001), 235-240.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358.
Doslic, Tomislav and Veljan, Darko. 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
M. Dziemianczuk, Generalizing Delannoy numbers via counting weighted lattice paths, INTEGERS, 13 (2013), #A54.
Egge, Eric S., Restricted signed permutations counted by the Schröder numbers. Discrete Math. 306 (2006), 552-563. [Many applications of these numbers.]
S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497-499.
S. Gire, Arbres, permutations a motifs exclus et cartes planaire: quelques problemes algorithmiques et combinatoires, Ph.D. Thesis, Universite Bordeaux I, 1993.
N. S. S. Gu, N. Y. Li, and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Guruswami, Venkatesan, Enumerative aspects of certain subclasses of perfect graphs. Discrete Math. 205 (1999), 97-117.
Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
D. E. Knuth, The Art of Computer Programming, Vol. 1, Section 2.2.1, Problem 11.
D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discrete Math. 218 (2000) 121-130.
Kremer, Darla and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
Laradji, A. and Umar, A. Asymptotic results for semigroups of order-preserving partial transformations. Comm. Algebra 34 (2006), 1071-1075. - Abdullahi Umar, Oct 11 2008
L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math., 26 (1961), 223-229.
L. Shapiro and A. B. Stephens, Bootstrap percolation, the Schröder numbers and the N-kings problem, SIAM J. Discrete Math., Vol. 4 (1991), pp. 275-280.
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 and also Problems 6.39 and 6.40.
Lin Yang and S.-L. Yang, The parametric Pascal rhombus. Fib. Q., 57:4 (2019), 337-346.
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.

Fung Lam, Table of n, a(n) for n = 0..2000 (terms 0..100 by T. D. Noe)
J. Abate and W. Whitt, Integer Sequences from Queueing Theory, J. Int. Seq. 13 (2010), 10.5.5, Corollary 8.
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Andrei Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, and R. Pinter, Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations, arXiv:1011.1889 [math.CO], 2010-2012.
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Preprint, 2002.
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.
Yu Hin Au, Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers, arXiv:1912.00555 [math.CO], 2019.
Jean-Christophe Aval and F. Bergeron, Rectangular Schroder Parking Functions Combinatorics, arXiv:1603.09487 [math.CO], 2016.
Axel Bacher, Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths, arXiv:1802.06030 [cs.DS], 2018.
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
Kayleigh Bangs, Skye Binegar, Young Kim, Kyle Ormsby, Angélica M. Osorno, David Tamas-Parris, and Livia Xu, Biased permutative equivariant categories, arXiv:1907.00933 [math.AT], 2019.
E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences, Discrete Mathematics and Theoretical Computer Science, 4 (2000), 31-44.
E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, Some permutations with forbidden subsequences and their inversion number, Discrete Math. 234(1-3) (2001), 1-15.
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.
J.-L. Baril, C. Khalil, and V. Vajnovszki, Catalan and Schröder permutations sortable by two restricted stacks, arXiv:2004.01812 [cs.DM], 2020.
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6
Paul Barry, Generalized Catalan Numbers, Hankel Transforms and Somos-4 Sequences , J. Int. Seq. 13 (2010) #10.7.2.
Paul Barry, On a Generalization of the Narayana Triangle, J. Int. Seq. 14 (2011), Article 11.4.5.
Paul Barry, Laurent Biorthogonal Polynomials and Riordan Arrays, arXiv preprint arXiv:1311.2292 [math.CA], 2013.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., 22 (2019), Article 19.5.8.
Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
Paul Barry, Riordan arrays, the A-matrix, and Somos 4 sequences, arXiv:1912.01126 [math.CO], 2019.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 25, 29.
Paul Barry and Aoife Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
Paul Barry and Nikolaos Pantelidis,On pseudo-involutions, involutions and quasi-involutions in the group of almost Riordan arrays, J Algebr Comb 54, 399-423 (2021). (appeared in its aerated form,i.e. 1,0,2,0,6,0,...)
Christian Bean, Émile Nadeau, and Henning Ulfarsson, Enumeration of Permutation Classes and Weighted Labelled Independent Sets, arXiv:1912.07503 [math.CO], 2019.
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. - From _N. J. A. Sloane_, Nov 28 2012
F. R. Bernhart and N. J. A. Sloane, Emails, April-May 1994.
J. Bloom and A. Burstein, Egge triples and unbalanced Wilf-equivalence, arXiv:1410.0230 [math.CO], 2014.
O. Bodini, A. Genitrini, and F. Peschanski, The Combinatorics of Non-determinism, In proc. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'13), Leibniz International Proceedings in Informatics, pp 425-436, 2013.
Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003 [math.CO], 2013-2014.
M. Bremner and S. Madariaga, Lie and Jordan products in interchange algebras, arXiv:1408.3069 [math.RA], 2014-2015.
M. Bremner and S. Madariaga, Permutation of elements in double semigroups, arXiv:1405.2889 [math.RA], 2014-2015.
R. Brignall, S. Huczynska, and V. Vatter, Simple permutations and algebraic generating functions, arXiv:math/0608391 [math.CO], 2006.
Marie-Louise Bruner and Martin Lackner, On the Likelihood of Single-Peaked Preferences, arXiv:1505.05852 [cs.GT], 2015.
Alexander Burstein, Sergi Elizalde, and Toufik Mansour, Restricted Dumont permutations, Dyck paths and noncrossing partitions, arXiv:math/0610234 [math.CO], 2006. See Theorem 3.5.
Alexander Burstein and J. Pantone, Two examples of unbalanced Wilf-equivalence, arXiv:1402.3842 [math.CO], 2014.
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
David Callan, An application of a bijection of Mansour, Deng, and Du, arXiv:1210.6455 [math.CO], 2012.
David Callan, A note on a bijection for Schröder permutations, arXiv:1602.05571 [math.CO], 2016.
David Callan and Toufik Mansour, Five subsets of permutations enumerated as weak sorting permutations, arXiv:1602.05182 [math.CO], 2016.
Hui-Qin Cao and Hao Pan, A Stern-type congruence for the Schröder numbers, arXiv:1512.06310 [math.NT], 2015.
Jean Cardinal, Vera Sacristán, and Rodrigo I. Silveira, A Note on Flips in Diagonal Rectangulations, arXiv:1712.07919 [math.CO], 2017.
F. Chapoton, F. Hivert, and J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv:1307.0092 [math.CO], 2013.
F. Chapoton and S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv:1310.4521 [math.CO], 2013.
W. Y. C. Chen, L. H. Liu, and C. J. Wang, Linked Partitions and Permutation Tableaux, arXiv:1305.5357 [math.CO], 2013.
Z. Chen and H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 (2016), eq. (1.13), a=2, b=1.
Shane Chern, On 0012-avoiding inversion sequences and a Conjecture of Lin and Ma, arXiv:2006.04318 [math.CO], 2020.
J. Cigler, Hankel determinants of some polynomial sequences, 2012.
Johann Cigler, Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, arXiv:2003.01676 [math.CO], 2020.
M. Ciucu, Perfect matchings of cellular graphs, J. Algebraic Combin., 5 (1996) 87-103.
CombOS - Combinatorial Object Server, Generate slicing floorplans
Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, Patterns in Inversion Sequences I, arXiv:1510.05434 [math.CO], 2015
S. Crowley, Mellin and Laplace Integral Transforms Related to the Harmonic Sawtooth Map and a Diversion Into The Theory Of Fractal Strings, Number Theory, viXra:1202.0079, 2012.
R. De Castro, A. L. Ramírez, and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv:1310.2449 [math.PR], 2013.
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, Exhaustive generation for permutations avoiding a (colored) regular sets of patterns, arXiv:1809.00742 [cs.DM], 2018.
B. Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.6.7), A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths, J. Int. Seq. 13 (2010), #10.9.2.
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.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
James East and Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018.
Ömer Eğecioğlu, Collier Gaiser, and Mei Yin, Enumerating pattern-avoiding permutations by leading terms, arXiv:2309.15964 [math.CO], 2023.
S.-P. Eu and T.-S. Fu, A simple proof of the Aztec diamond problem, arXiv:math/0412041 [math.CO], 2004.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012 and J. Int. Seq. 17 (2014), #14.1.5
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see p. 474.
Shishuo Fu, Z. Lin, and J. Zeng, Two new unimodal descent polynomials, arXiv:1507.05184 [math.CO], 2015-2019.
Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
Christian Gaetz and Yibo Gao, Separable elements in Weyl groups, arXiv:1905.09331 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Olivier Gérard, Illustration of initial terms
Étienne Ghys, Quand beaucoup de courbes se rencontrent — Images des Mathématiques, CNRS, 2009.
Étienne Ghys, Intersecting curves, Amer. Math. Monthly, 120 (2013), 232-242.
Étienne Ghys, A Singular Mathematical Promenade, arXiv:1612.06373, 2016.
Samuele Giraudo, Operads from posets and Koszul duality, arXiv:1504.04529 [math.CO], 2015.
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.
D. Gouyou-Beauchamps and B. Vauquelin, Deux propriétés combinatoires des nombres de Schröder, Theor. Inform. Appl., 22 (1988), 361-388.
Taras Goy and Mark Shattuck, Determinant identities for the Catalan, Motzkin and Schröder numbers, The Art of Discrete and Applied Mathematics, Vol. 7 (2024), #P1.09.
Li Guo and Jun Pei, Averaging algebras, Schröder numbers and rooted trees, arXiv:1401.7386 [math.RA], 2014.
Nils Haug, T. Prellberg, and G. Siudem, Scaling in area-weighted generalized Motzkin paths, arXiv:1605.09643 [cond-mat.stat-mech], 2016.
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, 1410.2657 [math.CO], 2014.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 159.
S. Kamioka, Laurent biorthogonal polynomials, q-Narayana polynomials and domino tilings of the Aztec diamonds, arXiv:1309.0268 [math.CO], 2013.
Sergey Kitaev and Jeffrey Remmel, Simple marked mesh patterns, arXiv:1201.1323 [math.CO], 2012.
S. Kitaev and J. Remmel, Quadrant Marked Mesh Patterns, J. Int. Seq. 15 (2012), #12.4.7
Laszlo Kozma and T. Saranurak, Binary search trees and rectangulations, arXiv:1603.08151 [cs.DS], 2016.
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, Aires des chemins surdiagonaux et application à un problème économique, Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche 24 (1976): 1-8. [Annotated scanned copy]
Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, 8 (2005), Article 05.5.5.
Guillaume Lample and François Charton, Deep Learning for Symbolic Mathematics, arXiv:1912.01412 [cs.SC], 2019.
A. Laradji and A. Umar Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra, 278, (2004), 342-359.
A. Laradji and A. Umar, Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq. 7 (2004), #04.3.8.
Tamás Lengyel, On some p-adic properties and supercongruences of Delannoy and Schröder Numbers, Integers (2021) Vol. 21, #A86.
Philippe Leroux, Hochschild two-cocycles and the good triple (As,Hoch,Mag infinity), arXiv:0806.4093 [math.RA], 2008.
Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 5.
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see pp. 18-19.
Peter Luschny, The Lost Catalan Numbers And The Schröder Tableaux.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016 [Section 2.24].
Peter McCalla and Asamoah Nkwanta, Catalan and Motzkin Integral Representations, arXiv:1901.07092 [math.NT], 2019.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
J.-C. Novelli and J.-Y. Thibon, Hopf algebras and dendriform structures arising from parking functions, Fundamenta Mathematicae 193 (2007), no. 3, 189-241 (arXiv:math/0511200 [math.CO]).
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
Jun Pei and Li Guo, Averaging algebras, Schröder numbers, rooted trees and operads, Journal of Algebraic Combinatorics, 42(1) (2015), 73-109; arXiv:1401.7386 [math.RA], 2014.
E. Pergola and R. A. Sulanke, Schröder Triangles, Paths and Parallelogram Polyominoes, J. Integer Sequences, 1 (1998), #98.1.7.
Feng Qi and B.-N. Guo, Some explicit and recursive formulas of the large and little Schröder numbers, Arab Journal of Mathematical Sciences, June 2016.
Feng Qi, Xiao-ting Shi, and Bai-Ni Guo, Integral representations of the large and little Schroder numbers, preprint, 2016.
Markus Saers, Dekai Wu, and Chris Quirk, On the Expressivity of Linear Transductions, The 13th Machine Translation Summit.
Seunghyun Seo, The Catalan Threshold Arrangement, Journal of Integer Sequences, 20 (2017), #17.1.1.
L. W. Shapiro and N. J. A. Sloane, Correspondence, 1976.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers [Corrected annotated scanned copy]
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.
R. A. Sulanke, Moments, Narayana numbers and the cut and paste for lattice paths.
R. A. Sulanke, Bijective recurrences concerning Schröder paths, Electron. J. Combin. 5 (1998), Research Paper 47, 11 pp.
Hua Sun and Yi Wang, A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers, J. Int. Seq. 17 (2014), #14.5.2
Zhi-Wei Sun, On Delannoy numbers and Schröder numbers, Journal of Number Theory, 131(12), (2011), 2387-2397; doi:10.1016/j.jnt.2011.06.005; arXiv 1009.2486 [math.NT].
Zhi-Wei Sun, Conjectures involving combinatorial sequences, arXiv:1208.2683 [math.CO], 2012. - _N. J. A. Sloane_, Dec 25 2012
Z.-W. Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in Shangri-La (eds., S. Kanemitsu, H.-Z. Li and J.-Y. Liu), Proc. the 6th China-Japan Sem. Number Theory (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258. - _N. J. A. Sloane_, Dec 28 2012
Paul Tarau, On Type-directed Generation of Lambda Terms, preprint, 2015.
Paul Tarau, On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization, 2015.
Paul Tarau, A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations, arXiv:1507.06944 [cs.LO], 2015.
Paul Tarau, A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms, arXiv preprint arXiv:1608.03912 [cs.PL], 2016.
V. K. Varma and H. Monien, Renormalization of two-body interactions due to higher-body interactions of lattice bosons, arXiv:1211.5664 [cond-mat.quant-gas], 2012. - _N. J. A. Sloane_, Jan 03 2013
Vincent Vatter, Permutation classes, arXiv:1409.5159 [math.CO], 2014.
Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv:1303.5595 [math.CO], 2013.
M. S. Waterman, Home Page (contains copies of his papers)
Eric Weisstein's World of Mathematics, Schröder Number.
J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995), 247-262.
J. Winter, M. M. Bonsangue, and J. J. M. M. Rutten, Context-free coalgebras, 2013.
Wikipedia, Schröder number
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
S.-n. Zheng and S.-l. Yang, On the-Shifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics 2014, Article ID 848374.
Index entries for "core" sequences

Apart from leading term, twice A001003 (the small Schroeder numbers). Cf. A025240.
Sequences A085403, A086456, A103137, A112478 are essentially the same sequence.
Main diagonal of A033877.
Cf. A002003, A004148, A088617, A060693, A144156.
Row sums of A104219. Bisections give A138462, A138463.
Row sums of A175124.
The sequences listed in Yang-Jiang's Table 1 appear to be A006318, A001003, A027307, A034015, A144097, A243675, A260332, A243676. - N. J. A. Sloane, Mar 28 2021

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

a006318 n = a004148_list !! n
a006318_list = 1 : f [1] where
   f xs = y : f (y : xs) where
     y = head xs + sum (zipWith (*) xs $ reverse xs)
-- Reinhard Zumkeller, Nov 13 2012

Order := 24: solve(series((y-y^2)/(1+y),y)=x,y); # then A(x)=y(x)/x
BB:=(-1-z-sqrt(1-6*z+z^2))/2: BBser:=series(BB, z=0, 24): seq(coeff(BBser, z, n), n=1..23); # Zerinvary Lajos, Apr 10 2007
A006318_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 2*a[w-1]+add(a[j]*a[w-j-1], j=1..w-1) od; convert(a,list)end: A006318_list(22); # Peter Luschny, May 19 2011
A006318 := n-> add(binomial(n+k, n-k) * binomial(2*k, k)/(k+1), k=0..n): seq(A006318(n), n=0..22); # Johannes W. Meijer, Jul 14 2013
seq(simplify(hypergeom([-n,n+1],[2],-1)), n=0..100); # Robert Israel, Mar 23 2015

a[0] = 1; a[n_Integer] := a[n] = a[n - 1] + Sum[a[k]*a[n - 1 - k], {k, 0, n - 1}]; Array[a[#] &, 30]
InverseSeries[Series[(y - y^2)/(1 + y), {y, 0, 24}], x] (* then A(x) = y(x)/x *) (* Len Smiley, Apr 11 2000 *)
CoefficientList[Series[(1 - x - (1 - 6x + x^2)^(1/2))/(2x), {x, 0, 30}], x] (* Harvey P. Dale, May 01 2011 *)
a[ n_] := 2 Hypergeometric2F1[ -n + 1, n + 2, 2, -1]; (* Michael Somos, Apr 03 2013 *)
a[ n_] := With[{m = If[ n < 0, -1 - n, n]}, SeriesCoefficient[(1 - x - Sqrt[ 1 - 6 x + x^2])/(2 x), {x, 0, m}]]; (* Michael Somos, Jun 10 2015 *)
Table[-(GegenbauerC[n+1, -1/2, 3] + KroneckerDelta[n])/2, {n, 0, 30}] (* Vladimir Reshetnikov, Nov 12 2016 *)
CoefficientList[Nest[1+x(#+#^2)&, 1+O[x], 20], x] (* Oliver Seipel, Dec 21 2024 *)

{a(n) = if( n<0, n = -1-n); polcoeff( (1 - x - sqrt( 1 - 6*x + x^2 + x^2 * O(x^n))) / 2, n+1)}; /* Michael Somos, Apr 03 2013 */

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

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

# Generalized algorithm of L. Seidel
def A006318_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = True; h = 1; R = []
    for i in range(2*n) :
        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
A006318_list(23) # Peter Luschny, Jun 02 2012

G.f.: (1 - x - (1 - 6*x + x^2)^(1/2))/(2*x).
a(n) = 2*hypergeom([-n+1, n+2], [2], -1). - Vladeta Jovovic, Apr 24 2003
For n > 0, a(n) = (1/n)*Sum_{k = 0..n} 2^k*C(n, k)*C(n, k-1). - Benoit Cloitre, May 10 2003
The g.f. satisfies (1 - x)*A(x) - x*A(x)^2 = 1. - Ralf Stephan, Jun 30 2003
For the asymptotic behavior, see A001003 (remembering that A006318 = 2*A001003). - N. J. A. Sloane, Apr 10 2011
From Philippe Deléham, Nov 28 2003: (Start)
Row sums of A088617 and A060693.
a(n) = Sum_{k = 0..n} C(n+k, n)*C(n, k)/(k+1). (End)
With offset 1: a(1) = 1, a(n) = a(n-1) + Sum_{i = 1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004
a(n) = Sum_{k = 0..n} A000108(k)*binomial(n+k, n-k). - Benoit Cloitre, May 09 2004
a(n) = Sum_{k = 0..n} A011117(n, k). - Philippe Deléham, Jul 10 2004
a(n) = (CentralDelannoy(n+1) - 3 * CentralDelannoy(n))/(2*n) = (-CentralDelannoy(n+1) + 6 * CentralDelannoy(n) - CentralDelannoy(n-1))/2 for n >= 1, where CentralDelannoy is A001850. - David Callan, Aug 16 2006
From Abdullahi Umar, Oct 11 2008: (Start)
A123164(n+1) - A123164(n) = (2*n+1)*a(n) (n >= 0).
  and 2*A123164(n) = (n+1)*a(n) - (n-1)*a(n-1) (n > 0). (End)
Define the general Delannoy numbers d(i, j) as in A001850. Then a(k) = d(2*k, k) - d(2*k, k-1) and a(0) = 1, Sum_{j=0..n} ((-1)^j * (d(n, j) + d(n-1, j-1)) * a(n-j)) = 0. - Peter E John, Oct 19 2006
Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example, Phi([1]) is the Catalan numbers A000108. The present sequence is (essentially) Phi([2]). - Gary W. Adamson, Oct 27 2008
G.f.: 1/(1-2x/(1-x/(1-2x/(1-x/(1-2x/(1-x/(1-2x/(1-x/(1-2x/(1-x.... (continued fraction). - Paul Barry, Dec 08 2008
G.f.: 1/(1 - x - x/(1 - x - x/(1 - x - x/(1 - x - x/(1 - x - x/(1 - ... (continued fraction). - Paul Barry, Jan 29 2009
a(n) ~ ((3 + 2*sqrt(2))^n)/(n*sqrt(2*Pi*n)*sqrt(3*sqrt(2) - 4))*(1-(9*sqrt(2) + 24)/(32*n) + ...). - G. Nemes (nemesgery(AT)gmail.com), Jan 25 2009
Logarithmic derivative yields A002003. - Paul D. Hanna, Oct 25 2010
a(n) = the upper left term in M^(n+1), M = the production matrix:
  1, 1, 0, 0, 0, 0, ...
  1, 1, 1, 0, 0, 0, ...
  2, 2, 1, 1, 0, 0, ...
  4, 4, 2, 1, 1, 0, ...
  8, 8, 8, 2, 1, 1, ...
  ... - Gary W. Adamson, Jul 08 2011
a(n) is the sum of top row terms in Q^n, Q = an infinite square production matrix as follows:
  1, 1, 0, 0, 0, 0, ...
  1, 1, 2, 0, 0, 0, ...
  1, 1, 1, 2, 0, 0, ...
  1, 1, 1, 1, 2, 0, ...
  1, 1, 1, 1, 1, 2, ...
  ... - Gary W. Adamson, Aug 23 2011
From Tom Copeland, Sep 21 2011: (Start)
With F(x) = (1 - 3*x - sqrt(1 - 6*x + x^2))/(2*x) an o.g.f. (nulling the n = 0 term) for A006318, G(x) = x/(2 + 3*x + x^2) is the compositional inverse.
Consequently, with H(x) = 1/ (dG(x)/dx) = (2 + 3*x + x^2)^2 / (2 - x^2),
  a(n) = (1/n!)*[(H(x)*d/dx)^n] x evaluated at x = 0, i.e.,
  F(x) = exp[x*H(u)*d/du] u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)). (End)
a(n-1) = number of ordered complete binary trees with n leaves having k internal vertices colored black, the remaining n - 1 - k internal vertices colored white, and such that each vertex and its rightmost child have different colors ([Drake, Example 1.6.7]). For a refinement of this sequence see A175124. - Peter Bala, Sep 29 2011
D-finite with recurrence: (n-2)*a(n-2) - 3*(2*n-1)*a(n-1) + (n+1)*a(n) = 0. - Vaclav Kotesovec, Oct 05 2012
G.f.: A(x) = (1 - x - sqrt(1 - 6*x + x^2))/(2*x) = (1 - G(0))/x; G(k) = 1 + x - 2*x/G(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Jan 04 2012
G.f.: A(x) = (1 - x - sqrt(1 - 6*x + x^2))/(2*x) = (G(0) - 1)/x; G(k) = 1 - x/(1 - 2/G(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Jan 04 2012
a(n+1) = a(n) + Sum_{k=0..n} a(k)*(n-k). - Reinhard Zumkeller, Nov 13 2012
G.f.: 1/Q(0) 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(-1-n) = a(n). - Michael Somos, Apr 03 2013
G.f.: 1/x - 1 - U(0)/x, where U(k) = 1 - x - x/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013
G.f.: (2 - 2*x - G(0))/(4*x), where G(k) = 1 + 1/( 1 - x*(6 - x)*(2*k - 1)/(x*(6 - x)*(2*k - 1) + 2*(k + 1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013
a(n) = 1/(n + 1) * (Sum_{j=0..n} C(n+j, j)*C(n+j+1, j+1)*(Sum_{k=0..n-j} (-1)^k*C(n+j+k, k))). - Graham H. Hawkes, Feb 15 2015
a(n) = hypergeom([-n, n+1], [2], -1). - Peter Luschny, Mar 23 2015
a(n) = sqrt(2) * LegendreP(n, -1, 3) where LegendreP is the associated Legendre function of the first kind (in Maple's notation). - Robert Israel, Mar 23 2015
G.f. A(x) satisfies: A(x) = Sum_{j>=0} x^j * Sum_{k=0..j} binomial(j,k)*A(x)^k. - Ilya Gutkovskiy, Apr 11 2019
From Peter Bala, May 13 2024: (Start)
a(n) = 2 * Sum_{k = 0..floor(n/2)} binomial(n, 2*k)*binomial(2*n-2*k, n)/(n-2*k+1) for n >= 1.
a(n) = Integral_{x = 0..1} Legendre_P(n, 2*x+1) dx. (End)
G.f. A(x) = 1/(1 - x) * c(x/(1-x)^2), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, Aug 29 2024

Edited by Charles R Greathouse IV, Apr 20 2010

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

A033282 Triangle read by rows: T(n, k) is the number of diagonal dissections of a convex n-gon into k+1 regions.

Original entry on oeis.org

1, 1, 2, 1, 5, 5, 1, 9, 21, 14, 1, 14, 56, 84, 42, 1, 20, 120, 300, 330, 132, 1, 27, 225, 825, 1485, 1287, 429, 1, 35, 385, 1925, 5005, 7007, 5005, 1430, 1, 44, 616, 4004, 14014, 28028, 32032, 19448, 4862, 1, 54, 936, 7644, 34398, 91728, 148512, 143208, 75582, 16796

Offset: 3

N. J. A. Sloane

T(n+3, k) is also the number of compatible k-sets of cluster variables in Fomin and Zelevinsky's cluster algebra of finite type A_n. Take a row of this triangle regarded as a polynomial in x and rewrite as a polynomial in y := x+1. The coefficients of the polynomial in y give a row of the triangle of Narayana numbers A001263. For example, x^2 + 5*x + 5 = y^2 + 3*y + 1. - Paul Boddington, Mar 07 2003
Number of standard Young tableaux of shape (k+1,k+1,1^(n-k-3)), where 1^(n-k-3) denotes a sequence of n-k-3 1's (see the Stanley reference).
Number of k-dimensional 'faces' of the n-dimensional associahedron (see Simion, p. 168). - Mitch Harris, Jan 16 2007
Mirror image of triangle A126216. - Philippe Deléham, Oct 19 2007
For relation to Lagrange inversion or series reversion and the geometry of associahedra or Stasheff polytopes (and other combinatorial objects) see A133437. - Tom Copeland, Sep 29 2008
Row generating polynomials 1/(n+1)*Jacobi_P(n,1,1,2*x+1). Row n of this triangle is the f-vector of the simplicial complex dual to an associahedron of type A_n [Fomin & Reading, p. 60]. See A001263 for the corresponding array of h-vectors for associahedra of type A_n. See A063007 and A080721 for the f-vectors for associahedra of type B and type D respectively. - Peter Bala, Oct 28 2008
f-vectors of secondary polytopes for Grobner bases for optimization and integer programming (see De Loera et al. and Thomas). - Tom Copeland, Oct 11 2011
From Devadoss and O'Rourke's book: The Fulton-MacPherson compactification of the configuration space of n free particles on a line segment with a fixed particle at each end is the n-Dim Stasheff associahedron whose refined f-vector is given in A133437 which reduces to A033282. - Tom Copeland, Nov 29 2011
Diagonals of A132081 are rows of A033282. - Tom Copeland, May 08 2012
The general results on the convolution of the refined partition polynomials of A133437, with u_1 = 1 and u_n = -t otherwise, can be applied here to obtain results of convolutions of these polynomials. - Tom Copeland, Sep 20 2016
The signed triangle t(n, k) =(-1)^k* T(n+2, k-1), n >= 1, k = 1..n, seems to be obtainable from the partition array A111785 (in Abramowitz-Stegun order) by adding the entries corresponding to the partitions of n with the number of parts k. E.g., triangle t, row n=4: -1, (6+3) = 9, -21, 14. - Wolfdieter Lang, Mar 17 2017
The preceding conjecture by Lang is true. It is implicit in Copeland's 2011 comments in A086810 on the relations among a gf and its compositional inverse for that entry and inversion through A133437 (a differently normalized version of A111785), whose integer partitions are the same as those for A134685. (An inversion pair in Copeland's 2008 formulas below can also be used to prove the conjecture.) In addition, it follows from the relation between the inversion formula of A111785/A133437 and the enumeration of distinct faces of associahedra. See the MathOverflow link concernimg Loday and the Aguiar and Ardila reference in A133437 for proofs of the relations between the partition polynomials for inversion and enumeration of the distinct faces of the A_n associahedra, or Stasheff polytopes. - Tom Copeland, Dec 21 2017
The rows seem to give (up to sign) the coefficients in the expansion of the integer-valued polynomial (x+1)*(x+2)^2*(x+3)^2*...*(x+n)^2*(x+n+1)/(n!*(n+1)!) in the basis made of the binomial(x+i,i). - F. Chapoton, Oct 07 2022
Chapoton's observation above is correct: the precise expansion is (x+1)*(x+2)^2*(x+3)^2*...*(x+n)^2*(x+n+1)/ (n!*(n+1)!) = Sum_{k = 0..n-1} (-1)^k*T(n+2,n-k-1)*binomial(x+2*n-k,2*n-k), as can be verified using the WZ algorithm. For example, n = 4 gives (x+1)*(x+2)^2*(x+3)^2*(x+4)^2*(x+5)/(4!*5!) = 14*binomial(x+8,8) - 21*binomial(x+7,7) + 9*binomial(x+6,6) - binomial(x+5,5). - Peter Bala, Jun 24 2023

			The triangle T(n, k) begins:
n\k  0  1   2    3     4     5      6      7     8     9
3:   1
4:   1  2
5:   1  5   5
6:   1  9  21   14
7:   1 14  56   84    42
8:   1 20 120  300   330   132
9:   1 27 225  825  1485  1287    429
10:  1 35 385 1925  5005  7007   5005   1430
11:  1 44 616 4004 14014 28028  32032  19448  4862
12:  1 54 936 7644 34398 91728 148512 143208 75582 16796
... reformatted. - _Wolfdieter Lang_, Mar 17 2017

S. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton Univ. Press, 2011 (See p. 241.)
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Exercise 7.50, pages 379, 573.
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 5.8.

Vincenzo Librandi, Table of n, a(n) for n = 3..2000
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.6.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
Karin Baur and P. P. Martin, The fibres of the Scott map on polygon tilings are the flip equivalence classes, arXiv:1601.05080 [math.CO], 2016.
David Beckwith, Legendre polynomials and polygon dissections?, Amer. Math. Monthly, 105 (1998), 256-257.
William Butler, Andrew Kalotay and N. J. A. Sloane, Correspondence, 1974
Arthur Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff. (See p. 239.)
Adrian Celestino and Yannic Vargas, Schröder trees, antipode formulas and non-commutative probability, arXiv:2311.07824 [math.CO], 2023.
Frédéric Chapoton, Enumerative properties of generalized associahedra, Séminaire Lotharingien de Combinatoire, B51b (2004), 16 pp.
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.
Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 16.
Jesús A. De Loera, Jörg Rambau, and Francisco Santos Leal, Triangulations of Point Sets [From Tom Copeland Oct 11 2011]
Satyan L. Devadoss, Combinatorial Equivalence of Real Moduli Spaces, Notices Amer. Math. Soc. 51 (2004), no. 6, 620-628.
Satyan L. Devadoss and Ronald C. Read, Cellular structures determined by polygons and trees, arXiv/0008145 [math.CO], 2000. [From Tom Copeland Nov 21 2017]
Anton Dochtermann, Face rings of cycles, associahedra, and standard Young tableaux, arXiv preprint arXiv:1503.06243 [math.CO], 2015.
Brian Drake, Ira M. Gessel, and Guoce Xin, Three Proofs and a Generalization of the Goulden-Litsyn-Shevelev Conjecture on a Sequence Arising in Algebraic Geometry, J. of Integer Sequences, Vol. 10 (2007), Article 07.3.7.
Cassandra Durell and Stefan Forcey, Level-1 Phylogenetic Networks and their Balanced Minimum Evolution Polytopes, arXiv:1905.09160 [math.CO], 2019.
P. Flajolet and M. Noy, Analytic Combinatorics of Non-crossing Configurations, Discrete Math., 204, 1999, 203-229.
Sergey Fomin and Nathan Reading, Root systems and generalized associahedra, Lecture notes for IAS/Park-City 2004, arXiv:math/0505518 [math.CO], 2005-2008. [From _Peter Bala_, Oct 28 2008]
Sergey Fomin and Andrei Zelevinsky, Cluster algebras I: Foundations, arXiv:math/0104151 [math.RT], 2001.
Sergey Fomin and Andrei Zelevinsky, Cluster algebras I: Foundations, J. Amer. Math. Soc. 15 (2002) no.2, 497-529.
Sergey Fomin and Andrei Zelevinsky, Y-systems and generalized associahedra, Ann. of Math. (2) 158 (2003), no. 3, 977-1018.
Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
Rijun Huang, Fei Teng, and Bo Feng, Permutation in the CHY-Formulation, arXiv:1801.08965 [hep-th], 2018.
Germain Kreweras, Sur les partitions non croisées d'un cycle, (French) Discrete Math. 1 (1972), no. 4, 333--350. MR0309747 (46 #8852).
Germain Kreweras, Sur les hiérarchies de segments, Cahiers Bureau Universitaire Recherche Opérationnelle, Cahier 20, Inst. Statistiques, Univ. Paris, 1973.
Germain 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)
Germain Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
Germain Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
Thibault Manneville and Vincent Pilaud, Compatibility fans for graphical nested complexes, arXiv:1501.07152 [math.CO], 2015.
Sebastian Mizera, Combinatorics and topology of Kawai-Lewellen-Tye relations J. High Energy Phys. 2017, No. 8, Paper No. 97, 54 p. (2017).
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv:1403.5962 [math.CO], 2014.
Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, arXiv:1505.07665 [math.CO], 2015.
Vincent Pilaud and V. Pons, Permutrees, arXiv:1606.09643 [math.CO], 2016-2017.
Ronald C. Read, On general dissections of a polygon, Aequat. Math. 18 (1978), 370-388.
Dean Rubine, Exercises for A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode, arXiv:2507.13045 [math.CO], 2025. See p. 9.
Rodica Simion, Convex Polytopes and Enumeration, Adv. in Appl. Math. 18 (1997) pp. 149-180.
Richard P. Stanley, Polygon dissections and standard Young tableaux, J. Comb. Theory, Ser. A, 76, 175-177, 1996.
Rekha R. Thomas, Lectures in Geometric Combinatorics [_Tom Copeland_, Oct 11 2011]

Cf. diagonals: A000012, A000096, A033275, A033276, A033277, A033278, A033279; A000108, A002054, A002055, A002056, A007160, A033280, A033281; row sums: A001003 (Schroeder numbers, first term omitted). See A086810 for another version.
A007160 is a diagonal. Cf. A001263.
With leading zero: A086810.
Cf. A019538 'faces' of the permutohedron.
Cf. A063007 (f-vectors type B associahedra), A080721 (f-vectors type D associahedra), A126216 (mirror image).
Cf. A248727 for a relation to f-polynomials of simplices.
Cf. A111785 (contracted partition array, unsigned; see a comment above).
Antidiagonal sums give A005043. - Jordan Tirrell, Jun 01 2017

[[Binomial(n-3, k)*Binomial(n+k-1, k)/(k+1): k in [0..(n-3)]]: n in [3..12]];  // G. C. Greubel, Nov 19 2018

T:=(n,k)->binomial(n-3,k)*binomial(n+k-1,k)/(k+1): seq(seq(T(n,k),k=0..n-3),n=3..12); # Muniru A Asiru, Nov 24 2018

t[n_, k_] = Binomial[n-3, k]*Binomial[n+k-1, k]/(k+1);
Flatten[Table[t[n, k], {n, 3, 12}, {k, 0, n-3}]][[1 ;; 52]] (* Jean-François Alcover, Jun 16 2011 *)

Q=(1+z-(1-(4*w+2+O(w^20))*z+z^2+O(z^20))^(1/2))/(2*(1+w)*z);for(n=3,12,for(m=1,n-2,print1(polcoef(polcoef(Q,n-2,z),m,w),", "))) \\ Hugo Pfoertner, Nov 19 2018

for(n=3,12, for(k=0,n-3, print1(binomial(n-3,k)*binomial(n+k-1,k)/(k+1), ", "))) \\ G. C. Greubel, Nov 19 2018

[[ binomial(n-3,k)*binomial(n+k-1,k)/(k+1) for k in (0..(n-3))] for n in (3..12)] # G. C. Greubel, Nov 19 2018

G.f. G = G(t, z) satisfies (1+t)*G^2 - z*(1-z-2*t*z)*G + t*z^4 = 0.
T(n, k) = binomial(n-3, k)*binomial(n+k-1, k)/(k+1) for n >= 3, 0 <= k <= n-3.
From Tom Copeland, Nov 03 2008: (Start)
Two g.f.s (f1 and f2) for A033282 and their inverses (x1 and x2) can be derived from the Drake and Barry references.
1. a: f1(x,t) = y = {1 - (2t+1) x - sqrt[1 - (2t+1) 2x + x^2]}/[2x (t+1)] = t x + (t + 2 t^2) x^2 + (t + 5 t^2 + 5 t^3) x^3 + ...
b: x1 = y/[t + (2t+1)y + (t+1)y^2] = y {1/[t/(t+1) + y] - 1/(1+y)} = (y/t) - (1+2t)(y/t)^2 + (1+ 3t + 3t^2)(y/t)^3 +...
2. a: f2(x,t) = y = {1 - x - sqrt[(1-x)^2 - 4xt]}/[2(t+1)] = (t/(t+1)) x + t x^2 + (t + 2 t^2) x^3 + (t + 5 t^2 + 5 t^3) x^4 + ...
b: x2 = y(t+1) [1- y(t+1)]/[t + y(t+1)] = (t+1) (y/t) - (t+1)^3 (y/t)^2 + (t+1)^4 (y/t)^3 + ...
c: y/x2(y,t) = [t/(t+1) + y] / [1- y(t+1)] = t/(t+1) + (1+t) y + (1+t)^2 y^2 + (1+t)^3 y^3 + ...
x2(y,t) can be used along with the Lagrange inversion for an o.g.f. (A133437) to generate A033282 and show that A133437 is a refinement of A033282, i.e., a refinement of the f-polynomials of the associahedra, the Stasheff polytopes.
y/x2(y,t) can be used along with the indirect Lagrange inversion (A134264) to generate A033282 and show that A134264 is a refinement of A001263, i.e., a refinement of the h-polynomials of the associahedra.
f1[x,t](t+1) gives a generator for A088617.
f1[xt,1/t](t+1) gives a generator for A060693, with inverse y/[1 + t + (2+t) y + y^2].
f1[x(t-1),1/(t-1)]t gives a generator for A001263, with inverse y/[t + (1+t) y + y^2].
The unsigned coefficients of x1(y t,t) are A074909, reverse rows of A135278. (End)
G.f.: 1/(1-x*y-(x+x*y)/(1-x*y/(1-(x+x*y)/(1-x*y/(1-(x+x*y)/(1-x*y/(1-.... (continued fraction). - Paul Barry, Feb 06 2009
Let h(t) = (1-t)^2/(1+(u-1)*(1-t)^2) = 1/(u + 2*t + 3*t^2 + 4*t^3 + ...), then a signed (n-1)-th row polynomial of A033282 is given by u^(2n-1)*(1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=2. The power series expansion of h(t) is related to A181289 (cf. A086810). - Tom Copeland, Sep 06 2011
With a different offset, the row polynomials equal 1/(1 + x)*Integral_{0..x} R(n,t) dt, where R(n,t) = Sum_{k = 0..n} binomial(n,k)*binomial(n+k,k)*t^k are the row polynomials of A063007. - Peter Bala, Jun 23 2016
n-th row polynomial = ( LegendreP(n-1,2*x + 1) - LegendreP(n-3,2*x + 1) )/((4*n - 6)*x*(x + 1)), n >= 3. - Peter Bala, Feb 22 2017
n*T(n+1, k) = (4n-6)*T(n, k-1) + (2n-3)*T(n, k) - (n-3)*T(n-1, k) for n >= 4. - Fang Lixing, May 07 2019

Missing factor of 2 for expansions of f1 and f2 added by Tom Copeland, Apr 12 2009

A007564 Shifts left when INVERT transform applied thrice.

Original entry on oeis.org

1, 1, 4, 19, 100, 562, 3304, 20071, 124996, 793774, 5120632, 33463102, 221060008, 1473830308, 9904186192, 67015401391, 456192667396, 3122028222934, 21467769499864, 148246598341018, 1027656663676600, 7148588698592956, 49884553176689584

Offset: 0

N. J. A. Sloane

More generally, coefficients of (1+m*x-sqrt(m^2*x^2-(2*m+2)*x+1))/(2*m*x) are given by a(n) = Sum_{k=0..n} (m+1)^k*N(n,k) where N(n,k) = (1/n)*binomial(n,k)*binomial(n,k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 24 2003
If y = x*A(x) then 3*y^2 - (1+2*x)*y + x = 0 and x = y*(1-3*y)/(1-2*y). - Michael Somos, Sep 28 2003
The sequence 0,1,4,19,... with g.f. (1-4*x-sqrt(1-8*x+4*x^2))/(6*x) and has a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n-1,2k)*C(k)*4^(n-1-2*k)*3^k. a(n+1) = Sum_{k=0..floor(n/2)} binomial(n,2*k)*C(k)*4^(n-2*k)*3^k counts Motzkin paths of length n in which the level steps have 4 colors and the up steps have 3. It is the binomial transform of A107264 and corresponds to the series reversion of x/(1+4*x+3*x^2). - Paul Barry, May 18 2005
The Hankel transform of this sequence is 3^binomial(n+1,2). - Philippe Deléham, Oct 29 2007
a(n) is the number of Schroder paths of semilength n in which there are no (2,0)-steps at level 0 and at a higher level they come in 2 colors. Example: a(2)=4 because we have UDUD, UUDD, UBD, and URD, where U=(1,1), D=(1,-1), while B (R) is a blue (red) (2,0)-step. - Emeric Deutsch, May 02 2011
a(n) is the number of Schroder paths of semilength n-1 in which the (2,0)-steps at level 0 come in 3 colors and those at a higher level come in 2 colors. Example: a(3)=19 because, denoting  U=(1,1), H=(1,0), and D=(1,-1), we have 3^2 = 9 paths of shape HH, 3 paths of shape HUD, 3 paths of shape UDH, 2 paths of shape UHD, and 1 path of each of the shapes UDUD and UUDD. - Emeric Deutsch, May 02 2011
From David Callan, Jun 21 2013: (Start)
a(n) = number of (left) planted binary trees with n edges in which each vertex has a designated favorite neighbor. Planted binary trees are counted by the Catalan numbers A000108.
Example: for n=2, there are 2 planted binary trees: edges LL and LR from the root (L=left, R=right). Each has just one vertex with 2 neighbors, and so a(2)=4.
Proof outline: each vertex has 1,2 or 3 neighbors. Let X (resp. Y) denote the number of vertices with 2 (resp. 3) neighbors. Then X + 2Y = n - 1 (split the non-root edges into pairs with a common parent vertex and singletons). Thus the number of choices for designating favorite neighbors is 2^X * 3^Y = 2^(n-1)(3/4)^Y. The distribution for Y is known because, under the rotation correspondence, a.k.a. the deBruijn-Morselt bijection, vertices with 2 children in an n-edge planted binary tree correspond to DDUs in a Dyck path, and DDUs have the Touchard distribution (A091894) with gf F(x,y) = (1-2x+2xy - sqrt(1-4x+4x^2-4x^2 y))/(2xy). The desired g.f., Sum_{n>=1} a(n)*x^n, is therefore 1/2*(F(2x,3/4)-1). (End)

			G.f. = 1 + x + 4*x^2 + 19*x^3 + 100*x^4 + 562*x^5 + 3304*x^6 + 20071*x^7 + 124996*x^8 + ...

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

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0 to 100 by T. D. Noe)
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.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry and Aoife Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.8.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
Z. Chen and H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 arXiv:1608.02448 [math.CO], 2016. Eq. (1.13) a=1, b=3.
C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 443
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 11.
N. J. A. Sloane, Transforms

Cf. A047891, A054872.

A007564_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]+3*add(a[j]*a[w-j-1],j=1..w-1) od;
convert(a, list) end: A007564_list(21); # Peter Luschny, May 19 2011

a[0]=1; a[1]=1; a[n_]/;n>=2 := a[n] = a[n-1] + 3 Sum[a[k-1]a[n-k],{k,n-1}] ; Table[a[n],{n,0,10}] (* David Callan, Aug 25 2009 *)
Table[Hypergeometric2F1[-n, 1 - n, 2, 3], {n, 0, 22}] (* Arkadiusz Wesolowski, Aug 13 2012 *)
Table[(2^n (LegendreP[n+1, 2] - LegendreP[n-1, 2]) + 2 KroneckerDelta[n])/(6n+3), {n, 0, 20}] (* Vladimir Reshetnikov, Nov 01 2015 *)
CoefficientList[Series[(1+2x-Sqrt[1-8x+4x^2])/(6x),{x,0,30}],x] (* Harvey P. Dale, Feb 07 2016 *)

{a(n) = if( n<1, n==0, sum( k=0, n, 3^k * binomial( n, k) * binomial( n, k+1)) / n)} /* Michael Somos, Sep 28 2003 */

{a(n) = if( n<0, 0, n++; polcoeff( serreverse( x * (1 - 3*x) / (1 - 2*x) + x * O(x^n)), n))} /* Michael Somos, Sep 28 2003 */

a(n) = (2^n*(pollegendre(n+1,2)-pollegendre(n-1,2)) + 2*(n==0))/(6*n+3); \\ Michel Marcus, Nov 02 2015

x='x+O('x^100); Vec((1+2*x-sqrt(1-8*x+4*x^2))/(6*x)) \\ Altug Alkan, Nov 02 2015

G.f.: (1+2*x-sqrt(1-8*x+4*x^2))/(6*x). - Emeric Deutsch, Nov 03 2001
a(0)=1; for n>=1, a(n) = Sum_{k=0..n} 3^k*N(n,k) where N(n,k) = (1/n)*binomial(n, k)*binomial(n, k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 24 2003
a(n) = Sum_{k=0..n} A088617(n, k)*3^k*(-2)^(n-k). - Philippe Deléham, Jan 21 2004
With offset 1: a(1) = 1, a(n) = -2*a(n-1) + 3*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004
D-finite with recurrence a(n) = (4*(2n-1)*a(n-1) - 4*(n-2)*a(n-2)) / (n+1) for n>=2, a(0) = a(1) = 1. - Philippe Deléham, Aug 19 2005
From Paul Barry, Dec 15 2008: (Start)
G.f.: 1/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x........ (continued fraction).
The g.f. of a(n+1) is 1/(1-4x-3x^2/(1-4x-3x^2/(1-4x-3x^2/(1-4x-3x^2.... (continued fraction). (End)
a(0) = 1, for n>=1, 3a(n) = A047891(n). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009
a(n) = upper left term in M^n, M = the production matrix:
1, 1
3, 3, 3
1, 1, 1, 1
3, 3, 3, 3, 3
1, 1, 1, 1, 1, 1
...
- Gary W. Adamson, Jul 08 2011
G.f.: A(x)= (1+2*x-sqrt(1-8*x+4*x^2))/(6*x)= 1/G(0); G(k)= 1 + 2*x - 3*x/G(k+1); (continued fraction, 1-step ). - Sergei N. Gladkovskii, Jan 05 2012
a(n) ~ sqrt(6+4*sqrt(3))*(4+2*sqrt(3))^n/(6*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 07 2012
a(n) = 2^n/sqrt(3)*LegendreP(n,-1,2) for n >= 1, where LegendreP is the associated Legendre function of the first kind, in Maple's notation. - Robert Israel, Mar 24 2015

A059231 Number of different lattice paths running from (0,0) to (n,0) using steps from S = {(k,k) or (k,-k): k positive integer} that never go below the x-axis.

Original entry on oeis.org

1, 1, 5, 29, 185, 1257, 8925, 65445, 491825, 3768209, 29324405, 231153133, 1841801065, 14810069497, 120029657805, 979470140661, 8040831465825, 66361595715105, 550284185213925, 4582462506008253, 38306388126997785, 321327658068506121, 2703925940081270205

Offset: 0

Wenjin Woan, Jan 20 2001

If y = x*A(x) then 4*y^2 - (1 + 3*x)*y + x = 0 and x = y*(1 - 4*y) / (1 - 3*y). - Michael Somos, Sep 28 2003
a(n) = A059450(n, n). - Michael Somos, Mar 06 2004
The Hankel transform of this sequence is 4^binomial(n+1,2). - Philippe Deléham, Oct 29 2007
a(n) is the number of Schroder paths of semilength n in which there are no (2,0)-steps at level 0 and at a higher level they come in 3 colors. Example: a(2)=5 because we have UDUD, UUDD, UBD, UGD, and URD, where U=(1,1), D=(1,-1), while B, G, and R are, respectively, blue, green, and red (2,0)-steps. - Emeric Deutsch, May 02 2011
Shifts left when INVERT transform applied four times. - Benedict W. J. Irwin, Feb 02 2016

			a(3) = 29 since the top row of Q^2 = (5, 8, 16, 0, 0, 0, ...), and 5 + 8 + 16 = 29.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry and Aoife Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.8.
Zhi Chen and Hao Pan, Identities involving weighted Catalan, Schroder and Motzkin paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=1, b=4.
Curtis Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28 (the sequence d_n).
Curtis Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
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.
Joseph P. S. Kung and Anna de Mier, Catalan lattice paths with rook, bishop and spider steps, J. Comb. Theor., Series A (2013) Vol. 120, Issue 2, 379-389.
Gregory J. Morrow, Laws relating runs and steps in gambler’s ruin, Stochastic Proc. Appl. (2024) Vol. 125, Issue 5, 2010-2025.
Gregory Morrow, Some probability distributions and integer sequences related to rook paths, Univ. Colorado Springs (2024). See pp. 1, 4, 15, 22. DOI
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
Wen-jin Woan, Diagonal lattice paths, Congr. Numer. 151 (2001) 173-178.

Cf. A000108, A001003, A007564, A127846.
Row sums of A086873.
Column k=2 of A227578. - Alois P. Heinz, Jul 17 2013

gf := (1+3*x-sqrt(9*x^2-10*x+1))/(8*x): s := series(gf, x, 100): for i from 0 to 50 do printf(`%d,`,coeff(s, x, i)) od:
A059231_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]+4*add(a[j]*a[w-j-1],j=1..w-1) od;
convert(a, list) end: A059231_list(20); # Peter Luschny, May 19 2011

Join[{1},Table[-I 3^n/2LegendreP[n,-1,5/3],{n,40}]] (* Harvey P. Dale, Jun 09 2011 *)
Table[Hypergeometric2F1[-n, 1 - n, 2, 4], {n, 0, 22}] (* Arkadiusz Wesolowski, Aug 13 2012 *)

{a(n) = if( n<0, 0, polcoeff( (1 + 3*x - sqrt(1 - 10*x + 9*x^2 + x^2 * O(x^n))) / (8*x), n))}; /* Michael Somos, Sep 28 2003 */

{a(n) = if( n<0, 0, n++; polcoeff( serreverse( x * (1 - 4*x) / (1 - 3*x) + x * O(x^n)), n))}; /* Michael Somos, Sep 28 2003 */

# Algorithm of L. Seidel (1877)
def A059231_list(n) :
    D = [0]*(n+2); D[1] = 1
    R = []; b = False; h = 1
    for i in range(2*n) :
        if b :
            for k in range(1, h, 1) : D[k] += 2*D[k+1]
        else :
            for k in range(h, 0, -1) : D[k] += 2*D[k-1]
            h += 1
        b = not b
        if b : R.append(D[1])
    return R
A059231_list(23)  # Peter Luschny, Oct 19 2012

a(n) = Sum_{k=0..n} 4^k*N(n, k) where N(n, k) = (1/n)*binomial(n, k)*binomial(n, k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 10 2003
a(n) = 3^n/2*LegendreP(n, -1, 5/3). - Vladeta Jovovic, Sep 17 2003
G.f.: (1 + 3*x - sqrt(1 - 10*x + 9*x^2)) / (8*x) = 2 / (1 + 3*x + sqrt(1 - 10*x + 9*x^2)). - Michael Somos, Sep 28 2003
a(n) = Sum_{k=0..n} A088617(n, k)*4^k*(-3)^(n-k). - Philippe Deléham, Jan 21 2004
With offset 1: a(1)=1, a(n) = -3*a(n-1) + 4*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004
D-finite with recurrence a(n) = (5(2n-1)a(n-1) - 9(n-2)a(n-2))/(n+1) for n>=2; a(0)=a(1)=1. - Emeric Deutsch, Mar 20 2004
Moment representation: a(n)=(1/(8*Pi))*Int(x^n*sqrt(-x^2+10x-9)/x,x,1,9)+(3/4)*0^n. - Paul Barry, Sep 30 2009
a(n) = upper left term in M^n, M = the production matrix:
  1, 1
  4, 4, 4
  1, 1, 1, 1
  4, 4, 4, 4, 4
  1, 1, 1, 1, 1, 1
  ... - Gary W. Adamson, Jul 08 2011
a(n) is the sum of top row terms of Q^(n-1), where Q = the following infinite square production matrix:
  1, 4, 0, 0, 0, ...
  1, 1, 4, 0, 0, ...
  1, 1, 1, 4, 0, ...
  1, 1, 1, 1, 4, ...
  ... - Gary W. Adamson, Aug 23 2011
G.f.: (1+3*x-sqrt(9*x^2-10*x+1))/(8*x)=(1+3*x -G(0))/(4*x) ; G(k)= 1+x*3-x*4/G(k+1); (continued fraction, 1-step ). - Sergei N. Gladkovskii, Jan 05 2012
a(n) ~ sqrt(2)*3^(2*n+1)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 11 2012
a(n) = A127846(n) for n>0. - Philippe Deléham, Apr 03 2013
0 = a(n)*(+81*a(n+1) - 225*a(n+2) + 36*a(n+3)) + a(n+1)*(+45*a(n+1) + 82*a(n+2) - 25*a(n+3)) + a(n+2)*(+5*a(n+2) + a(n+3)) for all n>=0. - Michael Somos, Aug 25 2014
G.f.: 1/(1 - x/(1 - 4*x/(1 - x/(1 - 4*x/(1 - x/(1 - ...)))))), a continued fraction. - Ilya Gutkovskiy, Aug 10 2017

A034827 a(n) = 2*binomial(n,4).

Original entry on oeis.org

0, 0, 0, 0, 2, 10, 30, 70, 140, 252, 420, 660, 990, 1430, 2002, 2730, 3640, 4760, 6120, 7752, 9690, 11970, 14630, 17710, 21252, 25300, 29900, 35100, 40950, 47502, 54810, 62930, 71920, 81840, 92752, 104720, 117810, 132090, 147630, 164502, 182780

Offset: 0

N. J. A. Sloane

Also number of ways to insert two pairs of parentheses into a string of n-4 letters (allowing empty pairs of parentheses). E.g., there are 30 ways for 2 letters. Cf. A002415.
2,10,30,70, ... gives orchard crossing number of complete graph K_n. - Ralf Stephan, Mar 28 2003
If Y is a 2-subset of an n-set X then, for n>=4, a(n-1) is the number of 4-subsets and 5-subsets of X having exactly one element in common with Y. - Milan Janjic, Dec 28 2007
Middle column of table on p. 6 of Feder and Garber. - Jonathan Vos Post, Apr 23 2009
Number of pairs of non-intersecting lines when each of n points around a circle is joined to every other point by straight lines. A pair of lines is considered non-intersecting if the lines do not intersect in either the interior or the boundary of a circle. - Melvin Peralta, Feb 05 2016
From a(2), convolution of the oblong numbers (A002378) with the nonnegative numbers (A001477). - Bruno Berselli, Oct 24 2016
Also the number of 3-cycles in the n-triangular honeycomb bishop graph. - Eric W. Weisstein, Aug 10 2017

Charles Jordan, Calculus of Finite Differences, Chelsea, 1965, p. 449.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Bruno Berselli, Table of n, a(n) for n = 0..1000
M. Aganagic, A. Klemm and C. Vafa, Disk Instantons, Mirror Symmetry and the Duality Web, arXiv:hep-th/0105045, 2001.
Steven Edwards and William Griffiths, On Generalized Delannoy Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.3.6.
Elie Feder and David Garber, The Orchard crossing number of an abstract graph, arXiv:math/0303317 [math.CO], 2003-2009.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), pp. 1917-1926.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014-2015.
Eric Weisstein's World of Mathematics, Graph Cycle.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

A diagonal of A088617.
Cf. A033487, A050534, A060008.
Partial sums of A007290.
Cf. A001477, A002378.
Cf. A051843 (4-cycles in the triangular honeycomb bishop graph), A290775 (5-cycles), A290779 (6-cycles).

[2*Binomial(n,4): n in [0..40]]; // Vincenzo Librandi, Oct 20 2013

[seq(binomial(n,4)*2,n=0..40)]; # Zerinvary Lajos, Jul 18 2006

CoefficientList[Series[2 x^4/(1 - x)^5, {x, 0, 40}], x] (* Vincenzo Librandi, Oct 20 2013 *)
LinearRecurrence[{5, -10, 10, -5, 1}, {0, 0, 0, 0, 2}, 50] (* Harvey P. Dale, Jun 09 2016 *)
Table[2 Binomial[n, 4], {n, 0, 40}] (* Bruno Berselli, Oct 24 2016 *)
2 Binomial[Range[0, 20], 4] (* Eric W. Weisstein, Aug 10 2017 *)

a(n)=2*binomial(n,4) \\ Charles R Greathouse IV, Jun 23 2015

a(n) = A096338(2*n-6) = 2*A000332(n), n>2. - R. J. Mathar, Nov 08 2010
G.f.: 2*x^4/(1-x)^5. - Colin Barker, Feb 29 2012
a(n) = Sum_{k=1..n-3} ( Sum_{i=1..k} i*(2*k-n+4) ). - Wesley Ivan Hurt, Sep 26 2013
E.g.f.: x^4*exp(x)/12. - G. C. Greubel, Feb 23 2017
From Amiram Eldar, Jul 19 2022: (Start)
Sum_{n>=4} 1/a(n) = 2/3.
Sum_{n>=4} (-1)^n/a(n) = 16*log(2) - 32/3. (End)

A060693 Triangle (0 <= k <= n) read by rows: T(n, k) is the number of Schröder paths from (0,0) to (2n,0) having k peaks.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 5, 10, 6, 1, 14, 35, 30, 10, 1, 42, 126, 140, 70, 15, 1, 132, 462, 630, 420, 140, 21, 1, 429, 1716, 2772, 2310, 1050, 252, 28, 1, 1430, 6435, 12012, 12012, 6930, 2310, 420, 36, 1, 4862, 24310, 51480, 60060, 42042, 18018, 4620, 660, 45, 1, 16796

Offset: 0

F. Chapoton, Apr 20 2001

The rows sum to A006318 (Schroeder numbers), the left column is A000108 (Catalan numbers); the next-to-left column is A001700, the alternating sum in each row but the first is 0.
T(n,k) is the number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1), H=(2,0) and never going below the x-axis) from (0,0) to (2n,0), having k peaks. Example: T(2,1)=3 because we have UU*DD, U*DH and HU*D, the peaks being shown by *. E.g., T(n,k) = binomial(n,k)*binomial(2n-k,n-1)/n for n>0. - Emeric Deutsch, Dec 06 2003
A090181*A007318 as infinite lower triangular matrices. - Philippe Deléham, Oct 14 2008
T(n,k) is also the number of rooted plane trees with maximal degree 3 and k vertices of degree 2 (a node may have at most 2 children, and there are exactly k nodes with 1 child). Equivalently, T(n,k) is the number of syntactically different expressions that can be formed that use a unary operation k times, a binary operation n-k times, and nothing else (sequence of operands is fixed). - Lars Hellstrom (Lars.Hellstrom(AT)residenset.net), Dec 08 2009

			Triangle begins:
00: [    1]
01: [    1,     1]
02: [    2,     3,      1]
03: [    5,    10,      6,      1]
04: [   14,    35,     30,     10,      1]
05: [   42,   126,    140,     70,     15,      1]
06: [  132,   462,    630,    420,    140,     21,     1]
07: [  429,  1716,   2772,   2310,   1050,    252,    28,    1]
08: [ 1430,  6435,  12012,  12012,   6930,   2310,   420,   36,   1]
09: [ 4862, 24310,  51480,  60060,  42042,  18018,  4620,  660,  45,  1]
10: [16796, 92378, 218790, 291720, 240240, 126126, 42042, 8580, 990, 55, 1]
...

Vincenzo Librandi, Rows n = 0..100, flattened
J. Agapito, A. Mestre, P. Petrullo, and M. Torres, Counting noncrossing partitions via Catalan triangles, CEAFEL Seminar, June 30, 2015.
Jean-Christophe Aval and François Bergeron, Rectangular Schröder Parking Functions Combinatorics, arXiv:1603.09487 [math.CO], 2016.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, J. Integer Sequ., Vol. 9 (2006), Article 06.2.4.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
Paul Barry, The Central Coefficients of a Family of Pascal-like Triangles and Colored Lattice Paths, J. Int. Seq., Vol. 22 (2019), Article 19.1.3.
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See p. 25.
David Callan and Toufik Mansour, Five subsets of permutations enumerated as weak sorting permutations, arXiv:1602.05182 [math.CO], 2016.
G. E. Cossali, A Common Generating Function of Catalan Numbers and Other Integer Sequences, J. Int. Seqs. 6 (2003).
Dan Drake, Bijections from Weighted Dyck Paths to Schröder Paths, J. Int. Seq. 13 (2010) # 10.9.2
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
Krishna Menon and Anurag Singh, Grassmannian permutations avoiding identity, arXiv:2212.13794 [math.CO], 2022.
Jean-Christophe Novelli and Jean-Yves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959 [math.CO], 2012.

Cf. A006318, A000108, A001700.
Triangle in A088617 transposed.
Diagonals give A000108, A001700, A002457, A002802, A002803; A000012, A000217, A034827, A000910, A088625, A088626.
T(2n,n) gives A007004.
Cf. A001263, A033282, A086810, A088617, A097610, A101282.

A060693 := (n,k) -> binomial(n,k)*binomial(2*n-k,n)/(n-k+1); # Peter Luschny, May 17 2011

t[n_, k_] := Binomial[n, k]*Binomial[2 n - k, n]/(n - k + 1); Flatten[Table[t[n, k], {n, 0, 9}, {k, 0, n}]] (* Robert G. Wilson v, May 30 2011 *)

T(n, k) = binomial(n, k)*binomial(2*n - k, n)/(n - k + 1);
for(n=0, 10, for(k=0, n, print1(T(n, k),", ")); print); \\ Indranil Ghosh, Jul 28 2017

from sympy import binomial
def T(n, k): return binomial(n, k) * binomial(2 * n - k, n) / (n - k + 1)
for n in range(11): print([T(n, k) for k in range(n + 1)])  # Indranil Ghosh, Jul 28 2017

Triangle T(n, k) (0 <= k <= n) read by rows; given by [1, 1, 1, 1, 1, ...] DELTA [1, 0, 1, 0, 1, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 12 2003
If C_n(x) is the g.f. of row n of the Narayana numbers (A001263), C_n(x) = Sum_{k=1..n} binomial(n,k-1)*(binomial(n-1,k-1)/k) * x^k and T_n(x) is the g.f. of row n of T(n,k), then T_n(x) = C_n(x+1), or T(n,k) = [x^n]Sum_{k=1..n}(A001263(n,k)*(x+1)^k). - Mitch Harris, Jan 16 2007, Jan 31 2007
G.f.: (1 - t*y - sqrt((1-y*t)^2 - 4*y)) / 2.
T(n, k) = binomial(2n-k, n)*binomial(n, k)/(n-k+1). - Philippe Deléham, Dec 07 2003
A060693(n, k) = binomial(2*n-k, k)*A000108(n-k); A000108: Catalan numbers. - Philippe Deléham, Dec 30 2003
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A000108(n), A006318(n), A047891(n+1), A082298(n), A082301(n), A082302(n), A082305(n), A082366(n), A082367(n), for x = -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, respectively. - Philippe Deléham, Apr 01 2007
T(n,k) = Sum_{j>=0} A090181(n,j)*binomial(j,k). - Philippe Deléham, May 04 2007
Sum_{k=0..n} T(n,k)*x^(n-k) = (-1)^n*A107841(n), A080243(n), A000007(n), A000012(n), A006318(n), A103210(n), A103211(n), A133305(n), A133306(n), A133307(n), A133308(n), A133309(n) for x = -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, respectively. - Philippe Deléham, Oct 18 2007
From Paul Barry, Jan 29 2009: (Start)
G.f.: 1/(1-xy-x/(1-xy-x/(1-xy-x/(1-xy-x/(1-xy-x/(1-.... (continued fraction);
G.f.: 1/(1-(x+xy)/(1-x/(1-(x+xy)/(1-x/(1-(x+xy)/(1-.... (continued fraction). (End)
T(n,k) = [k<=n]*(Sum_{j=0..n} binomial(n,j)^2*binomial(j,k))/(n-k+1). - Paul Barry, May 28 2009
T(n,k) = A104684(n,k)/(n-k+1). - Peter Luschny, May 17 2011
From Tom Copeland, Sep 21 2011: (Start)
With F(x,t) = (1-(2+t)*x-sqrt(1-2*(2+t)*x+(t*x)^2))/(2*x) an o.g.f. (nulling the n=0 term) in x for the A060693 polynomials in t,
  G(x,t) = x/(1+t+(2+t)*x+x^2) is the compositional inverse in x.
Consequently, with H(x,t) = 1/(dG(x,t)/dx) = (1+t+(2+t)*x+x^2)^2 / (1+t-x^2), the n-th A060693 polynomial in t is given by (1/n!)*((H(x,t)*d/dx)^n) x evaluated at x=0, i.e., F(x,t) = exp(x*H(u,t)*d/d) u, evaluated at u = 0.
  Also, dF(x,t)/dx = H(F(x,t),t). (End)
See my 2008 formulas in A033282 to relate this entry to A088617, A001263, A086810, and other matrices. - Tom Copeland, Jan 22 2016
Rows of this entry are non-vanishing antidiagonals of A097610. See p. 14 of Agapito et al. for a bivariate generating function and its inverse. - Tom Copeland, Feb 03 2016
From Werner Schulte, Jan 09 2017: (Start)
T(n,k) = A126216(n,k-1) + A126216(n,k) for 0 < k < n;
Sum_{k=0..n} (-1)^k*(1+x*(n-k))*T(n,k) = x + (1-x)*A000007(n).
(End)
Conjecture: Sum_{k=0..n} (-1)^k*T(n,k)*(n+1-k)^2 = 1+n+n^2. - Werner Schulte, Jan 11 2017

More terms from Vladeta Jovovic, Apr 21 2001
New description from Philippe Deléham, Aug 12 2003
New name using a comment by Emeric Deutsch from Peter Luschny, Jul 26 2017

A107841 Series reversion of x(1-3x)/(1-x).

Original entry on oeis.org

1, 2, 10, 62, 430, 3194, 24850, 199910, 1649350, 13879538, 118669210, 1027945934, 9002083870, 79568077034, 708911026210, 6359857112438, 57403123415350, 520895417047010, 4749381474135850, 43489017531266654, 399755692955359630, 3687437532852484442, 34121911117572911410

Offset: 0

Paul Barry, May 24 2005

In general, the series reversion of x(1-r*x)/(1-x) has g.f. (1+x-sqrt(1+2*(1-2*r)*x+x^2))/(2*r) and general term given by a(n)=(1/(n+1))sum{k=0..n, C(n+1,k)C(2n-k,n)(-1)^k*r^(n-k)}; a(n)=(1/(n+1))sum{k=0..n, C(n+1,k+1)C(n+k,k)(-1)^(n-k)*r^k}; a(n)=sum{k=0..n, (1/(k+1))*C(n,k)C(n+k,k)(-1)^(n-k)*r^k}; a(n)=sum{k=0..n, A088617(n,k)*(-1)^(n-k)*r^k}.
The Hankel transform of this sequence is 6^C(n+1,2). - Philippe Deléham, Oct 29 2007
Number of Dyck n-paths with three colors of up (U,a,b) and one color of down (D) avoiding UD. - David Scambler, Jun 24 2013
This sequence is implied in the turbulence solutions of the incompressible Navier-Stokes equations in R^3. a(n) = numbers of realizable vorticity eddies in terms of initial conditions. - Fung Lam, Dec 31 2013
Conjugate sequence to this series is defined by series reversion of x(1+3*x)/(1+x), G.f.: ((x-1)-sqrt(1-10*x+ x^2))/(6*x). Conjugate sequence is the negation of this series except a(0). - Fung Lam, Jan 16 2014
Complete Chebyshev transform is G.f. = 3*F((1-x^2)/(1+x^2)), where F(x) is the g.f. of A107841. Real part of G.f. (= (1 - sqrt(3*x^4-2))/((1+x^2))) generates periodic sequence A056594. In general, for reversion of x*(1-r*x)/(1-x), r>=2, Real part of r*F((1-x^2)/(1+x^2)) (= (1 - sqrt(r*x^4 - r + 1))/(1+x^2)) generates A056594. - Fung Lam, Apr 29 2014
a(n) is the number of small Schröder n-paths with 2 types of up steps (i.e., lattice paths from (0,0) to (2n,0) using steps U1=U2=(1,1), F=(2,0), D=(1,-1), with no F steps on the x-axis). - Yu Hin Au, Dec 07 2019

Fung Lam, Table of n, a(n) for n = 0..1000 [The first 200 terms were computed by Vincenzo Librandi]
J. Abate and W. Whitt, Integer Sequences from Queueing Theory, J. Int. Seq. 13 (2010), 10.5.5, p_n(2).
Yu Hin (Gary) Au, Some Properties and Combinatorial Implications of Weighted Small Schröder Numbers, arXiv:1912.00555 [math.CO], 2019.
Paul Barry, Embedding structures associated with Riordan arrays and moment matrices, arXiv preprint arXiv:1312.0583 [math.CO], 2013.
Z. Chen and H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 [math.CO], 2016; eq. (1.13), a=2, b=3.
Samuele Giraudo, Operads from posets and Koszul duality, arXiv preprint arXiv:1504.04529 [math.CO], 2015.
F. Lam, Integral Invariance and Non-linearity Reduction for Proliferating Vorticity Scales in Fluid Dynamics, arXiv:1311.6395 [physics.flu-dyn], 2013-2014.
F. Lam, Vorticity evolution in a rigid pipe of circular cross-section, arXiv preprint arXiv:1505.07723 [physics.flu-dyn], 2015-2019.

Cf. A001003 (r=2), this sequence (r=3), A131763 (r=4), A131765 (r=5), A131846 (r=6), A131926 (r=7), A131869 (r=8), A131927 (r=9).

seq(simplify((-1)^n*hypergeom([-n, n + 1], [2], 3)), n=0..10); # Georg Fischer, Sep 14 2024 (from Peter Luschny's formula in A131763, with last parameter r=3)

CoefficientList[Series[(1+x-Sqrt[1-10*x+x^2])/(6*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 17 2012 *)

x='x+O('x^66); Vec(serreverse(x*(1-3*x)/(1-x))) \\ Joerg Arndt, May 15 2013

G.f.: (1+x-sqrt(1-10x+x^2))/(6x).
a(n) = (1/(n+1))sum{k=0..n, C(n+1, k)C(2n-k, n)(-1)^k*3^(n-k)}.
a(n) = (1/(n+1))sum{k=0..n, C(n+1, k+1)C(n+k, k)(-1)^(n-k)*3^k}.
a(n) = sum{k=0..n, (1/(k+1))*C(n, k)C(n+k, k)(-1)^(n-k)*3^k}.
a(n) = sum{k=0..n, A088617(n, k)*(-1)^(n-k)*3^k}.
a(n) = Sum_{k>=0} A086810(n, k)*2^k. - Philippe Deléham, May 26 2005
a(n) = (2/3)*A103210(n) for n>0. - Philippe Deléham, Oct 29 2007
G.f.: 1/(1-2x/(1-3x/(1-2x/(1-3x/(1-2x/(1-3x/(1-2x/(1-3x........ (continued fraction). - Paul Barry, Dec 15 2008
From Paul Barry, May 15 2009: (Start)
G.f.: 1/(1-2x/(1-x-2x/(1-x-2x/(1-x-2x/(1-x-2x/(1-... (continued fraction).
G.f.: 1/(1-2x-6x^2/(1-5x-6x^2/(1-5x-6x^2/(1-5x-6x^2/(1-... (continued fraction). (End)
G.f.: 1/(1+x-3x/(1+x-3x/(1+x-3x/(1+x-3x/(1+x-3x/(1+... (continued fraction). - Paul Barry, Mar 18 2011
D-finite with recurrence: (n+1)*a(n) = 5*(2*n-1)*a(n-1) - (n-2)*a(n-2). - Vaclav Kotesovec, Oct 17 2012
a(n) ~ sqrt(12+5*sqrt(6))*(5+2*sqrt(6))^n/(6*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012
a(n+1) is the coefficient of x^(n+1) in 2*sum{j,1,n}((sum{k,1,n}a(k)x^k)^(j+1)), a(1)=1 with offset by 1. - Fung Lam, Dec 31 2013
The series reversion of x*(1 - r*x)/(1 - x) is D-finite with the general recurrence n*a(n) - (2*r-1)*(2*n-3)*a(n-1) + (n-3)*a(n-2) = 0 and with initial values a(1) = 1, a(2) = r-1, a(3) = (2*r-1)*(r-1). This sequence uses r=3, cf. crossrefs. - Georg Fischer, Sep 14 2024

A055151 Triangular array of Motzkin polynomial coefficients.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 6, 2, 1, 10, 10, 1, 15, 30, 5, 1, 21, 70, 35, 1, 28, 140, 140, 14, 1, 36, 252, 420, 126, 1, 45, 420, 1050, 630, 42, 1, 55, 660, 2310, 2310, 462, 1, 66, 990, 4620, 6930, 2772, 132, 1, 78, 1430, 8580, 18018, 12012, 1716, 1, 91, 2002, 15015, 42042

Offset: 0

Michael Somos, Jun 14 2000

T(n,k) = number of Motzkin paths of length n with k up steps. T(n,k)=number of 0-1-2 trees with n edges and k+1 leaves, n>0. (A 0-1-2 tree is an ordered tree in which every vertex has at most two children.) E.g., T(4,1)=6 because we have UDHH, UHDH, UHHD, HHUD, HUHD, HUDH, where U=(1,1), D(1,-1), H(1,0). - Emeric Deutsch, Nov 30 2003
Coefficients in series reversion of x/(1+H*x+U*D*x^2) corresponding to Motzkin paths with H colors for H(1,0), U colors for U(1,1) and D colors for D(1,-1). - Paul Barry, May 16 2005
Eigenvector equals A119020, so that A119020(n) = Sum_{k=0..[n/2]} T(n,k)*A119020(k). - Paul D. Hanna, May 09 2006
Row reverse of A107131. - Peter Bala, May 07 2012
Also equals the number of 231-avoiding permutations of n+1 for which descents(w) = peaks(w) = k, where descents(w) is the number of positions i such that w[i]>w[i+1], and peaks(w) is the number of positions i such that w[i-1]w[i+1]. For example, T(4,1) = 6 because 13245, 12435, 14235, 12354, 12534, 15234 are the only 231-avoiding permutations of 5 elements with descents(w) = peaks(w) = 1. - Kyle Petersen, Aug 02 2013
Apparently, a refined irregular triangle related to this triangle (and A097610) is given in the Alexeev et al. link on p. 12. This entry's triangle is also related through Barry's comment to A125181 and A134264. The diagonals of this entry are the rows of A088617. - Tom Copeland, Jun 17 2015
The row length sequence of this irregular triangle is A008619(n) = 1 + floor(n/2). - Wolfdieter Lang, Aug 24 2015

			The irregular triangle T(n,k) begins:
n\k 0  1   2    3   4  5 ...
0:  1
1:  1
2:  1  1
3:  1  3
4:  1  6   2
5:  1 10  10
6:  1 15  30    5
7:  1 21  70   35
8:  1 28 140  140  14
9:  1 36 252  420 126
10: 1 45 420 1050 630 42
... reformatted. - _Wolfdieter Lang_, Aug 24 2015

Miklos Bona, Handbook of Enumerative Combinatorics, CRC Press (2015), page 617, Corollary 10.8.2
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 4.3.

Alois P. Heinz, Rows n = 0..200, flattened
N. Alexeev, J. Andersen, R. Penner, and P. Zograf, Enumeration of chord diagrams on many intervals and their non-orientable analogs, arXiv:1307.0967 [math.CO], 2013-2014.
Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, and Simonetta Pagnutti, Motzkin Numbers: an Operational Point of View, arXiv:1703.07262 [math.CO], 2017.
Paul Barry, The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1804.05027 [math.CO], 2018.
Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Thomas Grubb and Frederick Rajasekaran, Set Partition Patterns and the Dimension Index, arXiv:2009.00650 [math.CO], 2020. Mentions this sequence.
Paul W. Lapey and Aaron Williams, A Shift Gray Code for Fixed-Content Łukasiewicz Words, Williams College, 2022.
Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
E. Marberg, Actions and identities on set partitions, arXiv preprint arXiv:1107.4173 [math.CO], 2011-2012.
MathOverflow, Motzkin polynomials and enumeration of chord diagrams.
Jean-Christophe Novelli and Jean-Yves Thibon, Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partitions and the Farahat-Higman algebra, arXiv:2106.08257 [math.CO], 2021-2022. See p. 32.
A. Postnikov, V. Reiner, and L. Williams, Faces of generalized permutohedra, arXiv:math/0609184 [math.CO], 2006-2007.
Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 20.
Claude Zeller and Robert Cordery, Light scattering as a Poisson process and first passage probability, arXiv:1906.11131 [cond-mat.stat-mech], 2019.

A107131 (row reversed), A080159 (with trailing zeros), A001006 = row sums, A000108(n) = T(2n, n), A001700(n) = T(2n+1, n), A119020 (eigenvector), A001263 (Narayana numbers), A089627 (gamma vectors of type B associahedra), A101280 (gamma vectors of type A permutohedra).
Cf. A125181, A134264, A088617, A161642, A258820, A003989, A008315, A091156, A011973, A097610, A126120.
Cf. A014531.

b:= proc(x, y) option remember;
      `if`(y>x or y<0, 0, `if`(x=0, 1, expand(
       b(x-1, y) +b(x-1, y+1) +b(x-1, y-1)*t)))
    end:
T:= n-> (p-> seq(coeff(p, t, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, Feb 05 2014

m=(1-x-(1-2x+x^2-4x^2y)^(1/2))/(2x^2 y); Map[Select[#,#>0&]&, CoefficientList[ Series[m,{x,0,15}],{x,y}]]//Grid (* Geoffrey Critzer, Feb 05 2014 *)
p[n_] := Hypergeometric2F1[(1-n)/2, -n/2, 2, 4 x]; Table[CoefficientList[p[n], x], {n, 0, 13}] // Flatten (* Peter Luschny, Jan 23 2018 *)

{T(n, k) = if( k<0 || 2*k>n, 0, n! / ((n-2*k)! * k! * (k+1)!))}

{T(n, k) = if( k<0 || 2*k>n, 0, polcoeff( polcoeff( 2 / (1 - x + sqrt((1 - x)^2 - 4*y*x^2 + x * O(x^n))), n), k))} /* Michael Somos, Feb 14 2006 */

{T(n, k) = n++; if( k<0 || 2*k>n, 0, polcoeff( polcoeff( serreverse( x / (1 + x + y*x^2) + x * O(x^n)), n), k))} /* Michael Somos, Feb 14 2006 */

T(n,k) = n!/((n-2k)! k! (k+1)!) = A007318(n, 2k)*A000108(k). - Henry Bottomley, Jan 31 2003
E.g.f. row polynomials R(n,y): exp(x)*BesselI(1, 2*x*sqrt(y))/(x*sqrt(y)). - Vladeta Jovovic, Aug 20 2003
G.f. row polynomials R(n,y): 2 / (1 - x + sqrt((1 - x)^2 - 4 *y * x^2)).
From Peter Bala, Oct 28 2008: (Start)
The rows of this triangle are the gamma vectors of the n-dimensional (type A) associahedra (Postnikov et al., p. 38). Cf. A089627 and A101280.
The row polynomials R(n,x) = Sum_{k = 0..n} T(n,k)*x^k begin R(0,x) = 1, R(1,x) = 1, R(2,x) = 1 + x, R(3,x) = 1 + 3*x. They are related to the Narayana polynomials N(n,x) := Sum_{k = 1..n} (1/n)*C(n,k)*C(n,k-1)*x^k through x*(1 + x)^n*R(n, x/(1 + x)^2) = N(n+1,x). For example, for n = 3, x*(1 + x)^3*(1 + 3*x/(1 + x)^2) = x + 6*x^2 + 6*x^3 + x^4, the 4th Narayana polynomial.
Recursion relation: (n + 2)*R(n,x) = (2*n + 1)*R(n-1,x) - (n - 1)*(1 - 4*x)*R(n-2,x), R(0,x) = 1, R(1,x) = 1. (End)
G.f.: M(x,y) satisfies: M(x,y)= 1 + x M(x,y) + y*x^2*M(x,y)^2. - Geoffrey Critzer, Feb 05 2014
T(n,k) = A161642(n,k)*A258820(n,k) = (binomial(n,k)/A003989(n+1, k+1))* A258820(n,k). - Tom Copeland, Jun 18 2015
Let T(n,k;q) = n!*(1+k)/((n-2*k)!*(1+k)!^2)*hypergeom([k,2*k-n],[k+2],q) then T(n,k;0) = A055151(n,k), T(n,k;1) = A008315(n,k) and T(n,k;-1) = A091156(n,k). - Peter Luschny, Oct 16 2015
From Tom Copeland, Jan 21 2016: (Start)
Reversed rows of A107131 are rows of this entry, and the diagonals of A107131 are the columns of this entry. The diagonals of this entry are the rows of A088617. The antidiagonals (bottom to top) of A088617 are the rows of this entry.
O.g.f.: [1-x-sqrt[(1-x)^2-4tx^2]]/(2tx^2), from the relation to A107131.
Re-indexed and signed, this triangle gives the row polynomials of the compositional inverse of the shifted o.g.f. for the Fibonacci polynomials of A011973, x / [1-x-tx^2] = x + x^2 + (1+t) x^3 + (1+2t) x^4 + ... . (End)
Row polynomials are P(n,x) = (1 + b.y)^n = Sum{k=0 to n} binomial(n,k) b(k) y^k = y^n M(n,1/y), where b(k) = A126120(k), y = sqrt(x), and M(n,y) are the Motzkin polynomials of A097610. - Tom Copeland, Jan 29 2016
Coefficients of the polynomials p(n,x) = hypergeom([(1-n)/2, -n/2], [2], 4x). - Peter Luschny, Jan 23 2018
Sum_{k=1..floor(n/2)} k * T(n,k) = A014531(n-1) for n>1. - Alois P. Heinz, Mar 29 2020

cp's OEIS Frontend

A006318 Large Schröder numbers (or large Schroeder numbers, or big Schroeder numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Sage

Formula

A033282 Triangle read by rows: T(n, k) is the number of diagonal dissections of a convex n-gon into k+1 regions.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A007564 Shifts left when INVERT transform applied thrice.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

A059231 Number of different lattice paths running from (0,0) to (n,0) using steps from S = {(k,k) or (k,-k): k positive integer} that never go below the x-axis.

Views

A107841 Series reversion of x(1-3x)/(1-x).