A292085 -id:A292085 - cp's OEIS frontend

A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, 218751, 699534, 2253676, 7305788, 23816743, 78023602, 256738751, 848152864, 2811996972, 9353366564, 31204088381, 104384620070, 350064856815, 1176693361956, 3963752002320

Offset: 1

N. J. A. Sloane and John Riordan

Also the number of unlabeled connected cographs on n nodes. - N. J. A. Sloane and Eric W. Weisstein, Oct 21 2003
A cograph is a simple graph which contains no path of length 3 as an induced subgraph. - Michael Somos, Apr 19 2014
Also called "hierarchies" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017

			G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...
a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)). - _Michael Somos_, Jul 25 2003

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 43.
A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999. (For definition of cograph)
A. Cayley, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 3, p. 246.
D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.
L. F. Meyers, Corrections and additions to Tree Representations in Linguistics. Report 3, 1966, p. 138. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
L. F. Meyers and W. S.-Y. Wang, Tree Representations in Linguistics. Report 3, 1963, pp. 107-108. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93 (the numbers called a_n in this paper). Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560-570.
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).

N. J. A. Sloane, First 1001 terms of A000669
Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, and Martin Leuner, On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture, arXiv:1907.01073 [math.CO], 2019.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See pp. 155, 162, 165, 172. - _N. J. A. Sloane_, Apr 18 2014
Peter J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, and Mingxian Zhong, Obstructions for three-coloring graphs without induced paths on six vertices, arXiv preprint arXiv:1504.06979 [math.CO], 2015-2018.
Steven R. Finch, Series-parallel networks
Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Philippe Flajolet, A Problem in Statistical Classification Theory
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72
Daniel L. Geisler, Combinatorics of Iterated Functions
A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 9.
O. Golinelli, Asymptotic behavior of two-terminal series-parallel networks, arXiv:cond-mat/9707023 [cond-mat.stat-mech], 1997.
JiSun Huh and Seonjeong Park, Toric varieties of Schröder type, arXiv:2204.00214 [math.AG], 2022. (Table 1)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 44 [broken link].
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From _N. J. A. Sloane_, Dec 22 2012
P. A. MacMahon, Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page 333 gives A000084 = 2*A000669.
Arnau Mir, Francesc Rossello, and Lucia Rotger, Sound Colless-like balance indices for multifurcating trees, arXiv:1805.01329 [q-bio.PE], 2018.
V. Modrak and D. Marton, Development of Metrics and a Complexity Scale for the Topology of Assembly Supply Chains, Entropy 2013, 15, 4285-4299.
J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226.
Vlady Ravelomanana and Loys Thimonier, Asymptotic enumeration of cographs, Electronic Notes in Discrete Mathematics, Volume 7, April 2001, pp. 58-61, Theorem 4.
J. Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16. (page 6)
J. Riordan, Letter to N. J. A. Sloane, Sep. 1970
J. Riordan, Letter to N. J. A. Sloane, Nov 10 1970
Audace Amen Vioutou Dossou-Olory, and Stephan Wagner, Inducibility of Topological Trees, arXiv:1802.06696 [math.CO], 2018.
Audace Amen Vioutou Dossou-Olory, The topological trees with extremal Matula numbers, arXiv:1806.03995 [math.CO], 2018.
Wei Wang and Ximei Huang, Almost all cographs have a cospectral mate, arXiv:2507.16730 [math.CO], 2025. See pp. 6, 8.
Eric Weisstein's World of Mathematics, Series-Parallel Network
Index entries for sequences related to rooted trees
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to trees

Equals (1/2)*A000084 for n >= 2.
Cf. A000055, A000311, A001678, A007827, A363064.
Cf. A000311, labeled hierarchies on n points.
Column 1 of A319254.
Main diagonal of A292085.
Row sums of A292086.

