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

1, 1, 3, 16, 101, 756, 6607, 65794, 733833, 9046648, 121961051, 1782690174, 28055070397, 472594822324, 8479144213191, 161340195463066, 3243707386310033, 68679247688467056, 1526976223741111987, 35557878951515668726, 865217354118762606021

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

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

Examples

			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
		

References

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

Links

• T. D. Noe, Table of n, a(n) for n = 0..100
• J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.

Crossrefs

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

Column k=2 of A210725. - Alois P. Heinz, Mar 15 2013

Programs

Mathematica

nn = 20; Range[0, nn]! CoefficientList[Series[Exp[x*Exp[x*Exp[x]]], {x, 0, nn}], x] (* T. D. Noe, Jun 21 2012 *)
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 *)

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

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

Formula

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

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

Extensions

More terms from Vladeta Jovovic, Apr 07 2001