cp's OEIS Frontend

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

%I A000248 M2857 N1148 #164 Jul 18 2025 10:13:52
%S A000248 1,1,3,10,41,196,1057,6322,41393,293608,2237921,18210094,157329097,
%T A000248 1436630092,13810863809,139305550066,1469959371233,16184586405328,
%U A000248 185504221191745,2208841954063318,27272621155678841,348586218389733556,4605223387997411873
%N A000248 Expansion of e.g.f. exp(x*exp(x)).
%C A000248 Number of forests with n nodes and height at most 1.
%C A000248 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
%C A000248 In other words, a(n) = number of idempotents in the full semigroup of maps from [1..n] to itself. [Tainiter]
%C A000248 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.
%C A000248 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
%C A000248 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
%D A000248 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 91.
%D A000248 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000248 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000248 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.32(d).
%H A000248 Alois P. Heinz, <a href="/A000248/b000248.txt">Table of n, a(n) for n = 0..541</a> (first 101 terms from T. D. Noe)
%H A000248 Rudolf Berghammer, Jules Desharnais, and Michael Winter, <a href="https://arxiv.org/abs/2505.00140">Counting Specific Classes of Relations Regarding Fixed Points and Reflexive Points</a>, arXiv:2505.00140 [cs.DM], 2025. See p. 24.
%H A000248 Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%H A000248 Giulio Cerbai and Anders Claesson, <a href="https://arxiv.org/abs/2507.09304">Counting fixed-point-free Cayley permutations</a>, arXiv:2507.09304 [math.CO], 2025. See p. 25.
%H A000248 Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 131.
%H A000248 Xing Gao and William F. Keigher, <a href="https://doi.org/10.1080/00927872.2016.1226885">Interlacing of Hurwitz series</a>, Communications in Algebra, 45:5 (2017), 2163-2185, DOI: 10.1080/00927872.2016.1226885. See Ex. 2.13.
%H A000248 Bernhard Harris and Lowell Schoenfeld, <a href="https://doi.org/10.1016/S0021-9800(67)80002-4">The number of idempotent elements in symmetric semigroups</a>, J. Combin. Theory, 3 (1967), 122-135.
%H A000248 Bernhard Harris and Lowell Schoenfeld, <a href="http://projecteuclid.org/euclid.ijm/1256054216">Asymptotic expansions for the coefficients of analytic functions</a>, Illinois Journal of Mathematics, Volume 12, Issue 2 (1968), 264-277.
%H A000248 Gottfried Helms, <a href="https://web.archive.org/web/20241001000000*/http://go.helms-net.de/math/tetdocs/PascalMatrixTetrated.pdf">Pascalmatrix tetrated</a>
%H A000248 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=117">Encyclopedia of Combinatorial Structures 117</a>
%H A000248 Vaclav Kotesovec, <a href="/A000248/a000248.jpg">Graph - the asymptotic ratio (1000 terms)</a>
%H A000248 Nate Kube and Frank Ruskey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Ruskey/ruskey99.html">Sequences That Satisfy a(n-a(n))=0</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
%H A000248 John 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.
%H A000248 John Riordan, <a href="/A001861/a001861.pdf">Letter to N. J. A. Sloane, Oct. 1970</a>
%H A000248 John Riordan and N. J. A. Sloane, <a href="/A003471/a003471_1.pdf">Correspondence, 1974</a>
%H A000248 Emre Sen, <a href="https://arxiv.org/abs/1909.05887">Exceptional Sequences and Idempotent Functions</a>, arXiv:1909.05887 [math.RT], 2019.
%H A000248 Melvin Tainiter, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80012-2">A characterization of idempotents in semigroups</a>, J. Combinat. Theory, 5 (1968), 370-373.
%H A000248 Haoliang Wang and Robert Simon, <a href="https://doi.org/10.1145/3267129.3267134">The Analysis of Synchronous All-to-All Communication Protocols for Wireless Systems</a>, Q2SWinet'18: Proceedings of the 14th ACM International Symposium on QoS and Security for Wireless and Mobile Networks (2018), 39-48.
%F A000248 G.f.: Sum_{k>=0} x^k/(1-k*x)^(k+1). - _Vladeta Jovovic_, Oct 25 2003
%F A000248 a(n) = Sum_{k=0..n} C(n,k)*(n-k)^k. - _Paul D. Hanna_, Jun 26 2009
%F A000248 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
%F A000248 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
%F A000248 Recurrence: a(0)=1, a(n) = Sum_{k=1..n} binomial(n-1,k-1)*k*a(n-k). - _James East_, Mar 30 2014
%F A000248 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
%F A000248 a(n) = Sum_{k=0..n} A005727(k)*Stirling2(n, k). - _Mélika Tebni_, Jun 12 2022
%F A000248 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
%e A000248 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
%p A000248 A000248 := proc(n) local k; add(k^(n-k)*binomial(n, k), k=0..n); end; # _Robert FERREOL_, Oct 11 2007
%p A000248 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
%t A000248 CoefficientList[Series[Exp[x Exp[x]],{x,0,20}],x]*Table[n!,{n,0,20}]
%t A000248 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 *)
%t A000248 Flatten[{1,Table[Sum[Binomial[n,k]*(n-k)^k,{k,0,n}],{n,1,20}]}] (* _Vaclav Kotesovec_, Jul 13 2014 *)
%t A000248 Table[Sum[BellY[n, k, Range[n]], {k, 0, n}], {n, 0, 20}] (* _Vladimir Reshetnikov_, Nov 09 2016 *)
%o A000248 (PARI) a(n)=sum(k=0,n,binomial(n,k)*(n-k)^k); \\ _Paul D. Hanna_, Jun 26 2009
%o A000248 (PARI) x='x+O('x^66); Vec(serlaplace(exp(x*exp(x)))) \\ _Joerg Arndt_, Oct 06 2013
%o A000248 (Sage) # uses[bell_matrix from A264428]
%o A000248 B = bell_matrix(lambda k: k+1, 20)
%o A000248 print([sum(B.row(n)) for n in range(20)]) # _Peter Luschny_, Sep 03 2019
%o A000248 (Magma) m:=25; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!(Exp(x*Exp(x)))); [Factorial(n-1)*b[n]: n in [1..m]]; // _Vincenzo Librandi_, Feb 01 2020
%Y A000248 First row of array A098697.
%Y A000248 Row sums of A133399.
%Y A000248 Column k=1 of A210725, A279636.
%Y A000248 Column k=2 of A245501.
%Y A000248 Cf. A005727, A048993.
%K A000248 easy,nonn,nice
%O A000248 0,3
%A A000248 _N. J. A. Sloane_, _Simon Plouffe_
%E A000248 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