A052855 -id:A052855 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 16, 29, 54, 102, 194, 375, 730, 1434, 2837, 5650, 11311, 22767, 46023, 93422, 190322, 389037, 797613, 1639878, 3380099, 6983484, 14459570, 29999618, 62357426, 129843590, 270807835, 565674584, 1183301266, 2478624060, 5198504694, 10916110768, 22948299899

Offset: 0

Paul D. Hanna, Oct 26 2011

nonn

For n>=1, a(n) is the number of rooted trees (see A000081) with n non-root nodes where non-root nodes cannot have out-degree 1, see the note by David Callan and the example. Imposing the condition also for the root node gives A001678. - Joerg Arndt, Jun 28 2014
Compare definition to G(x) = exp( Sum_{n>=1} G(x^n)*x^n/n ), where G(x) is the g.f. of A000081, the number of rooted trees with n nodes.
Number of forests of lone-child-avoiding rooted trees with n unlabeled vertices. - Gus Wiseman, Feb 03 2020

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 9*x^6 + 16*x^7 + 29*x^8 +...
where
log(A(x)) = A(x)/(1+x)*x + A(x^2)/(1+x^2)*x^2/2 + A(x^3)/(1+x^3)*x^3/3 +...
The coefficients in A(x)/(1+x) begin:
[1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127, 248, 482, 952, 1885, 3765, ...]
(this is, up to offset, A001678),
from which g.f. A(x) may be generated by the Euler transform:
A(x) = 1/((1-x)^1*(1-x^2)^0*(1-x^3)^1*(1-x^4)^1*(1-x^5)^2*(1-x^6)^3*(1-x^7)^6*(1-x^8)^10*(1-x^9)^19*(1-x^10)^35*...).
From _Joerg Arndt_, Jun 28 2014: (Start)
The a(6) = 9 rooted trees with 6 non-root nodes as described in the comment are:
:           level sequence       out-degrees (dots for zeros)
:     1:  [ 0 1 2 3 3 3 2 ]    [ 1 2 3 . . . . ]
:  O--o--o--o
:        .--o
:        .--o
:     .--o
:
:     2:  [ 0 1 2 3 3 2 2 ]    [ 1 3 2 . . . . ]
:  O--o--o--o
:        .--o
:     .--o
:     .--o
:
:     3:  [ 0 1 2 3 3 2 1 ]    [ 2 2 2 . . . . ]
:  O--o--o--o
:        .--o
:     .--o
:  .--o
:
:     4:  [ 0 1 2 2 2 2 2 ]    [ 1 5 . . . . . ]
:  O--o--o
:     .--o
:     .--o
:     .--o
:     .--o
:
:     5:  [ 0 1 2 2 2 2 1 ]    [ 2 4 . . . . . ]
:  O--o--o
:     .--o
:     .--o
:     .--o
:  .--o
:
:     6:  [ 0 1 2 2 2 1 1 ]    [ 3 3 . . . . . ]
:  O--o--o
:     .--o
:     .--o
:  .--o
:  .--o
:
:     7:  [ 0 1 2 2 1 2 2 ]    [ 2 2 . . 2 . . ]
:  O--o--o
:     .--o
:  .--o--o
:     .--o
:
:     8:  [ 0 1 2 2 1 1 1 ]    [ 4 2 . . . . . ]
:  O--o--o
:     .--o
:  .--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 1 1 ]    [ 6 . . . . . . ]
:  O--o
:  .--o
:  .--o
:  .--o
:  .--o
:  .--o
(End)
From _Gus Wiseman_, Jan 22 2020: (Start)
The a(0) = 1 through a(6) = 9 rooted trees with n + 1 nodes where non-root vertices cannot have out-degree 1:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)    (oooooo)
                ((oo))  ((ooo))  ((oooo))   ((ooooo))
                        (o(oo))  (o(ooo))   (o(oooo))
                                 (oo(oo))   (oo(ooo))
                                 ((o(oo)))  (ooo(oo))
                                            ((o(ooo)))
                                            ((oo)(oo))
                                            ((oo(oo)))
                                            (o(o(oo)))
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
David Callan, Rooted trees with no out-degree = 1, (7-July-2014).
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A052855, A246403.
The labeled version is A254382.
Unlabeled rooted trees are A000081.
Lone-child-avoiding rooted trees are A001678(n+1).
Topologically series-reduced rooted trees are A001679.
Labeled lone-child-avoiding rooted trees are A060356.
Cf. A000669, A004111, A108919, A291636, A330951, A331488, A331934.

