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

 

Logo


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

%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 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,changed

%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 September 24 04:14 EDT 2017. Contains 292402 sequences.