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,5

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.

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

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

Prog

(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

Crossrefs

The rooted version is A060356.

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

Sequence in context: A022283 A135971 A146143 * A002792 A183941 A022673

Adjacent sequences: A108916 A108917 A108918 * A108920 A108921 A108922

Keyword

easy,nonn

Author

Vladeta Jovovic, Jul 20 2005

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

Status

approved