A001190 -id:A001190 - cp's OEIS frontend

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

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

A000598 Number of rooted ternary trees with n nodes; number of n-carbon alkyl radicals C(n)H(2n+1) ignoring stereoisomers.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241, 48865, 124906, 321198, 830219, 2156010, 5622109, 14715813, 38649152, 101821927, 269010485, 712566567, 1891993344, 5034704828, 13425117806, 35866550869, 95991365288, 257332864506, 690928354105

Offset: 0

N. J. A. Sloane

Number of unlabeled rooted trees in which each node has out-degree <= 3.
Ignoring stereoisomers means that the children of a node are unordered. They can be permuted in any way and it is still the same tree. See A000625 for the analogous sequence with stereoisomers counted.
In alkanes every carbon has valence exactly 4 and every hydrogen has valence exactly 1. But the trees considered here are just the carbon "skeletons" (with all the hydrogen atoms stripped off) so now each carbon bonds to 1 to 4 other carbons. The out-degree is then <= 3.
Other descriptions of this sequence: quartic planted trees with n nodes; ternary rooted trees with n nodes and height at most 3.
The number of aliphatic amino acids with n carbon atoms in the side chain, and no rings or double bonds, has the same growth as this sequence. - Konrad Gruetzmann, Aug 13 2012

			From _Joerg Arndt_, Feb 25 2017: (Start)
The a(5) = 8 rooted trees with 5 nodes and out-degrees <= 3 are:
:         level sequence    out-degrees (dots for zeros)
:     1:  [ 0 1 2 3 4 ]    [ 1 1 1 1 . ]
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]    [ 1 1 2 . . ]
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]    [ 1 2 1 . . ]
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]    [ 2 1 1 . . ]
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]    [ 1 3 . . . ]
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]    [ 2 2 . . . ]
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]    [ 2 1 . 1 . ]
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]    [ 3 1 . . . ]
:  O--o--o
:  .--o
:  .--o
(End)

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 62 (quoting Cayley, who is wrong).
A. Cayley, On the mathematical theory of isomers, Phil. Mag. vol. 67 (1874), 444-447 (a(6) is wrong).
J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.397.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 529.
Handbook of Combinatorics, North-Holland '95, p. 1963.
Knop, Mueller, Szymanski and Trinajstich, Computer generation of certain classes of molecules.
D. Perry, The number of structural isomers ..., J. Amer. Chem. Soc. 54 (1932), 2918-2920.
G. Polya, Mathematical and Plausible Reasoning, Vol. 1 Prob. 4 pp. 85; 233.
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).

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000 (first 200 terms from N. J. A. Sloane)
Jean-François Alcover, Mathematica program translated from N. J. A. Sloane's Maple program for A000022, A000200, A000598, A000602, A000678.
A. T. Balaban, J. W. Kennedy and L. V. Quintas, The number of alkanes having n carbons and a longest chain of length d, J. Chem. Education, 65 (1988), 304-313.
A. Cayley, On the mathematical theory of isomers, Phil. Mag. vol. 67 (1874), 444-447 (a(6) is wrong). (Annotated scanned copy)
Frederic Chyzak, Enumerating alcohols and other classes of chemical molecules.
Maximilian Fichtner, K. Voigt, and S. Schuster, The tip and hidden part of the iceberg: Proteinogenic and non-proteinogenic aliphatic amino acids, Biochimica et Biophysica Acta (BBA)-General, 2016, Volume 1861, Issue 1, Part A, January 2017, pp. 3258-3269.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 478.
K. Grützmann, S. Böcker, and S. Schuster, Combinatorics of aliphatic amino acids, Naturwissenschaften, Vol. 98, No. 1, 79-86, 2011.
H. R. Henze and C. M. Blair, The number of structurally isomeric alcohols of the methanol series, J. Amer. Chem. Soc., 53 (8) (1931), 3042-3046.
H. R. Henze and C. M. Blair, The number of structurally isomeric alcohols of the methanol series, J. Amer. Chem. Soc., 53 (8) (1931), 3042-3045. (Annotated scanned copy)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Camden A. Parks and James B. Hendrickson, Enumeration of monocyclic and bicyclic carbon skeletons, J. Chem. Inf. Comput. Sci., vol. 31, 334-339 (1991).
D. Perry, The number of structural isomers of certain homologs of methane and methanol, J. Amer. Chem. Soc. 54 (1932), 2918-2920. [Gives a(60) correctly.] (Annotated scanned copy)
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443; Table I, line 2.
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443; Table I, line 2. (Annotated scanned copy)
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [Annotated scanned copy] See p. 20, Eq. (G); p. 27, Eq. 2.1.
Marko Riedel, Chris Grossack, Counting trees with a degree constraint, Math StackExchange.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361. (Annotated scanned copy)
Hugo Schiff, Zur Statistik chemischer Verbindungen, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875. [Annotated scanned copy]
N. J. A. Sloane, Maple program and first 60 terms for A000022, A000200, A000598, A000602, A000678.
N. Trinajstich, Z. Jerievi, J. V. Knop, W. R. Muller and K. Szymanski, Computer Generation of Isomeric Structures, Pure & Appl. Chem., Vol. 55, No. 2, pp. 379-390, 1983.
Wikipedia, Polya's enumeration theorem.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000599, A000600, A000602, A000625, A000628, A000678, A010372, A010373, A086194, A086200, A261340.
Cf. A292553, A292554, A292555, A292556.
Cf. A000081, A001190, A014591, A032305, A295461, A298118, A298120, A298204, A298422, A298426.
Column k=3 of A299038.

