A000444 Number of partially labeled rooted trees with n nodes (3 of which are labeled).

9, 64, 326, 1433, 5799, 22224, 81987, 293987, 1031298, 3555085, 12081775, 40576240, 134919788, 444805274, 1455645411, 4733022100, 15302145060, 49223709597, 157629612076, 502736717207, 1597541346522, 5059625685739, 15975936032821, 50304490599602

Offset: 3

Author

N. J. A. Sloane

Keywords

• nonn

References

• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 134.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 3..650
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Column k=3 of A008295.

Cf. A042977.

Programs

Maple

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-2)^3*(9-8*B(n-2)+2*B(n-2)^2)/(1-B(n-2))^5, x=0, n+1), x,n): seq(a(n), n=3..24); # Alois P. Heinz, Aug 21 2008

Mathematica

b[n_] := b[n] = If[n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[b[n+1-j*k], {j, 1, Quotient[n, k]}]; B[n_] := B[n] = Sum [b[k]*x^k, {k, 1, n}]; a[n_] := Coefficient[Series[B[n-2]^3*(9 - 8*B[n-2] + 2*B[n-2]^2)/(1 - B[n-2])^5, {x, 0, n+1}], x, n]; Table[a[n], {n, 3, 30}] (* Jean-François Alcover, Mar 10 2014, after Alois P. Heinz *)

Formula

G.f.: A(x) = B(x)^3*(9-8*B(x)+2*B(x)^2)/(1-B(x))^5, where B(x) is g.f. for rooted trees with n nodes, cf. A000081.

a(n) ~ c * d^n * n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.244665117500618173509... . - Vaclav Kotesovec, Sep 11 2014

Extensions

More terms from Vladeta Jovovic, Oct 19 2001