Method 1: a := [1,1]; for n from 3 to 30 do L := series( mul( (1-x^k)^(-a[k]),k=1..n-1)/(1-x^n)^b, x,n+1); t1 := coeff(L,x,n); R := series( 1+2*add(a[k]*x^k,k=1..n-1)+2*b*x^n, x, n+1); t2 := coeff(R,x,n); t3 := solve(t1-t2,b); a := [op(a),t3]; od: A000669 := n-> a[n];
Method 2, more efficient: with(numtheory): M := 1001; a := array(0..M); p := array(0..M); a[1] := 1; a[2] := 1; a[3] := 2; p[1] := 1; p[2] := 3; p[3] := 7;
Method 2, cont.: for m from 4 to M do t1 := divisors(m); t3 := 0; for d in t1 minus {m} do t3 := t3+d*a[d]; od: t4 := p[m-1]+2*add(p[k]*a[m-k],k=1..m-2)+t3; a[m] := t4/m; p[m] := t3+t4; od: # A000669 := n-> a[n]; A058757 := n->p[n];
# Method 3:
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(a(i)+j-1, j)*
       b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n, n-1)):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 28 2016

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[a[i]+j-1, j]* b[n-i*j, i-1], {j, 0, n/i}]]];
a[n_] := If[n<2, n, b[n, n-1]];
Array[a, 40] (* Jean-François Alcover, Jan 08 2021, after Alois P. Heinz *)

{a(n) = my(A, X); if( n<2, n>0, X = x + x * O(x^n); A = 1 / (1 - X); for(k=2, n, A /= (1 - X^k)^polcoeff(A, k)); polcoeff(A, n)/2)}; /* Michael Somos, Jul 25 2003 */

from collections import Counter
def A000669_list(n):
    list = [1] + [0] * (n - 1)
    for i in range(1, n):
        for p in Partitions(i + 1, min_length=2):
            m = Counter(p)
            list[i] += prod(binomial(list[s - 1] + m[s] - 1, m[s]) for s in m)
    return list
print(A000669_list(20)) # M. Eren Kesim, Jun 21 2021

