login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001190 Wedderburn-Etherington numbers: unlabeled binary rooted trees (every node has out-degree 0 or 2) with n endpoints (and 2n-1 nodes in all).
(Formerly M0790 N0298)
57

%I M0790 N0298

%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 out-degree 0 or 2) with n endpoints (and 2n-1 nodes in all).

%C Also n-node binary rooted trees (every node has out-degree <= 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 out-degree 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).

%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

%D Fatemeh Bagherzadeh, M Bremner, S Madariaga, Jordan Trialgebras and Post-Jordan Algebras, arXiv preprint arXiv:1611.01214, 2016

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

%D S. 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 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.52.

%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, 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 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 H. Bottomley, <a href="/A001190/a001190.gif">Illustration of initial terms</a>

%H M. Bremner, S. Madariaga, 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 P. 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 Sean Cleary, M. Fischer, R. C. Griffiths, 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, 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, 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 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 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, 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 S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/otter/otter.html">Otter's Tree Enumeration Constants</a> [Broken link]

%H P. Flajolet and R. 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 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://www.math.sc.edu/~czabarka/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. Southern Calif., 2012.

%H M. Konvalinka, 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, 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 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 F. Sievers, G. M. Hughes, 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 out-degrees (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 n = 32; c[0] = 0; f[x_] = Sum[c[k]*x^k, {k, 0, n}]; eq[0] = Rest[ Thread[ CoefficientList[(-2x + 2f[x] - f[x]^2 - f[x^2])/2, x] == 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}]; Table[c[k], {k, 0, n}] /. Flatten[ Table[s[k], {k, 1, n}]] (* _Jean-François Alcover_, Jul 22 2011 *)

%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 */

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

%K easy,core,nonn,nice,eigen

%O 0,5

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 19 08:51 EST 2017. Contains 294923 sequences.