%I M0790 N0298 #276 Oct 28 2024 15:41:59

%S 0,1,1,1,2,3,6,11,23,46,98,207,451,983,2179,4850,10905,24631,56011,

%T 127912,293547,676157,1563372,3626149,8436379,19680277,46026618,

%U 107890609,253450711,596572387,1406818759,3323236238,7862958391,18632325319,44214569100

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

%C Also number of n-node binary rooted trees (every node has outdegree <= 2) where root has degree 0 (only for n=1) or 1.

%C 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

%C 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]

%C 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

%C 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

%C 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

%C Named after the English mathematician Ivor Etherington (1908-1994) and the Scottish mathematician Joseph Wedderburn (1882-1948). - _Amiram Eldar_, May 29 2021

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.

%D Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 55.

%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.

%D A. Gutiérrez-Sánchez, Shen-colored tournaments, thesis, UNAM, 2012.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%D Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.52.

%D Richard P. Stanley, Catalan Numbers, Cambridge, 2015, p. 133.

%H Alois P. Heinz, <a href="/A001190/b001190.txt">Table of n, a(n) for n = 0..2545</a> (first 201 terms from T. D. Noe)

%H R. Arratia, S. Garibaldi, and A. W. Hales, <a href="http://arxiv.org/abs/1508.05337">The van den Berg--Kesten--Reimer inequality for infinite spaces</a>, arXiv preprint arXiv:1508.05337 [math.PR], 2015.

%H Yu Hin (Gary) Au, Fatemeh Bagherzadeh, and Murray R. Bremner, <a href="https://arxiv.org/abs/1903.00813">Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube</a>, arXiv:1903.00813 [math.CO], 2019.

%H F. Bagherzadeh, M. R. Bremner, and S. Madariaga, <a href="http://arxiv.org/abs/1611.01214">Jordan trialgebras and post-Jordan algebras</a>, arXiv:1611.01214 [math.RA], 2016.

%H Nils Berglund and Yvain Bruned, <a href="https://arxiv.org/abs/1907.13028">BPHZ renormalisation and vanishing subcriticality limit of the fractional Phi_d^3 model</a>, arXiv:1907.13028 [math.PR], 2019.

%H Nils Berglund and Christian Kuehn, <a href="https://hal.archives-ouvertes.fr/hal-01432157">Model Spaces of Regularity Structures for Space-Fractional SPDEs</a>, Journal of Statistical Physics, Springer Verlag, 2017, 168 (2), pp. 331-368; HAL Id: hal-01432157.

%H Mayfawny Bergmann, <a href="http://scholar.rose-hulman.edu/rhumj/vol15/iss2/1/"> Efficiency of Lossless Compression of a Binary Tree via its Minimal Directed Acyclic Graph Representation</a>. Rose-Hulman Undergraduate Mathematics Journal: Vol. 15: Iss. 2, Article 1 (2014).

%H Sara Billey, Matjaz Konvalinka, and Frederick A Matsen IV, <a href="http://arxiv.org/abs/1507.04976">On the enumeration of tanglegrams and tangled chains</a>, arXiv:1507.04976 [math.CO], 2015.

%H Sara Billey, Matjaž Konvalinka, and Frederick A. Matsen IV, <a href="https://hal.archives-ouvertes.fr/hal-02173394">On trees, tanglegrams, and tangled chains</a>, hal-02173394 [math.CO], 2020.

%H Henry Bottomley, <a href="/A001190/a001190.gif">Illustration of initial terms</a>.

%H M. Bremner, S. Madariaga, and L. A. Peresi, <a href="http://arxiv.org/abs/1407.3810">Structure theory for the group algebra of the symmetric group, with applications to polynomial identities for the octonions</a>, arXiv:1407.3810 [math.RA], 2014.

%H Nicolas Broutin and Philippe Flajolet, <a href="https://doi.org/10.1002/rsa.20393">The distribution of height and diameter in random non-plane binary trees</a>, Random Struct. Algorithms 41, No. 2, 215-252 (2012).

%H Peter J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H Peter J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, 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

%H Lorenzo Cappello and Julia A. Palacios, <a href="https://arxiv.org/abs/1902.05527">Sequential importance sampling for multi-resolution Kingman-Tajima coalescent counting</a>, arXiv:1902.05527 [stat.AP], 2019.

%H Sean Cleary, M. Fischer, R. C. Griffiths, and R. Sainudiin, <a href="http://lamastex.org/preprints/20151231_SomeDistsFRBTrees.pdf">Some distributions on finite rooted binary trees</a>, UCDMS Research Report NO. UCDMS2015/2, School of Mathematics and Statistics, University of Canterbury, Christchurch, NZ, 2015.

%H S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, <a href="http://dx.doi.org/10.1016/0166-1280(95)04329-6">Enumeration of constitutional isomers of polyenes</a>, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.