N := 45; G000598 := 0: i := 0: while i<(N+1) do G000598 := series(1+z*(G000598^3/6+subs(z=z^2,G000598)*G000598/2+subs(z=z^3,G000598)/3)+O(z^(N+1)),z,N+1): t[ i ] := G000598: i := i+1: od: A000598 := n->coeff(G000598,z,n);
# Another Maple program for g.f. G000598:
G000598 := 1; f := proc(n) global G000598; coeff(series(1+(1/6)*x*(G000598^3+3*G000598*subs(x=x^2,G000598)+2*subs(x=x^3,G000598)),x, n+1),x,n); end; for n from 1 to 50 do G000598 := series(G000598+f(n)*x^n,x,n+1); od; G000598;
spec := [S, {Z=Atom, S=Union(Z, Prod(Z, Set(S, card=3)))}, unlabeled]: [seq(combstruct[count](spec, size=n), n=0..20)];

m = 45; Clear[f]; f[1, x_] := 1+x; f[n_, x_] := f[n, x] = Expand[1+x*(f[n-1, x]^3/6 + f[n-1, x^2]*f[n-1, x]/2 + f[n-1, x^3]/3)][[1 ;; n]]; Do[f[n, x], {n, 2, m}]; CoefficientList[f[m, x], x]
(* second program (after N. J. A. Sloane): *)
m = 45; gf[] = 0; Do[gf[z] = 1 + z*(gf[z]^3/6 + gf[z^2]*gf[z]/2 + gf[z^3]/3) + O[z]^m // Normal, m]; CoefficientList[gf[z], z]  (* Jean-François Alcover, Sep 23 2014, updated Jan 11 2018 *)
b[0, i_, t_, k_] = 1; m = 3; (* m = maximum children *)
b[n_,i_,t_,k_]:= b[n,i,t,k]= If[i<1,0,
  Sum[Binomial[b[i-1, i-1, k, k] + j-1, j]*
  b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
Join[{1},Table[b[n-1, n-1, m, m], {n, 1, 35}]] (* Robert A. Russell, Dec 27 2022 *)

seq(n)={my(g=O(x)); for(n=1, n, g = 1 + x*(g^3/6 + subst(g,x,x^2)*g/2 + subst(g,x,x^3)/3) + O(x^n)); Vec(g)} \\ Andrew Howroyd, May 22 2018

def seq(n):
    B = PolynomialRing(QQ, 't', n+1);t = B.gens()
    R. = B[[]]
    T = sum([t[i] * z^i for i in range(1,n+1)]) + O(z^(n+1))
    lhs, rhs = T, 1 + z/6 * (T(z)^3 + 3*T(z)*T(z^2) + 2*T(z^3))
    I = B.ideal([lhs.coefficients()[i] - rhs.coefficients()[i] for i in range(n)])
    return [I.reduce(t[i]) for i in range(1,n+1)]
seq(33) # Chris Grossack, Mar 31 2025

G.f. A(x) satisfies A(x) = 1 + (1/6)*x*(A(x)^3 + 3*A(x)*A(x^2) + 2*A(x^3)).

a(n) ~ c * d^n / n^(3/2), where d = 1/A261340 = 2.8154600331761507465266167782426995425365065396907..., c = 0.517875906458893536993162356992854345458168348098... . - Vaclav Kotesovec, Aug 15 2015

Additional comments from Steve Strand (snstrand(AT)comcast.net), Aug 20 2003

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 18, 14, 5, 1, 0, 1, 12, 35, 39, 21, 6, 1, 0, 1, 16, 62, 97, 72, 30, 7, 1, 0, 1, 20, 103, 212, 214, 120, 40, 8, 1, 0, 1, 25, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0

Offset: 1

Christian G. Bower, May 09 2000

Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014

			From _Joerg Arndt_, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1    0
03: 1    1    0
04: 1    2    1    0
05: 1    4    3    1    0
06: 1    6    8    4    1    0
07: 1    9   18   14    5    1    0
08: 1   12   35   39   21    6    1    0
09: 1   16   62   97   72   30    7    1    0
10: 1   20  103  212  214  120   40    8    1    0
11: 1   25  161  429  563  416  185   52    9    1    0
12: 1   30  241  804 1344 1268  732  270   65   10    1    0
13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 2 3 4 ]   1
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]   2
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]   2
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]   2
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]   3
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]   3
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]   2
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]   3
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]   4
:  O--o
:  .--o
:  .--o
:  .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).

F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Row sums give A000081.
Columns 2 through 12: A002620(n-1), A055278-A055287.
Cf. A055288, A055289, A055290.
Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* Gus Wiseman, Mar 19 2018 *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

A126120 Catalan numbers (A000108) interpolated with 0's.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862, 0, 16796, 0, 58786, 0, 208012, 0, 742900, 0, 2674440, 0, 9694845, 0, 35357670, 0, 129644790, 0, 477638700, 0, 1767263190, 0, 6564120420, 0, 24466267020, 0, 91482563640, 0, 343059613650, 0

Offset: 0

Philippe Deléham, Mar 06 2007

