login
Number of forests with n nodes and height at most 2.
(Formerly M3021 N1223)
33

%I M3021 N1223 #33 Jul 03 2018 12:44:37

%S 1,1,3,16,101,756,6607,65794,733833,9046648,121961051,1782690174,

%T 28055070397,472594822324,8479144213191,161340195463066,

%U 3243707386310033,68679247688467056,1526976223741111987,35557878951515668726,865217354118762606021

%N Number of forests with n nodes and height at most 2.

%C Equivalently, the number of mappings from a set of n elements into itself where f(f(x)) = f(f(f(x))). - _Chad Brewbaker_, Mar 26 2014

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A000949/b000949.txt">Table of n, a(n) for n = 0..100</a>

%H J. Riordan, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80033-X">Forests of labeled trees</a>, J. Combin. Theory, 5 (1968), 90-103.

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

%F a(n) = n!*sum(m=1..n-1, sum(k=1..n-m, (k^(n-m-k)*m^k)/(k!*(n-m-k)!))/m!)+1. - _Vladimir Kruchinin_, May 28 2011

%e G.f. = 1 + x + 3*x^2 + 16*x^3 + 101*x^4 + 756*x^5 + 6607*x^6 + 65794*x^7 + ... - _Michael Somos_, Jul 03 2018

%t nn = 20; Range[0, nn]! CoefficientList[Series[Exp[x*Exp[x*Exp[x]]], {x, 0, nn}], x] (* _T. D. Noe_, Jun 21 2012 *)

%t a[ n_] := If[ n < 0, 0, 1 + n! Sum[ Sum[ k^(n - m - k) m^k / (k! (n - m - k)!), {k, n - m}] / m!, {m, n - 1}]]; (* _Michael Somos_, Jul 03 2018 *)

%o (Maxima) a(n):=n!*sum(sum((k^(n-m-k)*m^k)/(k!*(n-m-k)!),k,1,n-m)/m!,m,1,n-1)+1; /* _Vladimir Kruchinin_, May 28 2011 */

%o (PARI) x='x+O('x^66); Vec(serlaplace(exp(x*exp(x*exp(x))))) /* show terms with a(0)=1 */ /* _Joerg Arndt_, May 28 2011 */

%Y Cf. A000248, A000950, A000951, A052512-A052514.

%Y Column k=2 of A210725. - _Alois P. Heinz_, Mar 15 2013

%K nonn

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Apr 07 2001