

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

Table of n, a(n) for n=0..20.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 96


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.
Cf. A226572.
Sequence in context: A006505 A004637 A191296 * A306498 A195201 A233403
Adjacent sequences: A052523 A052524 A052525 * A052527 A052528 A052529


KEYWORD

easy,nonn


AUTHOR

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


EXTENSIONS

Edited by Dean Hickerson, Jun 07 2006


STATUS

approved