Inverse binomial transform of A001006.
The Hankel transform of this sequence gives A000012 = [1,1,1,1,1,...].
Counts returning walks (excursions) of length n on a 1-d integer lattice with step set {+1,-1} which stay in the chamber x >= 0. - Andrew V. Sutherland, Feb 29 2008
Moment sequence of the trace of a random matrix in G=USp(2)=SU(2). If X=tr(A) is a random variable (A distributed according to the Haar measure on G) then a(n) = E[X^n]. - Andrew V. Sutherland, Feb 29 2008
Essentially the same as A097331. - R. J. Mathar, Jun 15 2008
Number of distinct proper binary trees with n nodes. - Chris R. Sims (chris.r.sims(AT)gmail.com), Jun 30 2010
-a(n-1), with a(-1):=0, n>=0, is the Z-sequence for the Riordan array A049310 (Chebyshev S). For the definition see that triangle. - Wolfdieter Lang, Nov 04 2011
See A180874 (also A238390 and A097610) and A263916 for relations to the general Bell A036040, cycle index A036039, and cumulant expansion polynomials A127671 through the Faber polynomials. - Tom Copeland, Jan 26 2016
A signed version is generated by evaluating polynomials in A126216 that are essentially the face polynomials of the associahedra. This entry's sequence is related to an inversion relation on p. 34 of Mizera, related to Feynman diagrams. - Tom Copeland, Dec 09 2019

			G.f. = 1 + x^2 + 2*x^4 + 5*x^6 + 14*x^8 + 42*x^10 + 132*x^12 + 429*x^14 + ...
From _Gus Wiseman_, Nov 14 2022: (Start)
The a(0) = 1 through a(8) = 14 ordered binary rooted trees with n + 1 nodes (ranked by A358375):
  o  .  (oo)  .  ((oo)o)  .  (((oo)o)o)  .  ((((oo)o)o)o)
                 (o(oo))     ((o(oo))o)     (((o(oo))o)o)
                             ((oo)(oo))     (((oo)(oo))o)
                             (o((oo)o))     (((oo)o)(oo))
                             (o(o(oo)))     ((o((oo)o))o)
                                            ((o(o(oo)))o)
                                            ((o(oo))(oo))
                                            ((oo)((oo)o))
                                            ((oo)(o(oo)))
                                            (o(((oo)o)o))
                                            (o((o(oo))o))
                                            (o((oo)(oo)))
                                            (o(o((oo)o)))
                                            (o(o(o(oo))))
(End)

Jerome Spanier and Keith B. Oldham, "Atlas of Functions", Ch. 49, Hemisphere Publishing Corp., 1987.

G. C. Greubel, Table of n, a(n) for n = 0..1000
V. E. Adler, Set partitions and integrable hierarchies, arXiv:1510.02900 [nlin.SI], 2015.
Martin Aigner, Catalan and other numbers: a recurrent theme, in Algebraic Combinatorics and Computer Science, a Tribute to Gian-Carlo Rota, pp.347-390, Springer, 2001.
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv:1609.06473 [math.CO], 2016.
Radica Bojicic, Marko D. Petkovic and Paul Barry, Hankel transform of a sequence obtained by series reversion II-aerating transforms, arXiv:1112.1656 [math.CO], 2011.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Francesc Fite, Kiran S. Kedlaya, Victor Rotger and Andrew V. Sutherland, Sato-Tate distributions and Galois endomorphism modules in genus 2, arXiv:1110.6638 [math.NT], 2011.
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.
Kiran S. Kedlaya and Andrew V. Sutherland, HyperellipticCurves, L-Polynomials, and Random Matrices. In: Arithmetic, Geometry, Cryptography, and Coding Theory: International Conference, November 5-9, 2007, CIRM, Marseilles, France. (Contemporary Mathematics; v.487)
S. Mizera, Combinatorics and Topology of Kawai-Lewellen-Tye Relations, arXiv:1706.08527 [hep-th], 2017.
Eric Rowland, Pattern avoidance in binary trees, J. Comb. Theory A 117 (6) (2010) 741-758, Sec. 3.1.
Yidong Sun and Fei Ma, Minors of a Class of Riordan Arrays Related to Weighted Partial Motzkin Paths, arXiv:1305.2015 [math.CO], 2013.
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. 99.
Y. Wang and Z.-H. Zhang, Combinatorics of Generalized Motzkin Numbers, J. Int. Seq. 18 (2015) # 15.2.4.

Cf. A000108, A036039, A036040, A097610, A127671, A180874, A238390, A263916.
Cf. A126216.
The unordered version is A001190, ranked by A111299.
These trees (ordered binary rooted) are ranked by A358375.
Cf. A000081, A001263, A005043, A032027, A063895, A245824.

&cat [[Catalan(n), 0]: n in [0..30]]; // Vincenzo Librandi, Jul 28 2016

with(combstruct): grammar := { BB = Sequence(Prod(a,BB,b)), a = Atom, b = Atom }: seq(count([BB,grammar], size=n),n=0..47); # Zerinvary Lajos, Apr 25 2007
BB := {E=Prod(Z,Z), S=Union(Epsilon,Prod(S,S,E))}: ZL:=[S,BB,unlabeled]: seq(count(ZL, size=n), n=0..45); # Zerinvary Lajos, Apr 22 2007
BB := [T,{T=Prod(Z,Z,Z,F,F), F=Sequence(B), B=Prod(F,Z,Z)}, unlabeled]: seq(count(BB, size=n+1), n=0..45); # valid for n> 0. # Zerinvary Lajos, Apr 22 2007
seq(n!*coeff(series(hypergeom([],[2],x^2),x,n+2),x,n),n=0..45); # Peter Luschny, Jan 31 2015
# Using function CompInv from A357588.
CompInv(48, n -> ifelse(irem(n, 2) = 0, 0, (-1)^iquo(n-1, 2))); # Peter Luschny, Oct 07 2022

a[n_?EvenQ] := CatalanNumber[n/2]; a[n_] = 0; Table[a[n], {n, 0, 45}] (* Jean-François Alcover, Sep 10 2012 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ BesselI[ 1, 2 x] / x, {x, 0, n}]]; (* Michael Somos, Mar 19 2014 *)
bot[n_]:=If[n==1,{{}},Join@@Table[Tuples[bot/@c],{c,Table[{k,n-k-1},{k,n-1}]}]];
Table[Length[bot[n]],{n,10}] (* Gus Wiseman, Nov 14 2022 *)
Riffle[CatalanNumber[Range[0,50]],0,{2,-1,2}] (* Harvey P. Dale, May 28 2024 *)

