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

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 58

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

Example

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)

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

Prog

(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 */
(Magma) m:=25; R<x>:=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
(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

Crossrefs

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

Cf. A000551.

Sequence in context: A235596 A346577 A367242 * A166554 A038156 A296964

Adjacent sequences: A052509 A052510 A052511 * A052513 A052514 A052515

Keyword

easy,nonn

Author

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

Status

approved