A052526 Number of labeled rooted trees with n leaves in which the degrees of the root and all internal nodes are >= 3.
0, 0, 0, 1, 1, 11, 36, 372, 2311, 26252, 243893, 3173281, 38916879, 583922418, 8808814262, 151530476047, 2694658394356, 52607648010035, 1072975736368359, 23516009286474813, 539838208864165036
Offset: 0
Examples
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.
Links
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 96
Crossrefs
Programs
-
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 *) -
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 */
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
Extensions
Edited by Dean Hickerson, Jun 07 2006
Comments