login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 "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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 7 07:00 EST 2023. Contains 360112 sequences. (Running on oeis4.)