A052524 Number of ordered labeled rooted trees on n nodes with non-leaf nodes having more than two children.

0, 1, 0, 6, 24, 480, 5760, 126000, 2580480, 69310080, 1959552000, 64505548800, 2292022656000, 90366525849600, 3843167789260800, 177248722210560000, 8758468152225792000, 463225965106544640000, 26058454876652470272000

Offset

0,4

Comments

The correspondence between rooted trees and dissection of (n+1)-gon as in A046736 is just like the case for Catalan numbers and binary trees.

Links

G. C. Greubel, Table of n, a(n) for n = 0..370

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 94

Formula

a(n) = n! * A046736(n+1) for n>0.

E.g.f.: A(x)=sum_{n>0} a(n)*x^n/n! satisfies A(x)-A(x)^2-A(x)^3 = x*(1-A(x)).

Recurrence: a(0)=0, a(1)=1, a(2)=0, a(3)=6, 8*n*(n+1)*(n+2)*(1-2*n)*a(n) +6*(13*n+10)*(2*n+1)*(n+2)*a(n+1) -24*(2*n+5)*(4*n+7)*a(n+2) -4*(19*n+40)*a(n+3) +35*a(n+4) = 0

a(n) ~ n^(n-1) * sqrt(r*(1-s)/(2+6*s)) / (exp(n) * r^n), where r = 0.2933671276754004454... is the root of the equation 5-8*r-32*r^2+4*r^3 = 0 and s = 0.40303171676268477587... is the root of the equation 1-2*s-2*s^2+2*s^3 = 0. - Vaclav Kotesovec, Jan 08 2014

Maple

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

Mathematica

CoefficientList[InverseSeries[Series[1 + 1/(x-1) + 2*x + x^2, {x, 0, 20}], x], x] * Range[0, 20]! (* Vaclav Kotesovec, Jan 08 2014 *)

Prog

(PARI) a(n)=if(n<1, 0, n!*polcoeff(serreverse((x-x^2-x^3)/(1-x) + O(x^(n+2))), n))

Crossrefs

Cf. A046736.

Sequence in context: A128614 A285018 A139240 * A267032 A234635 A036284

Adjacent sequences: A052521 A052522 A052523 * A052525 A052526 A052527

Keyword

easy,nonn

Author

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

Status

approved