A050381 Number of series-reduced planted trees with n leaves of 2 colors.

2, 3, 10, 40, 170, 785, 3770, 18805, 96180, 502381, 2667034, 14351775, 78096654, 429025553, 2376075922, 13252492311, 74372374366, 419651663108, 2379399524742, 13549601275893, 77460249369658, 444389519874841

Offset

1,1

Comments

Consider the free algebraic system with two commutative associative operators (x+y) and (x*y) and two generators A,B. The number of elements with n occurrences of the generators is 2*a(n) if n>1, and the number of generators if n=1. - Michael Somos, Aug 07 2017

From Gus Wiseman, Feb 07 2020: (Start)

Also the number of semi-lone-child-avoiding rooted trees with n leaves. Semi-lone-child-avoiding means there are no vertices with exactly one child unless that child is an endpoint/leaf. For example, the a(1) = 2 through a(3) = 10 trees are:

o (oo) (ooo)

(o) (o(o)) (o(oo))

((o)(o)) (oo(o))

((o)(oo))

(o(o)(o))

(o(o(o)))

((o)(o)(o))

((o)(o(o)))

(o((o)(o)))

((o)((o)(o)))

(End)

Links

Andrew Howroyd, Table of n, a(n) for n = 1..500

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).

F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From N. J. A. Sloane, Dec 22 2012

N. J. A. Sloane, Transforms

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Index entries for sequences related to rooted trees

Formula

Doubles (index 2+) under EULER transform.

Product_{k>=1} (1-x^k)^-a(k) = 1 + a(1)*x + Sum_{k>=2} 2*a(k)*x^k. - Michael Somos, Aug 07 2017

a(n) ~ c * d^n / n^(3/2), where d = 6.158893517087396289837838459951206775682824030495453326610366016992093939... and c = 0.1914250508201011360729769525164141605187995730026600722369002... - Vaclav Kotesovec, Aug 17 2018

Example

For n=2, the 2*a(2) = 6 elements are: A+A, A+B, B+B, A*A, A*B, B*B. - Michael Somos, Aug 07 2017

Mathematica

terms = 22;
B[x_] = x O[x]^(terms+1);
A[x_] = 1/(1 - x + B[x])^2;
Do[A[x_] = A[x]/(1 - x^k + B[x])^Coefficient[A[x], x, k] + O[x]^(terms+1) // Normal, {k, 2, terms+1}];
Join[{2}, Drop[CoefficientList[A[x], x]/2, 2]] (* Jean-François Alcover, Aug 17 2018, after Michael Somos *)
slaurte[n_]:=If[n==1, {o, {o}}, Join@@Table[Union[Sort/@Tuples[slaurte/@ptn]], {ptn, Rest[IntegerPartitions[n]]}]];
Table[Length[slaurte[n]], {n, 10}] (* Gus Wiseman, Feb 07 2020 *)

Prog

(PARI) {a(n) = my(A, B); if( n<2, 2*(n>0), B = x * O(x^n); A = 1 / (1 - x + B)^2; for(k=2, n, A /= (1 - x^k + B)^polcoeff(A, k)); polcoeff(A, n)/2)}; /* Michael Somos, Aug 07 2017 */

Crossrefs

Column 2 of A319254.

Cf. A029856, A031148.

Lone-child-avoiding rooted trees with n leaves are A000669.

Lone-child-avoiding rooted trees with n vertices are A001678.

The locally disjoint case is A331874.

Semi-lone-child-avoiding rooted trees with n vertices are A331934.

Matula-Goebel numbers of these trees are A331935.

Cf. A000081, A005804, A141268, A196545, A291636, A316697, A330465, A331872, A331933, A331964.

Sequence in context: A003048 A008980 A064183 * A129716 A032293 A059733

Adjacent sequences: A050378 A050379 A050380 * A050382 A050383 A050384

Keyword

nonn

Author

Christian G. Bower, Nov 15 1999

Status

approved