A086317 -id:A086317 - cp's OEIS frontend

A245651 Decimal expansion of eta/xi = A086318/A086317, a coefficient associated with the asymptotics of the number of weakly binary trees.

3, 1, 8, 7, 7, 6, 6, 2, 5, 9, 2, 5, 0, 2, 9, 6, 7, 5, 4, 8, 0, 0, 8, 1, 7, 6, 9, 7, 7, 8, 0, 1, 3, 1, 8, 1, 9, 7, 2, 1, 2, 4, 1, 8, 6, 7, 8, 7, 8, 7, 0, 1, 7, 0, 1, 9, 7, 5, 4, 9, 6, 8, 1, 7, 8, 9, 5, 7, 3, 2, 3, 4, 2, 6, 0, 2, 2, 9, 9, 0, 0, 6, 4, 0, 9, 1

Offset: 0

Jean-François Alcover, Jul 28 2014

			0.31877662592502967548008176977801318197212418678787017019754968178957323426...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.6 Otter's Tree Enumeration Constants, p. 297.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Nils Berglund, 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.
Eric Weisstein's MathWorld, Weakly binary tree

Cf. A086317, A086318.

digits = 103; Clear[c, k]; c[0] = 2; c[n_] := c[n] = c[n-1]^2 + 2; k[n_] := k[n] = (Sqrt[c[n]^2^(-n)]*Sqrt[3 + Sum[1/Product[c[j], {j, 1, k}], {k, 1, n}]])/(c[n]^2^(-n)*(2*Sqrt[Pi])); k[5]; k[n = 10]; While[RealDigits[k[n], 10, digits] != RealDigits[k[n-5], 10, digits], n = n+5]; RealDigits[k[n], 10, digits] // First

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

A000672 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 37, 66, 135, 265, 552, 1132, 2410, 5098, 11020, 23846, 52233, 114796, 254371, 565734, 1265579, 2841632, 6408674, 14502229, 32935002, 75021750, 171404424, 392658842, 901842517, 2076217086, 4790669518, 11077270335

Offset: 0

N. J. A. Sloane

This can be described in 2 ways: (a) Trees with n nodes of valency <= 3, for n = 0,1,2,3,... (b) Trees with t = 2n+2 nodes of valency either 1 or 3 (implying that there are n nodes of valency 3 - the boron atoms - and n+2 nodes of valency 1 - the hydrogen atoms), for t = 2,4,6,8,...

Essentially the same sequences arises from studying the number of unrooted, unlabeled binary tree topologies with n leaves (see A129860). - Steven Kelk, Jul 22 2016

			The 4 trees with 6 nodes are:
._._._._._. . ._._._._. . ._._._._. . ._._._.
. . . . . . . . | . . . . . . | . . . . | |
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 11*x^8 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
P. J. Cameron, Oligomorphic Permutation Groups, Cambridge; see Fig. 2 p. 35.
A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, page 33. Note that at least the first two editions give an incorrect version of this sequence.
R. C. Read, personal communication.
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. J. Mathar, Table of n, a(n) for n = 0..191 [b-file corrected by _N. J. A. Sloane_, Oct 04 2010]
Dominik Bendle, Janko Boehm, Yue Ren, and Benjamin Schröter, Parallel Computation of tropical varieties, their positive part, and tropical Grassmannians, arXiv:2003.13752 [math.AG], 2020.
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).
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183.
M. Chan, Tropical hyperelliptic curves, arXiv preprint arXiv:1110.0273 [math.CO], 2011.
Sergio Consoli, Jan Korst, Gijs Geleijnse, and Steffen Pauws, On the minimum quartet tree cost problem, arXiv:1807.00566 [cs.DM], 2018.
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.
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).
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Six-Point Conformal Blocks in the Snowflake Channel, arXiv:2004.02824 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Seven-Point Conformal Blocks in the Extended Snowflake Channel and Beyond, arXiv:2006.13964 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, All Global One- and Two-Dimensional Higher-Point Conformal Blocks, arXiv:2009.07674 [hep-th], 2020.
M. D. Hendy, C. H. C. Little, David Penny, Comparing trees with pendant vertices labelled, SIAM J. Appl. Math. 44 (5) (1984) Table 1
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, PhD Dissertation, University of South Carolina, 2012. - From _N. J. A. Sloane_, Dec 22 2012
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
Eric Weisstein's World of Mathematics, Trivalent Tree
Index entries for sequences related to trees

