

A052526


Number of labeled rooted trees with n leaves in which the degrees of the root and all internal nodes are >= 3.


4



0, 0, 0, 1, 1, 11, 36, 372, 2311, 26252, 243893, 3173281, 38916879, 583922418, 8808814262, 151530476047, 2694658394356, 52607648010035, 1072975736368359, 23516009286474813, 539838208864165036
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

Old name was "Nonplanar labeled trees with neither unary nor binary nodes". "Nonplanar" presumably indicates that we are only concerned with the abstract tree, not with a particular embedding in the plane.


LINKS



FORMULA

E.g.f.: RootOf(2*exp(Z)4*Z+2*x2Z^2)x.
E.g.f.: reversed[1+2*x+1/2*x^2exp(x)]x, a(n):=sum(k=1..n1, (n+k1)!*sum(j=1..k, 1/(kj)!*sum(l=0..j, (1)^(l)*sum(i=0..l, (2^(l2*i)*stirling2(n+jil1,jl))/(i!*(li)!*(n+jil1)!))))). [Vladimir Kruchinin, Sep 25 2012]
a(n) ~ n^(n1) / (sqrt(c1) * exp(n) * (c^2/2  c  1)^(n1/2)), where c = A226572 = LambertW(1, exp(2)) = 3.146193220620582585237... .  Vaclav Kotesovec, May 04 2015


EXAMPLE

For n=5 there are 2 unlabeled trees of this type. In the first, the root node has 5 children which are all leaves. In the second, the root has 3 children; 2 are leaves and 1 has 3 children which are leaves. The first has only one labeling; the second has binomial(5,2)=10 labelings. So a(5) = 1 + 10 = 11.


MAPLE

Non spec := [S, {B=Union(S, Z), S=Set(B, 3 <= card)}, labeled]: seq(combstruct[count](spec, size=n), n=0..20);


MATHEMATICA

ClearAll[a]; max = 20; Z[x_] := Sum[ a[k]*x^k, {k, 0, max}]; a[0] = 0; a[1] = 1/2; a[2] = 0; se = Normal[ Series[ (2*E^Z[x]  4*Z[x] + 2*x  2  Z[x]^2)  x, {x, 0, max}]]; sol = SolveAlways[se == 0, x] // First; A052526 = Join[{0, 0, 0}, Table[k!*2^k*a[k], {k, 3, max}]] /. sol (* _JeanFrançois Alcover, Sep 25 2012, from first e.g.f. *)
CoefficientList[InverseSeries[Series[1+2*x+1/2*x^2E^x, {x, 0, 20}], x]x, x] * Range[0, 20]! (* Vaclav Kotesovec, May 04 2015 *)


PROG

(Maxima) a(n):=sum((n+k1)!*sum(1/(kj)!*sum((1)^(l)*sum((2^(l2*i)*stirling2(n+jil1, jl))/(i!*(li)!*(n+jil1)!), i, 0, l), l, 0, j), j, 1, k), k, 1, n1); [Vladimir Kruchinin, Sep 25 2012]


CROSSREFS

Unlabeled trees of this type are counted by A052525. Labeled trees in which the degrees of nonleaf nodes are >= 2 are counted by A000311.


KEYWORD

easy,nonn


AUTHOR

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


EXTENSIONS



STATUS

approved



