A052512 Number of rooted labeled trees of height at most 2.

0, 1, 2, 9, 40, 205, 1176, 7399, 50576, 372537, 2936080, 24617131, 218521128, 2045278261, 20112821288, 207162957135, 2228888801056, 24989309310961, 291322555295904, 3524580202643155, 44176839081266360, 572725044269255661, 7668896804574138232, 105920137923940473079

Offset: 0

Author

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

Keywords

• easy
• nonn

Comments

Equivalently, number of mappings f from a set of n elements into itself such that f o f (f applied twice) is constant. - Robert FERREOL, Mar 05 2016

Examples

			From _Robert FERREOL_, Mar 05 2016: (Start)
For n = 3 the a(3) = 9 mappings from {a,b,c} into itself are:
f_1(a) = f_1(b) = f_1(c) = a
f_2(c) = b, f_2(b) = f_2(a) = a
f_3(b) = c, f_3(c) = f_3(a) = a
and 6 others, associated to b and c.
(End)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..300
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 58

Crossrefs

Cf. A000248 (forests with n nodes and height at most 1).

Cf. A000551.

Programs

Magma

m:=25; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( x*Exp(x*Exp(x)) )); [0] cat [Factorial(n)*b[n]: n in [1..m-1]]; // G. C. Greubel, May 13 2019

Maple

spec := [S,{S=Prod(Z,Set(T1)), T2=Z, T1=Prod(Z,Set(T2))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
# second Maple program:
a:= n-> n*add(binomial(n-1, k)*(n-k-1)^k, k=0..n-1);
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 15 2013

Mathematica

nn=20; a=x Exp[x]; Range[0,nn]! CoefficientList[Series[x Exp[a], {x,0,nn}], x] (* Geoffrey Critzer, Sep 19 2012 *)

PARI

N=33;  x='x+O('x^N);
egf=x*exp(x*exp(x));
v=Vec(serlaplace(egf));
vector(#v+1,n,if(n==1,0,v[n-1]))
/* Joerg Arndt, Sep 15 2012 */

Sage

m = 20; T = taylor(x*exp(x*exp(x)), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # G. C. Greubel, May 13 2019

Formula

E.g.f.: x*exp(x*exp(x)).

a(n) = n * A000248(n-1). - Olivier Gérard, Aug 03 2012.

a(n) = Sum_{k=0..n-1} n*C(n-1,k)*(n-k-1)^k. - Alois P. Heinz, Mar 15 2013