Column k = 3 of A144528.
A000672 = A000675 + A000673.
Cf. A001190(n+1) (rooted trees).
Cf. A052120, A000022, A000200, A000602, A129860.

(* c = A001190 *) c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k, 1, (n-1)/2}]; c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k], {k, 1, n/2-1}]; c[0] = 0; c[1] = 1; b[x_] := If[IntegerQ[x], c[x+1], 0]; a[0] = a[1] = a[2] = 1; a[n_] := b[n/2] - (1/3)*(b[(n-1)/3]-1)*b[(n-1)/3]*(b[(n-1)/3] + 1) + 2*b[n] - b[n+1] - Sum[(1/2)*(b[i]-1)*b[i]*b[-2*i + n - 1], {i, 1, (n-2)/2}] + Sum[b[i]*Sum[b[j]*b[n-i-j-1], {j, i, (1/2)*(n-i-1)}], {i, 1, (n-1)/3}]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jan 19 2015 *)
n = 50; (* algorithm from Rains and Sloane *)
S2[f_,h_,x_] := f[h,x]^2/2 + f[h,x^2]/2;
S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S2[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S3[T,h-1,z]z - S3[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{1,1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* Robert A. Russell, Sep 15 2018 *)
n = 60; c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k,1,(n-1)/2}];
c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k],
  {k,1,n/2-1}]; c[0] = 0; c[1] = 1; (* as in program 1 above *)
gf[x_] := Sum[c[i+1] x^i, {i,0,n}]; (* g.f. for A001190(n+1) *)
ci[x_] := SymmetricGroupIndex[3, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 +
x ci[x], {x,0,n}]], x] (* Robert A. Russell, Jan 17 2023 *)

Rains and Sloane give a g.f.
a(0)=a(1)=a(2)=1, a(n) = 2*b(n+1) - b(n+2) + b((n+1)/2) - 2*C(1+b(n/3), 3) - Sum_{i=1..[(n-1)/2]} C(b(i), 2)*b(n-2*i) + Sum_{i=1..[n/3]} b(i) Sum_{j=i..[(n-i)/2]} b(j)*b(n-i-j), where b(x) = A001190(x+1) if x is an integer, otherwise 0 (Cyvin et al.) [Index of A001190 shifted by R. J. Mathar, Mar 08 2010]
a(n) = A000673(n) + A000675(n).
a(n) ~ c * d^n / n^(5/2), where d = A086317 = 2.4832535361726368585622885181... and c = 1.2551088797592580080398489829149157375... . - Vaclav Kotesovec, Apr 19 2016
G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S3,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^3 + 3*B(x) B(x^2) + 2*B(x^3)) / 6, where B(x) = 1 + x * cycle_index(S2,B(x)) = 1 + x * (B(x)^2 + B(x^2)) / 2 is the generating function for A001190(n+1). - Robert A. Russell, Jan 17 2023

A003214 Number of binary forests with n nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 76, 152, 320, 672, 1454, 3154, 6959, 15439, 34608, 77988, 176985, 403510, 924683, 2127335, 4913452, 11385955, 26468231, 61700232, 144206269, 337837221, 793213550, 1866181155, 4398867672, 10387045476, 24567374217, 58196129468, 138056734916

Offset: 0

N. J. A. Sloane

From Piet Hut, Nov 07 2003: "Number of ways to place n stars in stable hierarchical multiple star systems (where each stable multiple is a binary tree: around its center of mass two multiple star systems revolve, each of which can be a singleton or a nontrivial multiple star system).

"For example, a(1) = 1 : *; a(2) = 2 : (**), * *; a(3) = 3 : ((**)*), (**) *, * * *; a(4) = 6 : (((**)*)*), ((**)(**)), ((**)*) *, (**) (**), (**) * *, * * * * ."

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..2544 (first 201 terms from T. D. Noe)
Piet Hut, Home Page.

Cf. A001190.

b:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
      (t-> t*(1-t)/2)(b(n/2)))+add(b(i)*b(n-i), i=1..n/2))
    end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*b(d),
      d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 11 2017

