|
%I M2857 N1148 #157 Feb 20 2023 09:07:20
%S 1,1,3,10,41,196,1057,6322,41393,293608,2237921,18210094,157329097,
%T 1436630092,13810863809,139305550066,1469959371233,16184586405328,
%U 185504221191745,2208841954063318,27272621155678841,348586218389733556,4605223387997411873
%N Expansion of e.g.f. exp(x*exp(x)).
%C Number of forests with n nodes and height at most 1.
%C 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 In other words, a(n) = number of idempotents in the full semigroup of maps from [1..n] to itself. [Tainiter]
%C 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 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 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 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 91.
%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).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.32(d).
%H 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 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 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 131.
%H 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 B. Harris and L. Schoenfeld, <a href="http://dx.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 Bernard 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 G. Helms, <a href="http://go.helms-net.de/math/tetdocs/PascalMatrixTetrated.pdf">Pascalmatrix tetrated</a> [From _Gottfried Helms_, Feb 04 2009]
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=117">Encyclopedia of Combinatorial Structures 117</a>
%H Vaclav Kotesovec, <a href="/A000248/a000248.jpg">Graph - the asymptotic ratio (1000 terms)</a>
%H 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 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.
%H J. Riordan, <a href="/A001861/a001861.pdf">Letter to N. J. A. Sloane, Oct. 1970</a>
%H John Riordan and N. J. A. Sloane, <a href="/A003471/a003471_1.pdf">Correspondence, 1974</a>
%H Emre Sen, <a href="https://arxiv.org/abs/1909.05887">Exceptional Sequences and Idempotent Functions</a>, arXiv:1909.05887 [math.RT], 2019.
%H M. 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 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 G.f.: Sum_{k>=0} x^k/(1-k*x)^(k+1). - _Vladeta Jovovic_, Oct 25 2003
%F a(n) = Sum_{k=0..n} C(n,k)*(n-k)^k. - _Paul D. Hanna_, Jun 26 2009
%F 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 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 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 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 a(n) = Sum_{k=0..n} A005727(k)*Stirling2(n, k). - _Mélika Tebni_, Jun 12 2022
%F 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 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 := proc(n) local k; add(k^(n-k)*binomial(n, k), k=0..n); end; # _Robert FERREOL_, Oct 11 2007
%p 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 CoefficientList[Series[Exp[x Exp[x]],{x,0,20}],x]*Table[n!,{n,0,20}]
%t 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 Flatten[{1,Table[Sum[Binomial[n,k]*(n-k)^k,{k,0,n}],{n,1,20}]}] (* _Vaclav Kotesovec_, Jul 13 2014 *)
%t Table[Sum[BellY[n, k, Range[n]], {k, 0, n}], {n, 0, 20}] (* _Vladimir Reshetnikov_, Nov 09 2016 *)
%o (PARI) a(n)=sum(k=0,n,binomial(n,k)*(n-k)^k); \\ _Paul D. Hanna_, Jun 26 2009
%o (PARI) x='x+O('x^66); Vec(serlaplace(exp(x*exp(x)))) \\ _Joerg Arndt_, Oct 06 2013
%o (Sage) # uses[bell_matrix from A264428]
%o B = bell_matrix(lambda k: k+1, 20)
%o print([sum(B.row(n)) for n in range(20)]) # _Peter Luschny_, Sep 03 2019
%o (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 First row of array A098697.
%Y Row sums of A133399.
%Y Column k=1 of A210725, A279636.
%Y Column k=2 of A245501.
%Y Cf. A005727, A048993.
%K easy,nonn,nice
%O 0,3
%A _N. J. A. Sloane_, _Simon Plouffe_
%E 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
| 