OFFSET
0,3
COMMENTS
a(n) is the number of forests of rooted labeled trees with height exactly one. Equivalently, the number of idempotent mappings from {1,2,...,n} into {1,2,...,n} where each fixed point has at least one (other than itself) element mapped to it. See the second summation formula provided by Vladeta Jovovic with conditions on k, the number of fixed points. - Geoffrey Critzer, Sep 20 2012
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 39
Vaclav Kotesovec, Asymptotic solution of the equations using the Lambert W-function
FORMULA
a(n) = Sum_{k=0..n} binomial(n, k)*(n-k-1)^k. - Vladeta Jovovic, Apr 12 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*k!*Stirling2(n-k, k). - Vladeta Jovovic, Dec 19 2004
a(n) ~ exp((1-r*(n+r))/(1+r)) * n^(n+1/2) * sqrt(1+r) / (r^n * sqrt((1+r)^3 + n*(1+3*r+r^2))), where r satisfies exp(r)*(1+r) - (1+n)/r = 1. - Vaclav Kotesovec, Aug 04 2014
(a(n)/n!)^(1/n) ~ exp(1/(2*LambertW(sqrt(n)/2))) / (2*LambertW(sqrt(n)/2)). - Vaclav Kotesovec, Aug 06 2014
G.f.: Sum_{k>=0} x^k / (1 - (k-1)*x)^(k+1). - Seiichi Manyama, Aug 29 2022
MAPLE
spec := [S, {S=Set(Tree), Tree=Prod(Z, Set(Z, 0 < card))}, labeled]: seq(combstruct[count](spec, size=n), n=0..20);
MATHEMATICA
nn=20; Range[0, nn]! CoefficientList[Series[Exp[x(Exp[x]-1)], {x, 0, nn}], x] (* Geoffrey Critzer, Sep 20 2012 *)
PROG
(PARI) my(x='x+O('x^30)); Vec(serlaplace( exp(x*exp(x)-x) )) \\ G. C. Greubel, Nov 15 2017
(PARI) my(N=30, x='x+O('x^N)); Vec(sum(k=0, N, x^k/(1-(k-1)*x)^(k+1))) \\ Seiichi Manyama, Aug 29 2022
(Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( Exp(x*Exp(x)-x) )); [Factorial(n-1)*b[n]: n in [1..m-1]]; // G. C. Greubel, May 13 2019
(Sage) m = 30; T = taylor(exp(x*exp(x)-x), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # G. C. Greubel, May 13 2019
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
STATUS
approved