%H N. G. de Bruijn and D. A. Klarner, <a href="http://dx.doi.org/10.1137/0603037">Multisets of aperiodic cycles</a>, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359-368. MR0666861(84i:05008). See p. 367. - _N. J. A. Sloane_, Mar 25 2014

%H Jimmy Devillet and Bruno Teheux, <a href="https://arxiv.org/abs/1805.11936">Associative, idempotent, symmetric, and order-preserving operations on chains</a>, arXiv:1805.11936 [math.RA], 2018.

%H Luc Devroye, Michael R. Doboli, Noah A. Rosenberg, and Stephan Wagner, <a href="https://arxiv.org/abs/2409.18956">Tree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees</a>, arXiv:2409.18956 [math.CO], 2024. See p. 21.

%H Filippo Disanto and Thomas Wiehe, <a href="http://arxiv.org/abs/1112.1295">Some combinatorial problems on binary rooted trees occurring in population genetics</a>, arXiv preprint arXiv:1112.1295 [math.CO], 2011-2012.

%H Michael R. Doboli, Hsien-Kuei Hwang, and Noah A. Rosenberg, <a href="https://doi.org/10.4230/LIPIcs.AofA.2024.18">Periodic Behavior of the Minimal Colijn-Plazzotta Rank for Trees with a Fixed Number of Leaves</a>, 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).

%H I. M. H. Etherington, <a href="http://www.jstor.org/stable/3605743">Non-associate powers and a functional equation</a>, Math. Gaz. 21 (1937), 36-39 and 153.

%H I. M. H. Etherington, <a href="/A000108/a000108_13.pdf">On non-associative combinations</a>, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]

%H I. M. H. Etherington, <a href="http://dx.doi.org/10.1017/S0370164600012244">On non-associative combinations</a>, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.

%H I. M. H. Etherington, <a href="http://dx.doi.org/10.1017/S0950184300002639">Some problems of non-associative combinations (I)</a>, Edinburgh Math. Notes, 32 (1940), pp. i-vi.

%H A. Erdelyi and I. M. H. Etherington, <a href="http://dx.doi.org/10.1017/S0950184300002640">Some problems of non-associative combinations (II)</a>, Edinburgh Math. Notes, 32 (1940), pp. vii-xiv.

%H V. Fack, S. Lievens and J. Van der Jeugt, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00418-6">On the diameter of the rotation graph of binary coupling trees</a>. Discrete Math. 245 (2002), no. 1-3, 1--18. MR1887046 (2003i:05047).

%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/otter/otter.html">Otter's Tree Enumeration Constants</a>. [Broken link]

%H Steven R. Finch, <a href="http://web.archive.org/web/20010207195939/http://www.mathsoft.com/asolve/constant/otter/otter.html">Otter's Tree Enumeration Constants</a>. [Wayback Machine]

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 72

%H J. N. Franklin and S. W. Golomb, <a href="http://projecteuclid.org/euclid.pjm/1102906370">A Function-Theoretic Approach to the Study of Nonlinear Recurring Sequences</a>, Pacific J. Math., Vol. 56, p. 467, 1975.

%H Ira M. Gessel, <a href="https://arxiv.org/abs/1509.03867">Counting tanglegrams with species</a>, arXiv:1509.03867 [math.CO], 2020.

%H Piet Hut, <a href="http://www.sns.ias.edu/~piet/">Home Page</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=43">Encyclopedia of Combinatorial Structures 43</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=45">Encyclopedia of Combinatorial Structures 45</a>

%H V. P. Johnson, <a href="http://people.math.sc.edu/czabarka/Theses/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. Southern Calif., 2012.

%H M. Konvalinka and S. Wagner, <a href="http://arxiv.org/abs/1512.01168">The shape of random tanglegrams</a>, arXiv preprint arXiv:1512.01168 [math.CO], 2015.

%H A. Ledda, G. Achaz, T. Wiehe and L. Ferretti, <a href="http://arxiv.org/abs/1510.06748">Decomposing the site frequency spectrum: the impact of tree topology on neutrality tests</a>, arXiv preprint arXiv:1510.06748 [q-bio.PE], 2015.

%H Eunjeong Lee, Mikiya Masuda, and Seonjeong Park, <a href="https://arxiv.org/abs/2105.12274">Toric Richardson varieties of Catalan type and Wedderburn-Etherington numbers</a>, arXiv:2105.12274 [math.AG], 2021.

%H F. Murtagh, <a href="http://dx.doi.org/10.1016/0166-218X(84)90066-0">Counting dendrograms: a survey</a>, Discrete Applied Mathematics, 7 (1984), 191-199.

%H C. D. Olds, <a href="http://www.jstor.org/stable/2305574">Problem 4277</a>, Amer. Math. Monthly, 56 (1949), 697-699.

%H C. D. Olds (Proposer) and H. W. Becker (Discussion), <a href="/A000108/a000108_6.pdf">Problem 4277</a>, Amer. Math. Monthly 56 (1949), 697-699. [Annotated scanned copy]