Product_{k>0} 1/(1-x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.
a(n) ~ c * d^n / n^(3/2), where d = 3.560839309538943329526129172709667..., c = 0.20638144460078903185013578707202765... [Ravelomanana and Thimonier, 2001]. - Vaclav Kotesovec, Aug 25 2014
Consider a nontrivial partition p of n. For each size s of a part occurring in p, compute binomial(a(s)+m-1, m) where m is the multiplicity of s. Take the product of this expression over all s. Take the sum of this new expression over all p to obtain a(n). - Thomas Anton, Nov 22 2018

Sequence crossreference fixed by Sean A. Irvine, Sep 15 2009

A001190 Wedderburn-Etherington numbers: unlabeled binary rooted trees (every node has outdegree 0 or 2) with n endpoints (and 2n-1 nodes in all).

Original entry on oeis.org

0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, 127912, 293547, 676157, 1563372, 3626149, 8436379, 19680277, 46026618, 107890609, 253450711, 596572387, 1406818759, 3323236238, 7862958391, 18632325319, 44214569100, 105061603969

Offset: 0

N. J. A. Sloane

Also number of n-node binary rooted trees (every node has outdegree <= 2) where root has degree 0 (only for n=1) or 1.
a(n+1) is the number of rooted trees with n nodes where the outdegree of every node is <= 2, see example. These trees are obtained by removing the root of the trees in the comment above. - Joerg Arndt, Jun 29 2014
Number of interpretations of x^n (or number of ways to insert parentheses) when multiplication is commutative but not associative. E.g., a(4) = 2: x(x*x^2) and x^2*x^2. a(5) = 3: (x*x^2)x^2, x(x*x*x^2) and x(x^2*x^2). [If multiplication is non-commutative then the answer is A000108(n-1). - Jianing Song, Apr 29 2022]
Number of ways to place n stars in a single bound stable hierarchical multiple star system; i.e., taking only the configurations from A003214 where all stars are included in single outer parentheses. - Piet Hut, Nov 07 2003
Number of colorations of Kn (complete graph of order n) with n-1 colors such that no triangle is three-colored. Two edge-colorations C1 and C2 of G are isomorphic iff exists an automorphism f (isomorphism between G an G) such that: f sends same-colored edges of C1 on same-colored edges of C2 and f^(-1) sends same-colored edges of C2 on same-colored edges of C1. - Abraham Gutiérrez, Nov 12 2012
For n>1, a(n) is the number of (not necessarily distinct) unordered pairs of free unlabeled trees having a total of n nodes. See the first entry in formula section. - Geoffrey Critzer, Nov 09 2014
Named after the English mathematician Ivor Etherington (1908-1994) and the Scottish mathematician Joseph Wedderburn (1882-1948). - Amiram Eldar, May 29 2021

			G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 23*x^8 + 46*x^9 + 98*x^10 + ...
From _Joerg Arndt_, Jun 29 2014: (Start)
The a(6+1) = 11 rooted trees with 6 nodes as described in the comment are:
:           level sequence       outdegrees (dots for zeros)
:     1:  [ 0 1 2 3 4 5 ]    [ 1 1 1 1 1 . ]
:  O--o--o--o--o--o
:
:     2:  [ 0 1 2 3 4 4 ]    [ 1 1 1 2 . . ]
:  O--o--o--o--o
:           .--o
:
:     3:  [ 0 1 2 3 4 3 ]    [ 1 1 2 1 . . ]
:  O--o--o--o--o
:        .--o
:
:     4:  [ 0 1 2 3 4 2 ]    [ 1 2 1 1 . . ]
:  O--o--o--o--o
:     .--o
:
:     5:  [ 0 1 2 3 4 1 ]    [ 2 1 1 1 . . ]
:  O--o--o--o--o
:  .--o
:
:     6:  [ 0 1 2 3 3 2 ]    [ 1 2 2 . . . ]
:  O--o--o--o
:        .--o
:     .--o
:
:     7:  [ 0 1 2 3 3 1 ]    [ 2 1 2 . . . ]
:  O--o--o--o
:        .--o
:  .--o
:
:     8:  [ 0 1 2 3 2 3 ]    [ 1 2 1 . 1 . ]
:  O--o--o--o
:     .--o--o
:
:     9:  [ 0 1 2 3 2 1 ]    [ 2 2 1 . . . ]
:  O--o--o--o
:     .--o
:  .--o
:
:    10:  [ 0 1 2 3 1 2 ]    [ 2 1 1 . 1 . ]
:  O--o--o--o
:  .--o--o
:
:    11:  [ 0 1 2 2 1 2 ]    [ 2 2 . . 1 . ]
:  O--o--o
:     .--o
:  .--o--o
:
(End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 55.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.
A. Gutiérrez-Sánchez, Shen-colored tournaments, thesis, UNAM, 2012.
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).
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.52.
Richard P. Stanley, Catalan Numbers, Cambridge, 2015, p. 133.

Alois P. Heinz, Table of n, a(n) for n = 0..2545 (first 201 terms from T. D. Noe)
R. Arratia, S. Garibaldi, and A. W. Hales, The van den Berg--Kesten--Reimer inequality for infinite spaces, arXiv preprint arXiv:1508.05337 [math.PR], 2015.
Yu Hin (Gary) Au, Fatemeh Bagherzadeh, and Murray R. Bremner, Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube, arXiv:1903.00813 [math.CO], 2019.
F. Bagherzadeh, M. R. Bremner, and S. Madariaga, Jordan trialgebras and post-Jordan algebras, arXiv:1611.01214 [math.RA], 2016.
Nils Berglund and Yvain Bruned, BPHZ renormalisation and vanishing subcriticality limit of the fractional Phi_d^3 model, arXiv:1907.13028 [math.PR], 2019.
Nils Berglund and Christian Kuehn, Model Spaces of Regularity Structures for Space-Fractional SPDEs, Journal of Statistical Physics, Springer Verlag, 2017, 168 (2), pp. 331-368; HAL Id: hal-01432157.
Mayfawny Bergmann, Efficiency of Lossless Compression of a Binary Tree via its Minimal Directed Acyclic Graph Representation. Rose-Hulman Undergraduate Mathematics Journal: Vol. 15: Iss. 2, Article 1 (2014).
Sara Billey, Matjaz Konvalinka, and Frederick A Matsen IV, On the enumeration of tanglegrams and tangled chains, arXiv:1507.04976 [math.CO], 2015.
Sara Billey, Matjaž Konvalinka, and Frederick A. Matsen IV, On trees, tanglegrams, and tangled chains, hal-02173394 [math.CO], 2020.
Henry Bottomley, Illustration of initial terms.
M. Bremner, S. Madariaga, and L. A. Peresi, Structure theory for the group algebra of the symmetric group, with applications to polynomial identities for the octonions, arXiv:1407.3810 [math.RA], 2014.
Nicolas Broutin and Philippe Flajolet, The distribution of height and diameter in random non-plane binary trees, Random Struct. Algorithms 41, No. 2, 215-252 (2012).
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, Some treelike objects, Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155-183. MR0891613 (89a:05009). See p. 155. - _N. J. A. Sloane_, Apr 18 2014
Lorenzo Cappello and Julia A. Palacios, Sequential importance sampling for multi-resolution Kingman-Tajima coalescent counting, arXiv:1902.05527 [stat.AP], 2019.
Sean Cleary, M. Fischer, R. C. Griffiths, and R. Sainudiin, Some distributions on finite rooted binary trees, UCDMS Research Report NO. UCDMS2015/2, School of Mathematics and Statistics, University of Canterbury, Christchurch, NZ, 2015.
S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.
N. G. de Bruijn and D. A. Klarner, Multisets of aperiodic cycles, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359-368. MR0666861(84i:05008). See p. 367. - _N. J. A. Sloane_, Mar 25 2014
Jimmy Devillet and Bruno Teheux, Associative, idempotent, symmetric, and order-preserving operations on chains, arXiv:1805.11936 [math.RA], 2018.
Luc Devroye, Michael R. Doboli, Noah A. Rosenberg, and Stephan Wagner, Tree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees, arXiv:2409.18956 [math.CO], 2024. See p. 21.
Filippo Disanto and Thomas Wiehe, Some combinatorial problems on binary rooted trees occurring in population genetics, arXiv preprint arXiv:1112.1295 [math.CO], 2011-2012.
Michael R. Doboli, Hsien-Kuei Hwang, and Noah A. Rosenberg, Periodic Behavior of the Minimal Colijn-Plazzotta Rank for Trees with a Fixed Number of Leaves, In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 18:1-18:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024).
Vladimir Dotsenko and Irvin Roy Hentzel, On the conjecture of Kashuba and Mathieu about free Jordan algebras, arXiv:2507.00437 [math.RA], 2025. See p. 14.
I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39 and 153.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]
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.
A. Erdelyi and I. M. H. Etherington, Some problems of non-associative combinations (II), Edinburgh Math. Notes, 32 (1940), pp. vii-xiv.
V. Fack, S. Lievens and J. Van der Jeugt, On the diameter of the rotation graph of binary coupling trees. Discrete Math. 245 (2002), no. 1-3, 1--18. MR1887046 (2003i:05047).
Steven R. Finch, Otter's Tree Enumeration Constants. [Broken link]
Steven R. Finch, Otter's Tree Enumeration Constants. [Wayback Machine]
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 72
J. N. Franklin and S. W. Golomb, A Function-Theoretic Approach to the Study of Nonlinear Recurring Sequences, Pacific J. Math., Vol. 56, p. 467, 1975.
Ira M. Gessel, Counting tanglegrams with species, arXiv:1509.03867 [math.CO], 2020.
Piet Hut, Home Page
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 43
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 45
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph.D. Dissertation, University of South Carolina, 2012.
M. Konvalinka and S. Wagner, The shape of random tanglegrams, arXiv preprint arXiv:1512.01168 [math.CO], 2015.
A. Ledda, G. Achaz, T. Wiehe and L. Ferretti, Decomposing the site frequency spectrum: the impact of tree topology on neutrality tests, arXiv preprint arXiv:1510.06748 [q-bio.PE], 2015.
Eunjeong Lee, Mikiya Masuda, and Seonjeong Park, Toric Richardson varieties of Catalan type and Wedderburn-Etherington numbers, arXiv:2105.12274 [math.AG], 2021.
F. Murtagh, Counting dendrograms: a survey, Discrete Applied Mathematics, 7 (1984), 191-199.
C. D. Olds, Problem 4277, Amer. Math. Monthly, 56 (1949), 697-699.
C. D. Olds (Proposer) and H. W. Becker (Discussion), Problem 4277, Amer. Math. Monthly 56 (1949), 697-699. [Annotated scanned copy]
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
J. Riordan, Letter to N. J. A. Sloane, Oct. 1970
David Serena and William J. Buchanan, Equivalence Classes Induced by Binary Tree Isomorphism -- Generating Functions, arXiv:2503.02663 [math.CO], 2025. See p. 5.
Chloe E. Shiff and Noah A. Rosenberg, Enumeration of rooted binary perfect phylogenies, arXiv:2410.14915 [q-bio.PE], 2024. See pp. 2, 5, 9.
F. Sievers, G. M. Hughes, and D. G. Higgins, Systematic Exploration of Guide-Tree Topology Effects for Small Protein Alignments, BMC Bioinformatics 2014, 15:338 (Mentions A001190).
J. H. M. Wedderburn, The functional equation g(x^2) = 2ax + [g(x)]^2, Ann. Math., 24 (1922-23), 121-140.
Eric Weisstein's World of Mathematics, Weakly Binary Tree.
Eric Weisstein's World of Mathematics, Strongly Binary Tree.
Wikipedia, Wedderburn-Etherington numbers.
Index entries for "core" sequences
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
Index entries for sequences related to parenthesizing

