A029856 -id:A029856 - cp's OEIS frontend

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

Christian G. Bower, Nov 15 1999

nonn

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)

			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

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

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.

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

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

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

A036249 Number of rooted trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Original entry on oeis.org

0, 1, 2, 5, 13, 37, 108, 332, 1042, 3360, 11019, 36722, 123875, 422449, 1453553, 5040816, 17599468, 61814275, 218252584, 774226549, 2758043727, 9862357697, 35387662266, 127374191687, 459783039109, 1664042970924, 6037070913558, 21951214425140, 79981665585029

Offset: 0

Christian G. Bower, Nov 15 1998

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1717
Håvard Berland, Brynjulf Owren and Bård Skaflestad, B-series and order conditions for exponential integrators, 2004. See p. 6.
F. Chapoton, F. Hivert, and J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
F. Chapoton, F. Hivert, and J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, Journal of Algebra, 465 (2016), 322-355.
Timothy Y. Chow and Mark G. Tiefenbruck, The Latin Tableau Conjecture, 2024. See p. 11.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 768
Index entries for sequences related to rooted trees

Essentially the same as A029856. Cf. A048802. Row sums of A303911.

b:= proc(n) option remember; `if`(n=0, 1, add(b(n-j)*
      add(d*a(d), d=numtheory[divisors](j)), j=1..n)/n)
    end:
a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+b(n-1)) end:
seq(a(n), n=0..35);  # Alois P. Heinz, Jun 13 2018

max = 27; A[] = 1; Do[A[x] = x*Exp[Sum[(A[x^k] + x^k)/k + O[x]^n, {k, 1, n}]] // Normal, {n, 1, max}]; CoefficientList[A[x] + O[x]^max, x] (* Jean-François Alcover, May 25 2018 *)

{a(n)=local(A=x+x*O(x^n));for(i=1,n, A=x*exp(sum(m=1,n,(subst(A,x,x^m)+x^m)/m)));polcoeff(A,n,x)} \\ Paul D. Hanna, Oct 19 2005

G.f. satisfies: A(x) = x*exp( Sum_{n>=1} (A(x^n) + x^n)/n ). - Paul D. Hanna, Oct 19 2005
If b(n) is the Euler transform of a(n), A052855, then a(n+1) = a(n) + b(n). - Franklin T. Adams-Watters, Mar 09 2006
G.f.: (x/(1 - x)) * Product_{n>=1} 1/(1 - x^n)^a(n). - Ilya Gutkovskiy, Jun 28 2021

A038049 Number of labeled rooted trees with 2-colored leaves.

Original entry on oeis.org

2, 4, 24, 224, 2880, 47232, 942592, 22171648, 600698880, 18422374400, 630897721344, 23864653578240, 988197253808128, 44460603225407488, 2159714024218951680, 112652924603290615808, 6280048587936003784704, 372616014329572403183616, 23445082059018189741752320

Offset: 1

Christian G. Bower, Jan 04 1999

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 185 (3.1.83)

Alois P. Heinz, Table of n, a(n) for n = 1..150
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A000169, A029856, A038050, A038054, A088789.

a:= n-> add(binomial(n, k)*(n-k)^(n-1), k=0..n):
seq(a(n), n=1..20);  # Alois P. Heinz, Nov 30 2012

Table[n!*Sum[2^j/j!*StirlingS2[n-1,n-j],{j,1,n}],{n,1,20}] (* Vaclav Kotesovec, Nov 30 2012 *)

Divides by n and shifts left under exponential transform.
E.g.f.: A(x) = x-LambertW(-x*exp(x)). - Vladeta Jovovic, Mar 08 2003
a(n) = Sum_{k=0..n} (binomial(n, k)*(n-k)^(n-1)).
A(x) = 2*compositional inverse of 2*x/(1+exp(2*x)). - Peter Bala, Oct 14 2011
a(n) ~ n^(n-1) * sqrt((1+LambertW(1/e))) / (e*LambertW(1/e))^n. - Vaclav Kotesovec, Nov 30 2012

A052855 Number of forests of rooted trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Original entry on oeis.org

1, 1, 3, 8, 24, 71, 224, 710, 2318, 7659, 25703, 87153, 298574, 1031104, 3587263, 12558652, 44214807, 156438309, 555973965, 1983817178, 7104313970, 25525304569, 91986529421, 332408847422, 1204259931815, 4373027942634, 15914143511582, 58030451159889

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Euler transform of A036249 (as well as first differences thereof). - Franklin T. Adams-Watters, Feb 08 2006

Alois P. Heinz, Table of n, a(n) for n = 0..1717
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 823

First differences of A036249 and A029856.

spec := [S,{B=Sequence(Z,1 <= card),S=Set(C),C=Prod(B,S)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

max = 26; A[] = 1; Do[A[x] = Exp[Sum[A[x^k]/(1 - x^k)*x^k/k + O[x]^n, {k, 1, n}]] // Normal, {n, 1, max}]; CoefficientList[A[x] + O[x]^max, x] (* Jean-François Alcover, May 25 2018 *)

{a(n)=my(A=1+x);for(i=1,n,A=exp(sum(m=1,n,subst(A/(1-x),x,x^m+x*O(x^n))*x^m/m)));polcoeff(A,n)} /* Paul D. Hanna, Oct 26 2011 */

G.f. satisfies A(x) = exp( Sum_{n>=1} A(x^n)/(1-x^n) * x^n/n ). - Paul D. Hanna, Oct 26 2011

G.f.: A(x) = Sum_{k>=0} a(k) * x^k = 1/Product_{j>=1} Product_{k>=0} (1-x^(j+k))^a(k). - Seiichi Manyama, Jun 07 2023

More terms from Franklin T. Adams-Watters, Feb 08 2006

A029857 Number of rooted trees with 3-colored leaves.

Original entry on oeis.org

3, 3, 9, 28, 94, 328, 1197, 4486, 17235, 67429, 267932, 1078003, 4383784, 17987897, 74385984, 309694232, 1297037177, 5460726214, 23098296648, 98113995068, 418335662448, 1789814398035, 7681522429474, 33061825858259, 142674028869587, 617180102839217

Offset: 1

Christian G. Bower

Alois P. Heinz, Table of n, a(n) for n = 1..500
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A000081, A029856, A038050.

with(numtheory): a:= proc(n) option remember; local d,j; if n<=1 then 3*n else (add(d*a(d), d=divisors(n-1)) +add(add(d*a(d), d=divisors(j)) *a(n-j), j=1..n-2))/ (n-1) fi end: seq(a(n), n=1..30); # Alois P. Heinz, Sep 06 2008

a[n_] := a[n] = If[n<=1, 3*n, (Sum[d*a[d], {d, Divisors[n-1]}] + Sum[Sum[ d*a[d], {d, Divisors[j]}]*a[n-j], {j, 1, n-2}])/(n-1)]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 21 2016 *)

Shifts left under Euler transform.
a(n) ~ c * d^n / n^(3/2), where d = 4.58859196701042554480382685... and c = 0.5102557157321640697473838... - Vaclav Kotesovec, Mar 29 2014
G.f. A(x) satisfies: A(x) = 2*x + x * exp( Sum_{k>=1} A(x^k) / k ). - Ilya Gutkovskiy, May 19 2023

A036251 Number of trees with 2-colored leaves.

Original entry on oeis.org

1, 2, 3, 3, 7, 14, 35, 85, 231, 633, 1845, 5461, 16707, 51945, 164695, 529077, 1722279, 5664794, 18813369, 62996850, 212533226, 721792761, 2466135375, 8471967938, 29249059293, 101440962296, 353289339927, 1235154230060

Offset: 0

Christian G. Bower, Nov 15 1998

nonn

Index entries for sequences related to trees

Essentially the same as A036250. Cf. A038054.

max = 30; B[] = 1; Do[B[x] = x*Exp[Sum[(B[x^k] + x^k)/k + O[x]^n, {k, 1, n}]] // Normal, {n, 1, max}]; A[x_] = 1 + x + x^2 + B[x] - B[x]^2/2 + B[x^2]/2; CoefficientList[A[x] + O[x]^max, x] (* Jean-François Alcover, Jan 28 2019 *)

G.f.: B(x) + B(x)^2/2 + B(x^2)/2 - B(x)*(B(x)-x), where B(x) is g.f. for A029856.

A318151 e-numbers of unlabeled rooted trees with empty leaves o[] allowed. A number n is in the sequence iff n = 2^(prime(y_1) * ... * prime(y_k)) for some k >= 0 and y_1, ..., y_k already in the sequence.

Original entry on oeis.org

1, 2, 4, 8, 16, 64, 128, 256, 512, 4096, 16384, 65536, 262144, 524288, 2097152, 16777216, 134217728, 268435456, 4294967296, 68719476736, 274877906944, 4398046511104, 281474976710656, 562949953421312, 9007199254740992, 18014398509481984, 72057594037927936

Offset: 1

Gus Wiseman, Aug 19 2018

nonn

If n = 1 let e(n) be the leaf symbol "o". Given a positive integer n > 1 we construct a unique orderless expression e(n) (as can be represented in functional programming languages such as Mathematica) with one atom by expressing n as a power of a number that is not a perfect power to a product of prime numbers: n = rad(x)^(prime(y_1) * ... * prime(y_k)) where rad = A007916. Then e(n) = e(x)[e(y_1), ..., e(y_k)]. For example, e(21025) = o[o[o]][o] because 21025 = rad(rad(1)^prime(rad(1)^prime(1)))^prime(1). The sequence consists of all numbers n such that e(n) contains no subexpressions in heads f[x_1, ..., x_k][y_1, ..., y_k] where k,j >= 0.

A subsequence of A000079.
Cf. A000081, A007916, A029856, A052409, A052410, A277576, A277996, A280000.
Cf. A317658, A316112, A317056, A317765, A317994, A318149, A318150, A318152, A318153.

A308227 G.f.: (x/(1 - x)) * Product_{k>=1} ((1 + x^k)/(1 - x^k))^a(k).

Original entry on oeis.org

1, 3, 11, 47, 217, 1065, 5453, 28789, 155633, 857207, 4793103, 27136555, 155249971, 896133487, 5212477023, 30522169103, 179777122393, 1064411910393, 6331361864657, 37817265028841, 226731778956181, 1363993567341257, 8231111557650837, 49812263080757845

Offset: 1

Ilya Gutkovskiy, May 16 2019

nonn

Cf. A029856, A036249, A052829, A073075.

a[n_] := a[n] = SeriesCoefficient[x/(1 - x) Product[((1 + x^k)/(1 - x^k))^a[k], {k, 1, n - 1}], {x, 0, n}]; Table[a[n], {n, 1, 24}]
terms = 24; A[] = 0; Do[A[x] = x Exp[Sum[2 A[x^(2 k - 1)]/(2 k - 1) + x^k/k, {k, 1, terms}]] + O[x]^(terms + 1) // Normal, terms + 1]; CoefficientList[A[x], x] // Rest

G.f. A(x) satisfies: A(x) = x * exp(Sum_{k>=1} 2*A(x^(2*k-1))/(2*k - 1) + x^k/k).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A036249 Number of rooted trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A038049 Number of labeled rooted trees with 2-colored leaves.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A052855 Number of forests of rooted trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A029857 Number of rooted trees with 3-colored leaves.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A036251 Number of trees with 2-colored leaves.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A318151 e-numbers of unlabeled rooted trees with empty leaves o[] allowed. A number n is in the sequence iff n = 2^(prime(y_1) * ... * prime(y_k)) for some k >= 0 and y_1, ..., y_k already in the sequence.

Views

Author

Keywords

Comments

Crossrefs

A308227 G.f.: (x/(1 - x)) * Product_{k>=1} ((1 + x^k)/(1 - x^k))^a(k).

Views

Author

Keywords

Crossrefs

Programs

Mathematica