with(numtheory):
b:= proc(n) b(n):= `if`(n=0, 1, a(n)-b(n-1)) end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(
       d*b(d-1), d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 02 2014

b[n_] := b[n] = If[n==0, 1, a[n] - b[n-1]];
a[n_] := a[n] = If[n==0, 1, Sum[Sum[d*b[d-1], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 21 2017, after Alois P. Heinz *)
urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],FreeQ[Z@@#,{}]&]],{n,10}] (* _Gus Wiseman, Jan 22 2020 *)

{a(n)=local(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)}

Euler transform of coefficients in A(x)/(1+x), where g.f. A(x) = Sum_{n>=0} a(n)*x^n.
a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711..., c = 1.3437262442171062526771597... . - Vaclav Kotesovec, Sep 03 2014
a(n) = A001678(n + 1) + A001678(n + 2). - Gus Wiseman, Jan 22 2020
Euler transform of A001678(n + 1). - Gus Wiseman, Feb 03 2020

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

Original entry on oeis.org

1, 1, 4, 14, 54, 206, 823, 3312, 13619, 56643, 238569, 1014443, 4352038, 18809992, 81843021, 358186642, 1575810191, 6965004499, 30914431131, 137736012285, 615785575785, 2761693248028, 12421390811559, 56016050571825, 253228531426237

Offset: 0

Seiichi Manyama, Jun 09 2023

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A052855, A198518, A363546, A363580, A363581.

Cf. A362389.

seq(n) = my(A=1); for(i=1, n, A=exp(sum(k=1, i, subst(A, x, x^k)*x^k/(k*(1-2*x^k)))+x*O(x^n))); Vec(A);

A(x) = (1 - 2*x) * B(x) where B(x) is the g.f. of A362389.

a(n) = A362389(n) - 2*A362389(n-1) for n > 0.

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

Original entry on oeis.org

1, 1, 5, 22, 105, 497, 2431, 11976, 59928, 302816, 1545660, 7955132, 41255625, 215378364, 1131134574, 5972272636, 31684600709, 168824599282, 903080385252, 4848038120323, 26110774945462, 141048622038068, 764026532321068, 4149020129689451

Offset: 0

Seiichi Manyama, Jun 09 2023

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A052855, A198518, A363545, A363580, A363581.

Cf. A363541.

seq(n) = my(A=1); for(i=1, n, A=exp(sum(k=1, i, subst(A, x, x^k)*x^k/(k*(1-3*x^k)))+x*O(x^n))); Vec(A);

A(x) = (1 - 3*x) * B(x) where B(x) is the g.f. of A363541.

a(n) = A363541(n) - 3*A363541(n-1) for n > 0.

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

Original entry on oeis.org

1, 1, 0, 2, 0, 2, 1, 6, -2, 11, -1, 30, -21, 76, -60, 223, -245, 653, -817, 2031, -2935, 6521, -10067, 21455, -35425, 72152, -123756, 246752, -436854, 855852, -1546777, 3001811, -5513604, 10630676, -19747742, 37949424, -71115077, 136415279, -257301742, 493313335

Offset: 0

Seiichi Manyama, Jun 10 2023

sign

Cf. A052855, A198518, A363545, A363546, A363581.

Cf. A363578.

seq(n) = my(A=1); for(i=1, n, A=exp(sum(k=1, i, subst(A, x, x^k)*x^k/(k*(1+2*x^k)))+x*O(x^n))); Vec(A);

A(x) = (1 + 2*x) * B(x) where B(x) is the g.f. of A363578.

a(n) = A363578(n) + 2*A363578(n-1) for n > 0.

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

Original entry on oeis.org

1, 1, -1, 4, -6, 11, -22, 62, -151, 353, -867, 2261, -5861, 15178, -39878, 106099, -283823, 763248, -2065453, 5621318, -15368682, 42190539, -116281176, 321647511, -892617214, 2484583934, -6935203356, 19408586888, -54447145335, 153084848495

Offset: 0

Seiichi Manyama, Jun 10 2023

sign

Cf. A052855, A198518, A363545, A363546, A363580.

Cf. A363579.

seq(n) = my(A=1); for(i=1, n, A=exp(sum(k=1, i, subst(A, x, x^k)*x^k/(k*(1+3*x^k)))+x*O(x^n))); Vec(A);

A(x) = (1 + 3*x) * B(x) where B(x) is the g.f. of A363579.

a(n) = A363579(n) + 3*A363579(n-1) for n > 0.

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

Original entry on oeis.org

1, 1, 4, 13, 47, 168, 635, 2420, 9460, 37445, 150309, 609568, 2495710, 10298332, 42793974, 178910161, 752034697, 3176346092, 13473881397, 57378127986, 245205968960, 1051257068207, 4520229295852, 19488595397346, 84231899582543, 364893870958302

Offset: 0

Seiichi Manyama, Jun 09 2023

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A052855, A363548.

Cf. A029857, A363545.

seq(n) = my(A=1); for(i=1, n, A=exp(sum(k=1, i, subst(A, x, x^k)*x^k/(k*(1-x^k)^2))+x*O(x^n))); Vec(A);

A(x) = (1 - x)^2 * (B(x)/x - 2) where B(x) is the g.f. of A029857.

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

Original entry on oeis.org

1, 1, 5, 19, 79, 326, 1414, 6198, 27794, 126233, 580885, 2700135, 12665756, 59869222, 284919675, 1364009722, 6564545500, 31742029545, 154134718727, 751316355122, 3674923035139, 18031965040197, 88734141475113, 437813286219942, 2165445447313147

Offset: 0

Seiichi Manyama, Jun 09 2023

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A052855, A363547.

Cf. A363507, A363546.

seq(n) = my(A=1); for(i=1, n, A=exp(sum(k=1, i, subst(A, x, x^k)*x^k/(k*(1-x^k)^3))+x*O(x^n))); Vec(A);

A(x) = (1 - x)^3 * B(x) where B(x) is the g.f. of A363507.

a(n) = Sum_{k=0..3} (-1)^k * binomial(3,k) * A363507(n-k).

A304914 Number of trees with positive integer edge labels summing to n.

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 55, 146, 415, 1212, 3653, 11246, 35346, 112750, 364714, 1193202, 3943557, 13148575, 44186841, 149536376, 509270554, 1744342614, 6005869285, 20777091355, 72192026878, 251848377631, 881865312582, 3098564357293, 10922162622233, 38614641384893

Offset: 0

Andrew Howroyd, May 20 2018

nonn

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

Row sums of A303842.

Cf. A052855.

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

\\ here b(n) is A052855 as series
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n)={my(v=[1]); for(i=2, n, v=concat([1], v + EulerT(v))); Ser(v)*(1-x)}
seq(n)={my(g=b(n)); Vec(g + (subst(g,x,x^2) - g^2)*x/(2*(1-x)))}

G.f.: g(x) + (g(x^2) - g(x)^2)*x/(2*(1-x)) where g(x) is the g.f. of A052855.

A052870 First differences of A052829.

Original entry on oeis.org

1, 1, 2, 6, 15, 44, 128, 386, 1179, 3679, 11601, 37030, 119262, 387325, 1266647, 4168264, 13791565, 45856091, 153134306, 513403575, 1727395042, 5830866601, 19740613869, 67014421326, 228066659185, 777961702283, 2659398743509, 9109015516017, 31258117755635

Offset: 0

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

Old name was: A simple grammar.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 841

Cf. A052829, A052855.

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

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

More terms from Alois P. Heinz, Mar 16 2016

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A304914 Number of trees with positive integer edge labels summing to n.

Views

Author