Cf. A000108, A001699, A002658, A003214, A006894, A006961, A088325.
Cf. A086317, A086318, A240943.
Cf. A292553, A292554, A292555, A292556.
Column k=2 of A292085 and of A299038.
Column k=1 of A319539 and of A319541.

A001190 := proc(n) option remember; local s,k; if n<=1 then RETURN(n); elif n <=3 then RETURN(1); else s := 0; if n mod 2 = 0 then s := A001190(n/2)*(A001190(n/2)+1)/2; for k from 1 to n/2-1 do s := s+A001190(k)*A001190(n-k); od; RETURN(s); else for k from 1 to (n-1)/2 do s := s+A001190(k)*A001190(n-k); od; RETURN(s); fi; fi; end;
N := 40: G001190 := add(A001190(n)*x^n,n=0..N);
spec := [S,{S=Union(Z,Prod(Z,Set(S,card=2)))},unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
# alternative Maple program:
a:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
      (t-> t*(1-t)/2)(a(n/2)))+add(a(i)*a(n-i), i=1..n/2))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Aug 28 2017

terms = 35; A[] = 0; Do[A[x] = x + (1/2)*(A[x]^2 + A[x^2]) + O[x]^terms // Normal, terms]; CoefficientList[A[x], x] (* Jean-François Alcover, Jul 22 2011, updated Jan 10 2018 *)
a[n_?OddQ] := a[n] = Sum[a[k]*a[n-k], {k, 1, (n-1)/2}]; a[n_?EvenQ] := a[n] = Sum[a[k]*a[n-k], {k, 1, n/2-1}] + (1/2)*a[n/2]*(1+a[n/2]); a[0]=0; a[1]=1; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Jun 13 2012, after recurrence formula *)
a[ n_] := If[ n < 0, 0, SeriesCoefficient[ Nest[ 1 - Sqrt[1 - 2 x - (# /. x -> x^2)] &, 0, BitLength @ n], {x, 0, n}]]; (* Michael Somos, Apr 25 2013 *)

{a(n) = local(A, m); if( n<0, 0, m=1; A = O(x); while( m<=n, m*=2; A = 1 - sqrt(1 - 2*x - subst(A, x, x^2))); polcoeff(A, n))}; /* Michael Somos, Sep 06 2003 */

{a(n) = local(A); if( n<4, n>0, A = vector(n, i, 1); for( i=4, n, A[i] = sum( j=1, (i-1)\2, A[j] * A[i-j]) + if( i%2, 0, A[i/2] * (A[i/2] + 1)/2)); A[n])}; /* Michael Somos, Mar 25 2006 */

from functools import lru_cache
@lru_cache(maxsize=None)
def A001190(n):
    if n <= 1: return n
    m = n//2 + n % 2
    return sum(A001190(i+1)*A001190(n-1-i) for i in range(m-1)) + (1 - n % 2)*A001190(m)*(A001190(m)+1)//2 # Chai Wah Wu, Jan 14 2022

G.f. satisfies A(x) = x + (1/2)*(A(x)^2 + A(x^2)) [de Bruijn and Klarner].
G.f. also satisfies A(x) = 1 - sqrt(1 - 2*x - A(x^2)). - Michael Somos, Sep 06 2003
a(2n-1) = a(1)a(2n-2) + a(2)a(2n-3) + ... + a(n-1)a(n), a(2n) = a(1)a(2n-1) + a(2)a(2n-2) + ... + a(n-1)a(n+1) + a(n)(a(n)+1)/2.
Given g.f. A(x), then B(x) = -1 + A(x) satisfies 0 = f(B(x), B(x^2), B(x^4)) where f(u, v, w) = (u^2 + v)^2 + 2*(v^2 + w). - Michael Somos, Oct 22 2006
The radius of convergence of the g.f. is A240943 = 1/A086317 ~ 0.4026975... - Jean-François Alcover, Jul 28 2014, after Steven R. Finch.
a(n) ~ A086318 * A086317^(n-1) / n^(3/2). - Vaclav Kotesovec, Apr 19 2016

A292086 Number T(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that k is the maximum of 1 and the node outdegrees; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 6, 2, 1, 0, 6, 17, 7, 2, 1, 0, 11, 47, 22, 7, 2, 1, 0, 23, 133, 72, 23, 7, 2, 1, 0, 46, 380, 230, 77, 23, 7, 2, 1, 0, 98, 1096, 751, 256, 78, 23, 7, 2, 1, 0, 207, 3186, 2442, 861, 261, 78, 23, 7, 2, 1, 0, 451, 9351, 8006, 2897, 887, 262, 78, 23, 7, 2, 1

Offset: 1

Alois P. Heinz, Sep 08 2017

			:   T(4,2) = 2        :   T(4,3) = 2      : T(4,4) = 1 :
:                     :                   :            :
:       o       o     :      o       o    :     o      :
:      / \     / \    :     / \     /|\   :   /( )\    :
:     o   N   o   o   :    o   N   o N N  :  N N N N   :
:    / \     ( ) ( )  :   /|\     ( )     :            :
:   o   N    N N N N  :  N N N    N N     :            :
:  ( )                :                   :            :
:  N N                :                   :            :
:                     :                   :            :
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,   1;
  0,  2,   2,   1;
  0,  3,   6,   2,  1;
  0,  6,  17,   7,  2,  1;
  0, 11,  47,  22,  7,  2, 1;
  0, 23, 133,  72, 23,  7, 2, 1;
  0, 46, 380, 230, 77, 23, 7, 2, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Index entries for sequences related to rooted trees

Columns k=1-10 give: A063524, A001190 (for n>1), A292229, A292230, A292231, A292232, A292233, A292234, A292235, A292236.
Row sums give A000669.
Limit of reversed rows gives A292087.
Cf. A244372, A288942, A292085.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, k)-`if`(k=1, 0, A(n, k-1)):
seq(seq(T(n, k), k=1..n), n=1..15);

b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]];
T[n_, k_] := A[n, k] - If[k == 1, 0, A[n, k - 1]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

T(n,k) = A292085(n,k) - A292085(n,k-1) for k>2, T(n,1) = A292085(n,1).

A268172 Binary-ternary Wedderburn-Etherington numbers.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 23, 58, 156, 426, 1194, 3393, 9802, 28601, 84347, 250732, 750908, 2262817, 6857386, 20882889, 63877262, 196162762, 604567254, 1869318719, 5797113028, 18026873112, 56197262814, 175594836698, 549839459963, 1725126992844, 5422602630117, 17074281639963, 53848886560675, 170085320026578

Offset: 0

Murray R. Bremner, Jan 27 2016

This is the number of non-planar binary-ternary rooted trees (every node has out-degree 0 or 2 or 3) with n leaf nodes, indexed by the number of leaf nodes (NOT the total number of nodes).

It can also be interpreted as the number of bracketings (valid placements of operation symbols) in a monomial of degree n in a nonassociative algebra with an (anti-)commutative binary operation and a completely (skew-)symmetric ternary operation.

			Here are the 1, 1, 2, 4, 9, 23 bracketings for degrees 1 to 6 (using the monomial interpretation), where the binary and ternary operations are written [-,-] and [-,-,-] respectively, and the hyphen is a placeholder for the argument symbols:
Degree 1: -.
Degree 2: [-,-].
Degree 3: [[-,-],-], [-,-,-].
Degree 4: [[[-,-],-],-], [[-,-],[-,-]], [[-,-,-],-], [[-,-],-,-].
Degree 5:
   [[[[-,-],-],-],-],
   [[[-,-,-],-],-],
   [[[-,-],[-,-]],-],
   [[[-,-],-,-],-],
   [[[-,-],-],[-,-]],
   [[-,-,-],[-,-]],
   [[[-,-],-],-,-],
   [[-,-,-],-,-],
   [[-,-],[-,-],-].
Degree 6:
   [[[[[-,-],-],-],-],-],
   [[[[-,-,-],-],-],-],
   [[[[-,-],[-,-]],-],-],
   [[[[-,-],-,-],-],-],
   [[[[-,-],-],[-,-]],-],
   [[[-,-,-],[-,-]],-],
   [[[[-,-],-],-,-],-],
   [[[-,-,-],-,-],-],
   [[[-,-], [-,-],-],-],
   [[[[-,-],-],-],[-,-]],
   [[[-,-,-],-],[-,-]],
   [[[-,-], [-,-]],[-,-]],
   [[[-,-],-,-],[-,-]],
   [[[-,-],-],[[-,-],-]],
   [[[-,-],-],[-,-,-]],
   [[-,-,-],[-,-,-]],
   [[[[-,-],-],-],-,-],
   [[[-,-,-],-],-,-],
   [[[-,-],[-,-]],-,-],
   [[[-,-],-,-],-,-],
   [[[-,-],-],[-,-],-],
   [[-,-,-],[-,-],-],
   [[-,-],[-,-],[-,-]].

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Murray R. Bremner, Maple code for binary-ternary Wedderburn-Etherington numbers
Murray R. Bremner, Recursion formula for binary-ternary Wedderburn-Etherington numbers

Cf. A001190 (Binary Wedderburn-Etherington numbers).
Cf. A000598 (Ternary Wedderburn-Etherington numbers: number of non-planar ternary rooted trees with n nodes): note that this sequence is indexed by the total number of nodes, NOT the number of leaves.
Cf. A000669, A268163.
Column k=3 of A292085.

# for first Maple program see Links
# second Maple program:
b:= proc(n, i, v) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or nAlois P. Heinz, Jan 28 2016

b[n_, i_, v_] := b[n, i, v] = If[n==0, If[v==0, 1, 0], If[i<1 || v<1 || nJean-François Alcover, Feb 25 2017, after Alois P. Heinz *)

See Maple code, and the recursion formula under Links.

cp's OEIS Frontend

A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A001190 Wedderburn-Etherington numbers: unlabeled binary rooted trees (every node has outdegree 0 or 2) with n endpoints (and 2n-1 nodes in all).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A292086 Number T(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that k is the maximum of 1 and the node outdegrees; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A268172 Binary-ternary Wedderburn-Etherington numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A292210 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than four.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A292211 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than five.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A292212 Number of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than six.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple