login
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
OFFSET
0,6
COMMENTS
Old name was "Non-planar labeled trees with neither unary nor binary nodes". "Non-planar" presumably indicates that we are only concerned with the abstract tree, not with a particular embedding in the plane.
FORMULA
E.g.f.: RootOf(2*exp(Z)-4*Z+2*x-2-Z^2)-x.
E.g.f.: reversed[1+2*x+1/2*x^2-exp(x)]-x, a(n):=sum(k=1..n-1, (n+k-1)!*sum(j=1..k, 1/(k-j)!*sum(l=0..j, (-1)^(l)*sum(i=0..l, (2^(l-2*i)*stirling2(n+j-i-l-1,j-l))/(i!*(l-i)!*(n+j-i-l-1)!))))). [Vladimir Kruchinin, Sep 25 2012]
a(n) ~ n^(n-1) / (sqrt(c-1) * exp(n) * (c^2/2 - c - 1)^(n-1/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 (* _Jean-François Alcover, Sep 25 2012, from first e.g.f. *)
CoefficientList[InverseSeries[Series[1+2*x+1/2*x^2-E^x, {x, 0, 20}], x]-x, x] * Range[0, 20]! (* Vaclav Kotesovec, May 04 2015 *)
PROG
(Maxima) a(n):=sum((n+k-1)!*sum(1/(k-j)!*sum((-1)^(l)*sum((2^(l-2*i)*stirling2(n+j-i-l-1, j-l))/(i!*(l-i)!*(n+j-i-l-1)!), i, 0, l), l, 0, j), j, 1, k), k, 1, n-1); /* Vladimir Kruchinin, Sep 25 2012 */
CROSSREFS
Unlabeled trees of this type are counted by A052525. Labeled trees in which the degrees of non-leaf nodes are >= 2 are counted by A000311.
Cf. A226572.
Sequence in context: A006505 A004637 A191296 * A366921 A306498 A195201
KEYWORD
easy,nonn,changed
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
EXTENSIONS
Edited by Dean Hickerson, Jun 07 2006
STATUS
approved