login
Number of rooted labeled trees of height at most 2.
10

%I #49 Sep 08 2022 08:44:59

%S 0,1,2,9,40,205,1176,7399,50576,372537,2936080,24617131,218521128,

%T 2045278261,20112821288,207162957135,2228888801056,24989309310961,

%U 291322555295904,3524580202643155,44176839081266360,572725044269255661,7668896804574138232,105920137923940473079

%N Number of rooted labeled trees of height at most 2.

%C 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

%H Alois P. Heinz, <a href="/A052512/b052512.txt">Table of n, a(n) for n = 0..300</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=58">Encyclopedia of Combinatorial Structures 58</a>

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

%F a(n) = n * A000248(n-1). - _Olivier GĂ©rard_, Aug 03 2012.

%F a(n) = Sum_{k=0..n-1} n*C(n-1,k)*(n-k-1)^k. - _Alois P. Heinz_, Mar 15 2013

%e From _Robert FERREOL_, Mar 05 2016: (Start)

%e For n = 3 the a(3) = 9 mappings from {a,b,c} into itself are:

%e f_1(a) = f_1(b) = f_1(c) = a

%e f_2(c) = b, f_2(b) = f_2(a) = a

%e f_3(b) = c, f_3(c) = f_3(a) = a

%e and 6 others, associated to b and c.

%e (End)

%p spec := [S,{S=Prod(Z,Set(T1)), T2=Z, T1=Prod(Z,Set(T2))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

%p # second Maple program:

%p a:= n-> n*add(binomial(n-1, k)*(n-k-1)^k, k=0..n-1);

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Mar 15 2013

%t nn=20; a=x Exp[x]; Range[0,nn]! CoefficientList[Series[x Exp[a], {x,0,nn}], x] (* _Geoffrey Critzer_, Sep 19 2012 *)

%o (PARI)

%o N=33; x='x+O('x^N);

%o egf=x*exp(x*exp(x));

%o v=Vec(serlaplace(egf));

%o vector(#v+1,n,if(n==1,0,v[n-1]))

%o /* _Joerg Arndt_, Sep 15 2012 */

%o (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

%o (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

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

%Y Cf. A000551.

%K easy,nonn

%O 0,3

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