terms = 35; (* G = G001190 *) G[] = 0; Do[G[x] = x + (1/2)*(G[x]^2 + G[x^2]) + O[x]^terms // Normal, terms]; A[x_] = Exp[Sum[G[x^i]/i, {i, 1, terms}]] + O[x]^terms; CoefficientList[A[x], x](* Jean-François Alcover, Nov 18 2011, updated Jan 12 2018 *)
(* b = A001190 *) b[n_] := b[n] = If[OddQ[n], Sum[b[k] b[n-k], {k, 1, (n-1)/2}], Sum[b[k] b[n-k], {k, 1, n/2 - 1}] + (1/2) b[n/2] (1+b[n/2])]; b[0] = 0; b[1] = 1;
etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[ Sum[d p[d], {d, Divisors[j]}] b[n-j], {j, 1, n}]/n]; b];
a[n_] := etr[b][n]; Table[a[n], {n, 0, 34}] (* Jean-François Alcover, Mar 14 2016 *)

Euler transform of A001190. - Michael Somos, Nov 10 2003
G.f.: exp( Sum_{i>=1} G001190(x^i)/i ), where G001190 = g.f. for A001190.
a(n) ~ c * d^n / n^(3/2), where d = A086317 = 2.4832535361726368585622885181... and c = 0.9874010699028009804... . - Vaclav Kotesovec, Apr 19 2016

A086318 Decimal expansion of asymptotic constant eta for counts of weakly binary trees.

Original entry on oeis.org

7, 9, 1, 6, 0, 3, 1, 8, 3, 5, 7, 7, 5, 1, 1, 8, 0, 7, 8, 2, 3, 6, 2, 8, 4, 5, 5, 7, 2, 3, 2, 6, 8, 2, 2, 4, 0, 7, 1, 7, 4, 2, 4, 1, 8, 0, 9, 0, 7, 8, 9, 4, 6, 7, 3, 1, 2, 3, 0, 7, 8, 3, 0, 9, 9, 2, 2, 9, 0, 4, 4, 1, 5, 0, 3, 8, 9, 3, 2, 9, 2, 5, 5, 4, 4, 6, 6, 7, 9, 0, 8, 6, 8, 4, 0, 4, 6, 3, 0, 3, 8, 3

Offset: 0

Eric W. Weisstein, Jul 15 2003

			0.791603183577511807823628455723268224071742418090789...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.6, p. 297.

Eric Weisstein's World of Mathematics, Weakly binary tree.

Cf. A001190, A086317.

digits = 102; c[0] = 2; c[n_] := c[n] = c[n - 1]^2 + 2; eta[n_Integer] := eta[n] = 1/2 * Sqrt[c[n]^2^(-n)/Pi] * Sqrt[3 + Sum[1/Product[c[j], {j, 1, k}], {k, 1, n}]]; eta[5]; eta[n = 10]; While[RealDigits[eta[n], 10, digits] != RealDigits[eta[n - 5], 10, digits], n = n + 5]; RealDigits[eta[n], 10, digits] // First (* Jean-François Alcover, May 27 2014 *)

Equals lim_{n->oo} A001190(n)*n^(3/2)/A086317^(n-1). - Vaclav Kotesovec, Apr 19 2016

A240943 Decimal expansion of the radius of convergence of Wedderburn-Etherington numbers g.f.

Original entry on oeis.org

4, 0, 2, 6, 9, 7, 5, 0, 3, 6, 7, 1, 4, 4, 1, 2, 9, 0, 9, 6, 9, 0, 4, 5, 3, 4, 8, 6, 5, 1, 0, 8, 3, 8, 0, 3, 4, 1, 7, 5, 5, 6, 7, 2, 1, 6, 2, 4, 9, 7, 2, 6, 5, 9, 2, 9, 1, 0, 5, 3, 4, 6, 4, 6, 0, 7, 6, 4, 2, 7, 2, 8, 9, 6, 6, 5, 2, 4, 2, 5, 8, 4, 1, 6, 4, 1, 6, 0, 9, 6, 0, 2, 6, 2, 1, 7, 2, 0, 5, 9, 5, 2

Offset: 0

