A000248 Expansion of e.g.f. exp(x*exp(x)).

1, 1, 3, 10, 41, 196, 1057, 6322, 41393, 293608, 2237921, 18210094, 157329097, 1436630092, 13810863809, 139305550066, 1469959371233, 16184586405328, 185504221191745, 2208841954063318, 27272621155678841, 348586218389733556, 4605223387997411873

Offset: 0

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• easy
• nonn
• nice

Comments

Number of forests with n nodes and height at most 1.

Equivalently, number of idempotent mappings f from a set of n elements into itself (i.e., satisfying f o f = f). - Robert FERREOL, Oct 11 2007

In other words, a(n) = number of idempotents in the full semigroup of maps from [1..n] to itself. [Tainiter]

a(n) is the number of ways to select a set partition of {1,2,...,n} and then designate one element in each block (cell) of the partition.

Let set B have cardinality n. Then a(n) is the number of functions f:D->C over all partitions {D,C} of B. See the example in the Example Section below. We note that f:empty set->B is designated as the null function, whereas f:B->empty set is undefined unless B itself is empty. - Dennis P. Walsh, Dec 05 2013

In physics, a(n) would be interpreted as the number of projection operators P on S_n, i.e., ones satisfying P^2 = P. Example: a particle with a half-integer spin s has a spin space with 2s+1 base states which admits a(2s+1) linear projection operators (including the identity). These are important because they satisfy the operator identity exp(zU) = 1+(exp(z)-1)*U, valid for any complex z. - Stanislav Sykora, Nov 03 2016

Examples

			a(3)=10 since, for B={1,2,3}, we have 10 functions: 1 function of the type f:empty set->B; 6 functions of the type f:{x}->B\{x}; and 3 functions of the type f:{x,y}->B\{x,y}. - _Dennis P. Walsh_, Dec 05 2013
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 91.
• 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).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.32(d).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..541 (first 101 terms from T. D. Noe)
• Rudolf Berghammer, Jules Desharnais, and Michael Winter, Counting Specific Classes of Relations Regarding Fixed Points and Reflexive Points, arXiv:2505.00140 [cs.DM], 2025. See p. 24.
• Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
• Giulio Cerbai and Anders Claesson, Counting fixed-point-free Cayley permutations, arXiv:2507.09304 [math.CO], 2025. See p. 25.
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 131.
• Xing Gao and William F. Keigher, Interlacing of Hurwitz series, Communications in Algebra, 45:5 (2017), 2163-2185, DOI: 10.1080/00927872.2016.1226885. See Ex. 2.13.
• Bernhard Harris and Lowell Schoenfeld, The number of idempotent elements in symmetric semigroups, J. Combin. Theory, 3 (1967), 122-135.
• Bernhard Harris and Lowell Schoenfeld, Asymptotic expansions for the coefficients of analytic functions, Illinois Journal of Mathematics, Volume 12, Issue 2 (1968), 264-277.
• Gottfried Helms, Pascalmatrix tetrated
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 117
• Vaclav Kotesovec, Graph - the asymptotic ratio (1000 terms)
• Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
• John Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.
• John Riordan, Letter to N. J. A. Sloane, Oct. 1970
• John Riordan and N. J. A. Sloane, Correspondence, 1974
• Emre Sen, Exceptional Sequences and Idempotent Functions, arXiv:1909.05887 [math.RT], 2019.
• Melvin Tainiter, A characterization of idempotents in semigroups, J. Combinat. Theory, 5 (1968), 370-373.
• Haoliang Wang and Robert Simon, The Analysis of Synchronous All-to-All Communication Protocols for Wireless Systems, Q2SWinet'18: Proceedings of the 14th ACM International Symposium on QoS and Security for Wireless and Mobile Networks (2018), 39-48.

Crossrefs

First row of array A098697.

Row sums of A133399.

Column k=1 of A210725, A279636.

Column k=2 of A245501.

Cf. A005727, A048993.

Programs

Magma