%H R. C. Read, <a href="/A000684/a000684_1.pdf">Letter to N. J. A. Sloane, Oct. 29, 1976</a>

%H J. Riordan, <a href="/A000262/a000262_1.pdf">Letter to N. J. A. Sloane, Oct. 1970</a>

%H Chloe E. Shiff and Noah A. Rosenberg, <a href="https://arxiv.org/abs/2410.14915">Enumeration of rooted binary perfect phylogenies</a>, arXiv:2410.14915 [q-bio.PE], 2024. See pp. 2, 5, 9.

%H F. Sievers, G. M. Hughes, and D. G. Higgins, <a href="http://www.biomedcentral.com/1471-2105/15/338">Systematic Exploration of Guide-Tree Topology Effects for Small Protein Alignments</a>, BMC Bioinformatics 2014, 15:338 (Mentions A001190).

%H J. H. M. Wedderburn, <a href="http://www.jstor.org/stable/1967710">The functional equation g(x^2) = 2ax + [g(x)]^2</a>, Ann. Math., 24 (1922-23), 121-140.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WeaklyBinaryTree.html">Weakly Binary Tree</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/StronglyBinaryTree.html">Strongly Binary Tree</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Wedderburn-Etherington_number">Wedderburn-Etherington numbers</a>.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>

%F G.f. satisfies A(x) = x + (1/2)*(A(x)^2 + A(x^2)) [de Bruijn and Klarner].

%F G.f. also satisfies A(x) = 1 - sqrt(1 - 2*x - A(x^2)). - _Michael Somos_, Sep 06 2003

%F 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.

%F 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

%F 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.

%F a(n) ~ A086318 * A086317^(n-1) / n^(3/2). - _Vaclav Kotesovec_, Apr 19 2016

%e 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 + ...

%e From _Joerg Arndt_, Jun 29 2014: (Start)

%e The a(6+1) = 11 rooted trees with 6 nodes as described in the comment are:

%e : level sequence outdegrees (dots for zeros)

%e : 1: [ 0 1 2 3 4 5 ] [ 1 1 1 1 1 . ]

%e : O--o--o--o--o--o

%e :

%e : 2: [ 0 1 2 3 4 4 ] [ 1 1 1 2 . . ]

%e : O--o--o--o--o

%e : .--o

%e :

%e : 3: [ 0 1 2 3 4 3 ] [ 1 1 2 1 . . ]

%e : O--o--o--o--o

%e : .--o

%e :

%e : 4: [ 0 1 2 3 4 2 ] [ 1 2 1 1 . . ]

%e : O--o--o--o--o

%e : .--o

%e :

%e : 5: [ 0 1 2 3 4 1 ] [ 2 1 1 1 . . ]

%e : O--o--o--o--o

%e : .--o

%e :

%e : 6: [ 0 1 2 3 3 2 ] [ 1 2 2 . . . ]

%e : O--o--o--o

%e : .--o

%e : .--o

%e :

%e : 7: [ 0 1 2 3 3 1 ] [ 2 1 2 . . . ]

%e : O--o--o--o

%e : .--o

%e : .--o

%e :

%e : 8: [ 0 1 2 3 2 3 ] [ 1 2 1 . 1 . ]

%e : O--o--o--o

%e : .--o--o

%e :

%e : 9: [ 0 1 2 3 2 1 ] [ 2 2 1 . . . ]

%e : O--o--o--o

%e : .--o

%e : .--o

%e :

%e : 10: [ 0 1 2 3 1 2 ] [ 2 1 1 . 1 . ]

%e : O--o--o--o

%e : .--o--o

%e :

%e : 11: [ 0 1 2 2 1 2 ] [ 2 2 . . 1 . ]

%e : O--o--o

%e : .--o

%e : .--o--o

%e :

%e (End)

%p 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;

%p N := 40: G001190 := add(A001190(n)*x^n,n=0..N);

%p spec := [S,{S=Union(Z,Prod(Z,Set(S,card=2)))},unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);

%p # alternative Maple program:

%p a:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,

%p (t-> t*(1-t)/2)(a(n/2)))+add(a(i)*a(n-i), i=1..n/2))

%p end:

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Aug 28 2017

%t 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 *)

%t 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 *)

%t 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 *)

%o (PARI) {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 */

%o (PARI) {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 */

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A001190(n):

%o if n <= 1: return n

%o m = n//2 + n % 2

%o 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

%Y Cf. A000108, A001699, A002658, A003214, A006894, A006961, A088325.

%Y Cf. A086317, A086318, A240943.

%Y Cf. A292553, A292554, A292555, A292556.

%Y Column k=2 of A292085 and of A299038.

%Y Column k=1 of A319539 and of A319541.

%K easy,core,nonn,nice,eigen

%O 0,5

%A _N. J. A. Sloane_