Jean-François Alcover, Aug 04 2014

			0.4026975036714412909690453486510838034175567216249726592910534646...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.6 Otter's Tree Enumeration Constants, p. 297.

Nils Berglund, Yvain Bruned, BPHZ renormalisation and vanishing subcriticality limit of the fractional Phi_d^3 model, arXiv:1907.13028 [math.PR], 2019.
Nils Berglund, 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.
Nicolas Broutin and Philippe Flajolet, The height of random binary unlabelled trees, arXiv:0807.2365 [math.CO], 2008.
Eric Weisstein's World of Mathematics, Weakly binary tree

Cf. A001190, A086317.

digits = 102; n0 = 50; dn = 50; Clear[rho]; rho[n_] := rho[n] = (Clear[c]; c[0] = 0; y[z_] = Sum[c[k]*z^k, {k, 0, n}]; eq[0] = Rest[ Thread[CoefficientList[(-2*z + 2*y[z] - y[z]^2 - y[z^2])/2, z] == 0]]; s[1] = First[Solve[First[eq[0]], c[1]]]; Do[eq[k-1] = Rest[eq[k-2]] /. s[k-1]; s[k] = First[Solve[First[eq[k-1]], c[k]]], {k, 2, n}]; z /. FindRoot[ 2*z + y[z^2] == 1 /. Flatten[Table[s[k], {k, 1, n}]], {z, 1/2}, WorkingPrecision -> digits+10]); rho[n0]; rho[n = n0 + dn]; While[RealDigits[rho[n], 10, digits] != RealDigits[rho[n - dn], 10, digits], Print["n = ", n]; n = n + dn]; RealDigits[rho[n], 10, digits] // First
(* or, after A086317: *) Clear[c, xi]; c[0] = 2; c[n_] := c[n] = c[n-1]^2 + 2; xi[n_Integer] := xi[n] = c[n]^(2^-n); xi[5]; xi[n = 10]; While[RealDigits[xi[n], 10, digits] != RealDigits[xi[n-5], 10, digits], n = n+5]; RealDigits[1/xi[n], 10, digits] // First (* Jean-François Alcover, Aug 04 2014 *)

1/A086317.

A244398 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 2.

Original entry on oeis.org

1, 2, 5, 10, 22, 45, 97, 206, 450, 982, 2178, 4849, 10904, 24630, 56010, 127911, 293546, 676156, 1563371, 3626148, 8436378, 19680276, 46026617, 107890608, 253450710, 596572386, 1406818758, 3323236237, 7862958390, 18632325318, 44214569099, 105061603968

Offset: 3

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..1000

Column k=2 of A244372.

Cf. A001190, A036656, A086317, A086318.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> b(n-1$2, 2$2) -`if`(n=0, 0, 1):
seq(a(n), n=3..40);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, 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]}]] // FullSimplify]; a[n_] := b[n-1, n-1, 2, 2] - If[n == 0, 0, 1]; Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Feb 09 2015, after Maple *)

a(n) = A001190(n+1)-1 = A036656(n+1)-1.

a(n) ~ c * d^n / n^(3/2), where d = 2.4832535361726368... = A086317 and c = 0.7916031835775118... = A086318. - Vaclav Kotesovec, Jun 27 2014

A380256 Number of rooted binary normal unlabeled galled trees with n leaves and exactly 1 gall.

Original entry on oeis.org

0, 0, 0, 1, 4, 15, 48, 148, 435, 1250, 3512, 9726, 26587, 71975, 193200, 515051, 1364896, 3598794, 9447028, 24704031, 64382465, 167288460, 433512724, 1120719444, 2891035926, 7443225226, 19129208972, 49082742607, 125752279124, 321744111359, 822165920924, 2098475215237

Offset: 0

Noah A Rosenberg, Jan 17 2025

nonn

The asymptotic growth of a(n) follows (0.3910...)(2.4833...^n)n^(1/2), where 2.4833... is the constant represented by A086317.

			For n=3 leaves, there is a unique rooted binary unlabeled tree with a root gall from which 3 leaves are descended; hence a(3)=1. This galled tree has the shape:
     .
    / \
   ._._.
  /  |  \

