A108919 Number of series-reduced labeled trees with n nodes.

1, 0, 1, 1, 13, 51, 601, 4803, 63673, 775351, 12186061, 196158183, 3661759333, 72413918019, 1583407093633, 36916485570331, 929770285841137, 24904721121298671, 711342228666833173, 21502519995056598639, 687345492498807434461, 23135454269839313430715, 818568166383797223246601, 30357965273255025673685091

Offset: 1

Author

Vladeta Jovovic, Jul 20 2005

Keywords

• easy
• nonn

Comments

"Series-reduced" means that if the tree is rooted at 1, then there is no node with just a single child.

Callan points out that A002792 is an incorrect version of this sequence. - Joerg Arndt, Jul 01 2014

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..415
• David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], 2014.

Crossrefs

The rooted version is A060356.

Cf. A000311, A000669, A001678, A292504, A316651, A316652, A318231, A318813, A330465, A330624, A352410.

Programs

Mathematica

f[n_] := Sum[(-1)^(n-k)*n!/k!*Binomial[n-1, k-1]*k^(k-1), {k, n}]/n; Table[ f[n], {n, 20}] (* Robert G. Wilson v, Jul 21 2005 *)

PARI

a(n) = { 1/n * sum(k=1, n, (-1)^(n-k) * binomial(n,k) * (n-1)!/(k-1)! * k^(k-1) ); } \\ Joerg Arndt, Aug 28 2014

Formula

a(n) = A060356(n)/n.

1 = Sum_{n>=0} a(n+1)*(exp(x)-x)^(-n-1)*x^n/n!.

E.g.f.: A(x) = Sum_{n>=0} a(n+1)*x^n/n! satisfies A(x) = exp(x*A(x))/(1+x). - Olivier Gérard, Dec 31 2013 (edited by Gus Wiseman, Dec 31 2019)

E.g.f.: -Integral (LambertW(-x/(1 + x))/x) dx. - Ilya Gutkovskiy, Jul 01 2020

Extensions

More terms from Robert G. Wilson v, Jul 21 2005

New name (from A002792) by Joerg Arndt, Aug 28 2014

Offset corrected by Gus Wiseman, Dec 31 2019