m:=25; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!(Exp(x*Exp(x)))); [Factorial(n-1)*b[n]: n in [1..m]]; // Vincenzo Librandi, Feb 01 2020

Maple

A000248 := proc(n) local k; add(k^(n-k)*binomial(n, k), k=0..n); end; # Robert FERREOL, Oct 11 2007
a:= proc(n) option remember; if n=0 then 1 else add(binomial(n-1, j) *(j+1) *a(n-1-j), j=0..n-1) fi end: seq(a(n), n=0..20); # Zerinvary Lajos, Mar 28 2009

Mathematica

CoefficientList[Series[Exp[x Exp[x]],{x,0,20}],x]*Table[n!,{n,0,20}]
a[0] = 1; a[1] = 1; a[n_] := a[n] = a[n - 1] + Sum[(Binomial[n - 1, j] + (n - 1) Binomial[n - 2, j]) a[j], {j, 0, n - 2}]; Table[a[n], {n, 0, 20}] (* David Callan, Oct 04 2013 *)
Flatten[{1,Table[Sum[Binomial[n,k]*(n-k)^k,{k,0,n}],{n,1,20}]}] (* Vaclav Kotesovec, Jul 13 2014 *)
Table[Sum[BellY[n, k, Range[n]], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)

PARI

a(n)=sum(k=0,n,binomial(n,k)*(n-k)^k); \\ Paul D. Hanna, Jun 26 2009

PARI

x='x+O('x^66); Vec(serlaplace(exp(x*exp(x)))) \\ Joerg Arndt, Oct 06 2013

Sage

# uses[bell_matrix from A264428]
B = bell_matrix(lambda k: k+1, 20)
print([sum(B.row(n)) for n in range(20)]) # Peter Luschny, Sep 03 2019

Formula

G.f.: Sum_{k>=0} x^k/(1-k*x)^(k+1). - Vladeta Jovovic, Oct 25 2003

a(n) = Sum_{k=0..n} C(n,k)*(n-k)^k. - Paul D. Hanna, Jun 26 2009

G.f.: G(0) where G(k) = 1 - x*(-1+2*k*x)^(2*k+1)/((x-1+2*k*x)^(2*k+2) - x*(x-1+2*k*x)^(4*k+4)/(x*(x-1+2*k*x)^(2*k+2) - (2*x-1+2*k*x)^(2*k+3)/G(k+1))) (continued fraction). - Sergei N. Gladkovskii, Jan 26 2013

E.g.f.: 1 + x/(1+x)*(G(0) - 1) where G(k) = 1 + exp(x)/(k+1)/(1-x/(x+(1)/G(k+1))) (continued fraction). - Sergei N. Gladkovskii, Feb 04 2013

Recurrence: a(0)=1, a(n) = Sum_{k=1..n} binomial(n-1,k-1)*k*a(n-k). - James East, Mar 30 2014

Asymptotics (Harris and Schoenfeld, 1968): a(n) ~ sqrt((r+1)/(2*Pi*(n+1)*(r^2+3*r+1))) * n! * exp((n+1)/(r+1)) / r^n, where r is the root of the equation r*(r+1)*exp(r) = n+1. - Vaclav Kotesovec, Jul 13 2014

a(n) = Sum_{k=0..n} A005727(k)*Stirling2(n, k). - Mélika Tebni, Jun 12 2022

More precise asymptotics: a(n) ~ n^(n + 1/2) / (sqrt(1 + 3*r + r^2) * exp(n - r*exp(r) + r/2) * r^(n + 1/2)), where r = 2*w - 1/(2*w) + 5/(8*w^2) - 19/(24*w^3) + 209/(192*w^4) - 763/(480*w^5) + 4657/(1920*w^6) - 6855/(1792*w^7) + 199613/(32256*w^8) + ... and w = LambertW(sqrt(n)/2). - Vaclav Kotesovec, Feb 20 2023

Extensions

In view of the multiple appearances of this sequence, I replaced the definition with the simple exponential generating function. - N. J. A. Sloane, Apr 16 2018