Lily Agranat-Tamir, Shaili Mathur, and Noah A. Rosenberg, Enumeration of rooted binary unlabeled galled trees, Bull. Math. Biol. 86 (2024), 45. (see Table 3)
Lily Agranat-Tamir, Michael Fuchs, Bernhard Gittenberger, and Noah A. Rosenberg, Asymptotic enumeration of rooted binary unlabeled galled trees with a fixed number of galls. In C. Mailler, S. Wild, eds. Proceedings of the 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs) 302: 27. Schloss Dagstuhl — Leibniz-Zentrum für Informatik.

Cf. A001190 (rooted binary unlabeled galled trees with n leaves and 0 galls), A380211 (rooted binary unlabeled galled trees with n leaves and any number of galls).

Radius of convergence of the generating function follows the contstant A240943 (exponential growth according to A086317).

G.f.: 1/(1-U(x)) - 1/(1-U(x))^2 + U(x)/(2*(1-U(x))^3) + U(x)/(2*(1-U(x))*(1-U(x^2))), where U(x) is the g.f. of A001190 (eq. 48 of Agranat-Tamir et al., Bull. Math. Biol. 86 (2024), 45).

A380306 Irregular triangle read by rows: T(n,k) is the number of rooted binary normal unlabeled galled trees with n leaves and exactly k galls, 0 <= k <= floor((n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 3, 15, 2, 6, 48, 18, 11, 148, 107, 6, 23, 435, 528, 78, 46, 1250, 2295, 661, 19, 98, 3512, 9185, 4356, 346, 207, 9726, 34503, 24564, 3776, 67, 451, 26587, 123612, 123825, 31289, 1543, 983, 71975, 426218, 574149, 216501, 20720, 246

Offset: 1

Noah A Rosenberg, Jan 19 2025

For fixed k, the asymptotic growth of T(n,k) with n follows (2^(2*k-1) / ((2*k)! * g^(4*k-1) * sqrt(Pi))) * n^(2*k-3/2) * r^n, where r is the constant 2.4833... represented by A086317 and g is a constant 1.1300... (Theorem 10 of Agranat-Tamir et al., Leibniz International Proceedings in Informatics (LIPIcs) 302 (2024), 27).

			Triangle begins:
     1;
     1;
     1,      1;
     2,      4;
     3,     15,       2;
     6,     48,      18;
    11,    148,     107,       6;
    23,    435,     528,      78;
    46,   1250,    2295,     661,      19;
    98,   3512,    9185,    4356,     346;
   207,   9726,   34503,   24564,    3776,     67;
   451,  26587,  123612,  123825,   31289,   1543;
   983,  71975,  426218,  574149,  216501,  20720,  246;
  2179, 193200, 1425011, 2493129. 1316450, 206644, 6942;

Lily Agranat-Tamir, Shaili Mathur, and Noah A. Rosenberg, Enumeration of rooted binary unlabeled galled trees, Bull. Math. Biol. 86 (2024), 45. (see Table 3)
Lily Agranat-Tamir, Michael Fuchs, Bernhard Gittenberger, and Noah A. Rosenberg, Asymptotic enumeration of rooted binary unlabeled galled trees with a fixed number of galls. In C. Mailler, S. Wild, eds. Proceedings of the 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs) 302: 27. Schloss Dagstuhl — Leibniz-Zentrum für Informatik.

First column (k=0) is A001190.
Second column (k=1) is A380256.
Row sums give A380211.

G.f. satisfies A(x,y) = x + y + (1/2)*A(x,y)^2 + (1/2)*A(x^2,y^2) - y/(1-A(x,y)) + y*A(x,y)/(2*(1-A(x,y))^2) + y*A(x,y)/(2*(1-A(x^2,y^2))) (eq. 56 of Agranat-Tamir et al., Bull. Math. Biol. 86 (2024), 45).

cp's OEIS Frontend

A245651 Decimal expansion of eta/xi = A086318/A086317, a coefficient associated with the asymptotics of the number of weakly binary trees.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

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

A000672 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A003214 Number of binary forests with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A086318 Decimal expansion of asymptotic constant eta for counts of weakly binary trees.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A240943 Decimal expansion of the radius of convergence of Wedderburn-Etherington numbers g.f.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A244398 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 2.

Views

Author

Keywords

Links

Crossrefs

Programs