from math import comb
def A126120(n): return 0 if n&1 else comb(n,m:=n>>1)//(m+1) # Chai Wah Wu, Apr 22 2024

def A126120_list(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 2; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h,0,-1) : D[k] -= D[k-1]
            h += 1; R.append(abs(D[1]))
        else :
            for k in range(1,h, 1) : D[k] += D[k+1]
        b = not b
    return R
A126120_list(46) # Peter Luschny, Jun 03 2012

a(2*n) = A000108(n), a(2*n+1) = 0.
a(n) = A053121(n,0).
(1/Pi) Integral_{0 .. Pi} (2*cos(x))^n *2*sin^2(x) dx. - Andrew V. Sutherland, Feb 29 2008
G.f.: (1 - sqrt(1 - 4*x^2)) / (2*x^2) = 1/(1-x^2/(1-x^2/(1-x^2/(1-x^2/(1-... (continued fraction). - Philippe Deléham, Nov 24 2009
G.f. A(x) satisfies A(x) = 1 + x^2*A(x)^2. - Vladimir Kruchinin, Feb 18 2011
E.g.f.: I_1(2x)/x Where I_n(x) is the modified Bessel function. - Benjamin Phillabaum, Mar 07 2011
Apart from the first term the e.g.f. is given by x*HyperGeom([1/2],[3/2,2], x^2). - Benjamin Phillabaum, Mar 07 2011
a(n) = Integral_{x=-2..2} x^n*sqrt((2-x)*(2+x))/(2*Pi) dx. - Peter Luschny, Sep 11 2011
E.g.f.: E(0)/(1-x) where E(k) = 1-x/(1-x/(x-(k+1)*(k+2)/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, Apr 05 2013
G.f.: 3/2- sqrt(1-4*x^2)/2 = 1/x^2 + R(0)/x^2, where R(k) = 2*k-1 - x^2*(2*k-1)*(2*k+1)/R(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 28 2013 (warning: this is not the g.f. of this sequence, R. J. Mathar, Sep 23 2021)
G.f.: 1/Q(0), where Q(k) = 2*k+1 + x^2*(1-4*(k+1)^2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Jan 09 2014
a(n) = n!*[x^n]hypergeom([],[2],x^2). - Peter Luschny, Jan 31 2015
a(n) = 2^n*hypergeom([3/2,-n],[3],2). - Peter Luschny, Feb 03 2015
a(n) = ((-1)^n+1)*2^(2*floor(n/2)-1)*Gamma(floor(n/2)+1/2)/(sqrt(Pi)* Gamma(floor(n/2)+2)). - Ilya Gutkovskiy, Jul 23 2016
D-finite with recurrence (n+2)*a(n) +4*(-n+1)*a(n-2)=0. - R. J. Mathar, Mar 21 2021
From Peter Bala, Feb 03 2024: (Start)
a(n) = 2^n * Sum_{k = 0..n} (-2)^(-k)*binomial(n, k)*Catalan(k+1).
G.f.: 1/(1 + 2*x) * c(x/(1 + 2*x))^2 = 1/(1 - 2*x) * c(-x/(1 - 2*x))^2 = c(x^2), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. (End)

An erroneous comment removed by Tom Copeland, Jul 23 2016

A298422 Number of rooted trees with n nodes in which all positive outdegrees are the same.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 2, 20, 2, 26, 12, 53, 2, 120, 2, 223, 43, 454, 2, 1100, 11, 2182, 215, 4902, 2, 11446, 2, 24744, 1242, 56014, 58, 131258, 2, 293550, 7643, 676928, 2, 1582686, 2, 3627780, 49155, 8436382, 2, 19809464, 50, 46027323, 321202

Offset: 1

Gus Wiseman, Jan 19 2018

nonn

Row sums of A298426.

			The a(9) = 6 trees: ((((((((o)))))))), (o(o(o(oo)))), (o((oo)(oo))), ((oo)(o(oo))), (ooo(oooo)), (oooooooo).

Alois P. Heinz, Table of n, a(n) for n = 1..200

Cf. A000005, A000081, A000598, A001190, A001678, A003238, A004111, A008864, A032305, A067538, A111299, A124343, A143773, A289078, A289079, A295461, A298118, A298204, A298423, A298424, A298426.

srut[n_]:=srut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[srut/@c]]]/@Select[IntegerPartitions[n-1],Function[ptn,And@@(Divisible[#-1,Length[ptn]]&/@ptn)]],SameQ@@Length/@Cases[#,{},{0,Infinity}]&]];
Table[srut[n]//Length,{n,20}]

a(n) = 2 <=> n in {A008864}. - Alois P. Heinz, Jan 20 2018

a(44)-a(52) from Alois P. Heinz, Jan 20 2018

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

Original entry on oeis.org

4, 14, 49, 86, 301, 454, 886, 1589, 1849, 3101, 3986, 6418, 9761, 13766, 13951, 19049, 22463, 26798, 31754, 48181, 51529, 57026, 75266, 85699, 93793, 100561, 111139, 128074, 137987, 196249, 199591, 203878, 263431, 295969, 298154, 302426, 426058, 448259, 452411

Offset: 1

Keith Briggs, Nov 02 2005

nonn

This sequence should probably start with 1. Then a number k is in the sequence iff k = 1 or k = prime(x) * prime(y) with x and y already in the sequence. - Gus Wiseman, May 04 2021

			From _Gus Wiseman_, May 04 2021: (Start)
The sequence of trees (starting with 1) begins:
     1: o
     4: (oo)
    14: (o(oo))
    49: ((oo)(oo))
    86: (o(o(oo)))
   301: ((oo)(o(oo)))
   454: (o((oo)(oo)))
   886: (o(o(o(oo))))
  1589: ((oo)((oo)(oo)))
  1849: ((o(oo))(o(oo)))
  3101: ((oo)(o(o(oo))))
  3986: (o((oo)(o(oo))))
  6418: (o(o((oo)(oo))))
  9761: ((o(oo))((oo)(oo)))
(End)

Kevin Ryde, Table of n, a(n) for n = 1..5000 (terms 1..186 from Charles R Greathouse IV)
Keith Briggs, Matula numbers and rooted trees
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Kevin Ryde, PARI/GP Code
Index entries for sequences related to Matula-Goebel numbers

Cf. A245824 (by number of leaves).
Cf. A005517, A005518, A061773, A245824.
These trees are counted by 2*A001190 - 1.
The semi-binary version is A292050 (counted by A001190).
The semi-identity case is A339193 (counted by A063895).
A000081 counts unlabeled rooted trees with n nodes.
A007097 ranks rooted chains.
A276625 ranks identity trees, counted by A004111.
A306202 ranks semi-identity trees, counted by A306200.
A306203 ranks balanced semi-identity trees, counted by A306201.
A331965 ranks lone-child avoiding semi-identity trees, counted by A331966.
Cf. A036656, A061775, A196050, A291636, A320230, A331935, A331965.

nn=20000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
binQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]===2,And@@binQ/@m]]];
Select[Range[2,nn],binQ] (* Gus Wiseman, Aug 28 2017 *)

i(n)=n==2 || is(primepi(n))
is(n)=if(n<14,return(n==4)); my(f=factor(n),t=#f[,1]); if(t>1, t==2 && f[1,2]==1 && f[2,2]==1 && i(f[1,1]) && i(f[2,1]), f[1,2]==2 && i(f[1,1])) \\ Charles R Greathouse IV, Mar 29 2013

list(lim)=my(v=List(), t); forprime(p=2, sqrt(lim), t=p; forprime(q=p, lim\t, if(i(p)&&i(q), listput(v, t*q)))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Mar 29 2013

PARI
```
\\ Also see links.
```

The Matula tree of k is defined as follows:
matula(k):
    create a node labeled k
    for each prime factor m of k:
       add the subtree matula(prime(m)), by an edge labeled m
    return the node

Definition corrected by Charles R Greathouse IV, Mar 29 2013

a(27)-a(39) from Charles R Greathouse IV, Mar 29 2013

A000992 "Half-Catalan numbers": a(n) = Sum_{k=1..floor(n/2)} a(k)*a(n-k) with a(1) = 1.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 24, 47, 103, 214, 481, 1030, 2337, 5131, 11813, 26329, 60958, 137821, 321690, 734428, 1721998, 3966556, 9352353, 21683445, 51296030, 119663812, 284198136, 666132304, 1586230523, 3734594241, 8919845275, 21075282588, 50441436842

Offset: 1

N. J. A. Sloane

From David Callan, Nov 02 2006: (Start)
a(n) = number of (unlabeled, rooted) ordered trees on n-1 vertices in which all outdegrees are <= 2 and, for each vertex of outdegree 2, the sizes of its two subtrees are weakly increasing left to right (n >= 2). The number b(n) of such trees on n vertices satisfies the recurrence b[1]=1; b[n_]/;n>=2 := b[n] = b[n-1] + Sum_{i=1..floor((n-1)/2)} b[i]b[n-1-i], the first term counting trees whose root has outdegree 1 and the sum counting trees whose root has outdegree 2 by size of the left subtree. This recurrence generates b(n) = a(n+1), n >= 1. For example, the a(5)=3 such trees are:
.|....|...../\..
.|.../.\.....|..
.|.............. (End)
From R. J. Mathar, Mar 27 2009: (Start)
The connection with the Rayleigh polynomials Phi(2n,x) of A158616 is that Phi(2n,x) = Sum_{i=1..a(n)} 2^(n_i) Product_{j=2..n-1} (x+j)^(n_ij), as described by Kishore.
So a(n) counts the terms in the representation of the polynomial Phi(2n,x) as a sum over these "base" polynomials.
For example, Phi(12,x) = 2^4*(x+2)^2*(x+3) + 2^2*(x+2)*(x+3)^2 + 2^3*(x+2)*(x+3)*(x+4) + 2^3*(x+2)*(x+3)*(x+5) + 2^2*(x+2)*(x+4)*(x+5) + 2*(x+3)^2*(x+5) has a(6)=6 terms. (End)
From Wolfdieter Lang, Jan 06 2012: (Start)
The o.g.f. G(x) := Sum_{n>=0} a(n)*x^n, with a(0)=0, satisfies the relation (G(x))^2 - 2*G(x) + G2(x^2) + 2*x = 0, with the o.g.f. G2(x) := Sum_{n>=0} a(n)^2*x^n of the squares. This can be proved from the connection to the half-convolution of the sequence with itself (for this notion see a comment on A201204, where also the rule for the o.g.f. is given). (End)
Limit_{n->infinity} a(n)^(1/n) = 2.49086422... . - Vaclav Kotesovec, Oct 15 2014
This sequence diverges from A001190 for n >= 8. A001190(n) gives the number of unlabeled binary trees with n leaves and n-1 internal nodes. - Andrew Howroyd, Apr 01 2023

			G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 24*x^8 + 47*x^9 + ...

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

Vaclav Kotesovec, Table of n, a(n) for n = 1..2500 (first 200 terms from T. D. Noe)
E. Bohl, P. Lancaster, Implementation of a Markov model for phylogenetic trees, J. Theor. Biol. 239 (3) (2006) 324-333.
J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975.
David S. Evans, Stars of Higher Multiplicity, Quarterly Journal of the Royal Astronomical Society, Vol. 9 (1968), pp. 388-400.
T. Feil, K.Hutson, R. J. Kretchmar, Tree traversals and permutations, Congr. Numer. 175 (2005) 201-221 (mentions the sequence only in the references, not in the text).
N. Kishore, A structure of the Rayleigh polynomial, Duke Math. J., 31 (1964), 513-518.

Compare recurrence for A000108 (the Catalan numbers).
A093637 counts above trees without the restriction that all outdegrees are <= 2.
Cf. A001190, A124973, A248748.

a000992 n = a000992_list !! (n-1)
a000992_list = 1 : f 1 0 [1] where
   f x y zs = z : f (x + y) (1 - y) (z:zs) where
     z = sum $ take x $ zipWith (*) zs $ reverse zs
-- Reinhard Zumkeller, Dec 21 2011

al := 1/2; M1 := 30; a[ 0 ] := 1; for n from 0 to M1 do n0 := floor(al*n);
a[ n+1 ] := sum( a[ i ]*a[ n-i ], i=0..n0); i := 'i'; od: [ seq(a[ j ],j=0..M1) ];
# second Maple program:
a:= proc(n) option remember; `if`(n=1, 1,
      add(a(j)*a(n-j), j=1..n/2))
    end:
seq(a(n), n=1..42);  # Alois P. Heinz, Sep 22 2019

a[1]=1; a[n_]:=a[n]=Sum[a[k] a[n-k],{k,1,Floor[n/2]}]; Table[a[n],{n,1,32}] (* Jean-François Alcover, Mar 21 2011 *)

A000992_list(n)={for(i=4,#n=vector(n,i,1),n[i]=sum(j=1,i\2,n[j]*n[i-j]));n}  \\ M. F. Hasler, Dec 20 2011

from functools import lru_cache
@lru_cache(maxsize=None)
def A000992(n): return sum(A000992(k)*A000992(n-k) for k in range(1,(n>>1)+1)) if n>1 else 1 # Chai Wah Wu, Nov 04 2024

A040039 First differences of A033485; also A033485 with terms repeated.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, 13, 13, 18, 18, 23, 23, 30, 30, 37, 37, 47, 47, 57, 57, 70, 70, 83, 83, 101, 101, 119, 119, 142, 142, 165, 165, 195, 195, 225, 225, 262, 262, 299, 299, 346, 346, 393, 393, 450, 450, 507, 507, 577, 577, 647, 647, 730, 730, 813, 813, 914, 914, 1015, 1015, 1134, 1134, 1253, 1253, 1395, 1395

Offset: 0

N. J. A. Sloane and J. H. Conway

Apparently a(n) = number of partitions (p_1, p_2, ..., p_k) of n+1, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i > p_{i+1}+...+p_k. - John McKay (mac(AT)mathstat.concordia.ca), Mar 06 2009
Comment from John McKay confirmed in paper by Bessenrodt, Olsson, and Sellers. Such partitions are called "strongly decreasing" partitions in the paper, see the function s(n) therein.
Also the number of unlabeled binary rooted trees with 2*n + 3 nodes in which the two branches directly under any given non-leaf node are either equal or at least one of them is a leaf. - Gus Wiseman, Oct 08 2018
From Gus Wiseman, Apr 06 2021: (Start)
This sequence counts both of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n + 1 in which all adjacent elements have quotients < 1/2. For example, the a(0) = 1 through a(8) = 7 subsets are:
  {1}  {2}  {3}    {4}    {5}    {6}    {7}      {8}      {9}
            {1,3}  {1,4}  {1,5}  {1,6}  {1,7}    {1,8}    {1,9}
                          {2,5}  {2,6}  {2,7}    {2,8}    {2,9}
                                        {3,7}    {3,8}    {3,9}
                                        {1,3,7}  {1,3,8}  {4,9}
                                                          {1,3,9}
                                                          {1,4,9}
2. Sets of distinct positive integers with maximum n + 1 whose first differences are term-wise greater than their decapitation (remove the maximum). For example, the set q = {1,4,9} has first differences (3,5), which are greater than (1,4), so q is counted under a(8). On the other hand, r = {1,5,9} has first differences (4,4), which are not greater than (1,5), so r is not counted under a(8).
Also the number of partitions of n + 1 into powers of 2 covering an initial interval of powers of 2. For example, the a(0) = 1 through a(8) = 7 partitions are:
  1  11  21   211   221    2211    421      4211      4221
         111  1111  2111   21111   2221     22211     22221
                    11111  111111  22111    221111    42111
                                   211111   2111111   222111
                                   1111111  11111111  2211111
                                                      21111111
                                                      111111111
(End)

			From _Joerg Arndt_, Dec 17 2012: (Start)
The a(19-1)=30 strongly decreasing partitions of 19 are (in lexicographic order)
[ 1]    [ 10 5 3 1 ]
[ 2]    [ 10 5 4 ]
[ 3]    [ 10 6 2 1 ]
[ 4]    [ 10 6 3 ]
[ 5]    [ 10 7 2 ]
[ 6]    [ 10 8 1 ]
[ 7]    [ 10 9 ]
[ 8]    [ 11 5 2 1 ]
[ 9]    [ 11 5 3 ]
[10]    [ 11 6 2 ]
[11]    [ 11 7 1 ]
[12]    [ 11 8 ]
[13]    [ 12 4 2 1 ]
[14]    [ 12 4 3 ]
[15]    [ 12 5 2 ]
[16]    [ 12 6 1 ]
[17]    [ 12 7 ]
[18]    [ 13 4 2 ]
[19]    [ 13 5 1 ]
[20]    [ 13 6 ]
[21]    [ 14 3 2 ]
[22]    [ 14 4 1 ]
[23]    [ 14 5 ]
[24]    [ 15 3 1 ]
[25]    [ 15 4 ]
[26]    [ 16 2 1 ]
[27]    [ 16 3 ]
[28]    [ 17 2 ]
[29]    [ 18 1 ]
[30]    [ 19 ]
The a(20-1)=30 strongly decreasing partitions of 20 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _Gus Wiseman_, Oct 08 2018: (Start)
The a(-1) = 1 through a(4) = 3 semichiral binary rooted trees:
  o  (oo)  (o(oo))  ((oo)(oo))  (o((oo)(oo)))  ((o(oo))(o(oo)))
                    (o(o(oo)))  (o(o(o(oo))))  (o(o((oo)(oo))))
                                               (o(o(o(o(oo)))))
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..500 from Joerg Arndt)
Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013

Cf. A000123.
Cf. A088567, A089054.
Cf. A001190, A003238, A111299, A292050, A317712, A320222, A320230, A320271.
The equal case is A001511.
The reflected version is A045690.
The unequal (anti-run) version is A045691.
A000929 counts partitions with all adjacent parts x >= 2y.
A002843 counts compositions with all adjacent parts x <= 2y.
A018819 counts partitions into powers of 2.
A154402 counts partitions with all adjacent parts x = 2y.
A274199 counts compositions with all adjacent parts x < 2y.
A342094 counts partitions with all adjacent parts x <= 2y (strict: A342095).
A342096 counts partitions without adjacent x >= 2y (strict: A342097).
A342098 counts partitions with all adjacent parts x > 2y.
A342337 counts partitions with all adjacent parts x = y or x = 2y.
Cf. A000009, A003114, A003242, A224957, A342191, A342330.

# For example, the five partitions of 4, written in nonincreasing order, are
# [1,1,1,1], [2,1,1], [2,2], [3,1], [4].
# Only the last two satisfy the condition, and a(3)=2.
# The Maple program below verifies this for small values of n.
with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
#while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od;
# John McKay

T[n_, m_] := T[n, m] = Sum[Binomial[n-2k-1, n-2k-m] Sum[Binomial[m, i] T[k, i], {i, 1, k}], {k, 0, (n-m)/2}] + Binomial[n-1, n-m];
a[n_] := T[n+1, 1];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[#[[i-1]]/#[[i]]<1/2,{i,2,Length[#]}]&]],{n,15}] (* Gus Wiseman, Apr 06 2021 *)

T(n,m):=sum(binomial(n-2*k-1,n-2*k-m)*sum(binomial(m,i)*T(k,i),i,1,k),k,0,(n-m)/2)+binomial(n-1,n-m);
makelist(T(n+1,1),n,0,40); /* Vladimir Kruchinin, Mar 19 2015 */

/* compute as "A033485 with terms repeated" */
b(n) = if(n<2, 1, b(floor(n/2))+b(n-1));  /* A033485 */
a(n) = b(n\2+1); /* note different offsets */
for(n=0,99, print1(a(n),", ")); /* Joerg Arndt, Jan 21 2011 */

from itertools import islice
from collections import deque
def A040039_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (1, 1, 2, 2)
    while True:
        a += b
        yield from (a, a)
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A040039_list = list(islice(A040039_gen(),40)) # Chai Wah Wu, Jun 07 2022

Let T(x) be the g.f, then T(x) = 1 + x/(1-x)*T(x^2) = 1 + x/(1-x) * ( 1 + x^2/(1-x^2) * ( 1 + x^4/(1-x^4) * ( 1 + x^8/(1-x^8) *(...) ))). [Joerg Arndt, May 11 2010]
From Joerg Arndt, Oct 02 2013: (Start)
G.f.: sum(k>=1, x^(2^k-1) / prod(j=0..k-1, 1-x^(2^k) ) ) [Bessenrodt/Olsson/Sellers].
G.f.: 1/(2*x^2) * ( 1/prod(k>=0, 1 - x^(2^k) ) - (1 + x) ).
a(n) = 1/2 * A018819(n+2).
(End)
a(n) = T(n+1,1), where T(n,m)=sum(k..0,(n-m)/2, binomial(n-2*k-1,n-2*k-m)*sum(i=1..k, binomial(m,i)*T(k,i)))+binomial(n-1,n-m). - Vladimir Kruchinin, Mar 19 2015
Using offset 1: a(1) = 1; a(n even) = a(n-1); a(n odd) = a(n-1) + a((n-1)/2). - Gus Wiseman, Oct 08 2018

A317712 Number of uniform rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 35, 72, 169, 388, 934, 2234, 5508, 13557, 33883, 85017, 215091, 546496, 1396524, 3582383, 9228470, 23852918, 61857180, 160871716, 419516462, 1096671326, 2873403980, 7544428973, 19847520789, 52308750878, 138095728065, 365153263313, 966978876376

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

An unlabeled rooted tree is uniform if the multiplicities of the branches directly under any given node are all equal.

			The a(5) = 8 uniform rooted trees:
  ((((o))))
  (((oo)))
  ((o(o)))
  ((ooo))
  (o((o)))
  (o(oo))
  ((o)(o))
  (oooo)

Vaclav Kotesovec, Table of n, a(n) for n = 1..2250 (terms 1..200 from Andrew Howroyd)
Gus Wiseman, All 72 uniform rooted trees with 8 nodes.

Cf. A000081, A001190, A004111, A072774, A301700, A317588.

Cf. A317705, A317707, A317708, A317709, A317710, A317711, A317717, A317718.

purt[n_]:=Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],SameQ@@Length/@Split[#]&],{ptn,IntegerPartitions[n-1]}];
Table[Length[purt[n]],{n,10}]

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
seq(n)={my(v=[1]); for(n=2, n, my(t=WeighT(v)); v=concat(v, sumdiv(n-1, d, t[d]))); v} \\ Andrew Howroyd, Aug 28 2018

a(n) ~ c * d^n / n^(3/2), where d = 2.774067238136373782458114960391469140405537808253... and c = 0.43338208953061974806801546569720246018271214... - Vaclav Kotesovec, Sep 07 2019

Term a(21) and beyond from Andrew Howroyd, Aug 28 2018

A063895 Start with x, xy; then concatenate each word in turn with all preceding words, getting x xy xxy xxxy xyxxy xxxxy xyxxxy xxyxxxy ...; sequence gives number of words of length n. Also binary trees by degree: x (x,y) (x,(x,y)) (x,(x,(x,y))) ((x,y),(x,(x,y)))...

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 11, 22, 43, 88, 179, 372, 774, 1631, 3448, 7347, 15713, 33791, 72923, 158021, 343495, 749102, 1638103, 3591724, 7893802, 17387931, 38379200, 84875596, 188036830, 417284181, 927469845, 2064465341, 4601670625, 10270463565, 22950838755

Offset: 1

Claude Lenormand (claude.lenormand(AT)free.fr), Aug 29 2001

Also binary rooted identity trees (those with no symmetries, cf. A004111).
From Gus Wiseman, May 04 2021: (Start)
Also the number of unlabeled binary rooted semi-identity trees with 2*n - 1 nodes. In a semi-identity tree, only the non-leaf branches directly under any given vertex are required to be distinct. Alternatively, an unlabeled rooted tree is a semi-identity tree iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees. For example, the a(3) = 1 through a(6) = 6 trees are:
  (o(oo))  (o(o(oo)))  ((oo)(o(oo)))  ((oo)(o(o(oo))))  ((o(oo))(o(o(oo))))
                       (o(o(o(oo))))  (o((oo)(o(oo))))  ((oo)((oo)(o(oo))))
                                      (o(o(o(o(oo)))))  ((oo)(o(o(o(oo)))))
                                                        (o((oo)(o(o(oo)))))
                                                        (o(o((oo)(o(oo)))))
                                                        (o(o(o(o(o(oo))))))
The a(8) = 11 trees with 15 nodes:
  ((o(oo))((oo)(o(oo))))
  ((o(oo))(o(o(o(oo)))))
  ((oo)((oo)(o(o(oo)))))
  ((oo)(o((oo)(o(oo)))))
  ((oo)(o(o(o(o(oo))))))
  (o((o(oo))(o(o(oo)))))
  (o((oo)((oo)(o(oo)))))
  (o((oo)(o(o(o(oo))))))
  (o(o((oo)(o(o(oo))))))
  (o(o(o((oo)(o(oo))))))
  (o(o(o(o(o(o(oo)))))))
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for sequences related to rooted trees

Cf. A063894, A036774.
The non-semi-identity version is 2*A001190(n)-1, ranked by A111299.
Semi-binary trees are also counted by A001190, but ranked by A292050.
The not necessarily binary version is A306200, ranked A306202.
The Matula-Goebel numbers of these trees are A339193.
The plane tree version is A343663.
A000081 counts unlabeled rooted trees with n nodes.
A004111 counts identity trees, ranked by A276625.
A306201 counts balanced semi-identity trees, ranked by A306203.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
Cf. A001678, A331934, A331963, A331964.

a:= proc(n) option remember; `if`(n<3, n*(3-n)/2, add(a(i)*a(n-i),
      i=1..(n-1)/2)+`if`(irem(n, 2, 'r')=0, (p->(p-1)*p/2)(a(r)), 0))
    end:
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 02 2013

a[n_] := a[n] = If[n<3, n*(3-n)/2, Sum[a[i]*a[n-i], {i, 1, (n-1)/2}]+If[{q, r} = QuotientRemainder[n, 2]; r == 0, (a[q]-1)*a[q]/2, 0]]; Table[a[n], {n, 1, 36}] (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)
ursiq[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursiq/@ptn]],#=={}||#=={{},{}}||Length[#]==2&&(UnsameQ@@DeleteCases[#,{}])&],{ptn,IntegerPartitions[n-1]}];Table[Length[ursiq[n]],{n,1,15,2}] (* Gus Wiseman, May 04 2021 *)

{a(n)=local(A, m); if(n<1, 0, m=1; A=O(x); while( m<=n, m*=2; A=1-sqrt(1-2*x-2*x^2+subst(A, x, x^2))); polcoeff(A, n))}

a(n) = (sum a(i)*a(j), i+j=n, i2. a(1)=a(2)=1.
G.f. A(x) = 1-sqrt(1-2x-2x^2+A(x^2)) satisfies x+x^2-A(x)+(A(x)^2-A(x^2))/2=0, A(0)=0. - Michael Somos, Sep 06 2003
a(n) ~ c * d^n / n^(3/2), where d = 2.33141659246516873904600076533362924695..., c = 0.2873051160895040470174351963... . - Vaclav Kotesovec, Sep 11 2014

Additional comments and g.f. from Christian G. Bower, Nov 29 2001

cp's OEIS Frontend

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

A000598 Number of rooted ternary trees with n nodes; number of n-carbon alkyl radicals C(n)H(2n+1) ignoring stereoisomers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A126120 Catalan numbers (A000108) interpolated with 0's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

Sage

Formula

Extensions

A298422 Number of rooted trees with n nodes in which all positive outdegrees are the same.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula