|
%I M2138 N0850 #84 Apr 26 2023 10:09:01
%S 0,2,24,312,4720,82800,1662024,37665152,952401888,26602156800,
%T 813815035000,27069937855488,972940216546896,37581134047987712,
%U 1552687346633913000,68331503866677657600,3191386068123595166656,157663539876436721860608
%N Total height of rooted trees with n labeled nodes.
%C a(n) is the total number of nonrecurrent elements mapped into a recurrent element in all functions f:{1,2,...,n}->{1,2,...,n}. a(n) = Sum_{k=1..n-1} A216971(n,k)*k. - _Geoffrey Critzer_, Jan 01 2013
%C a(n) is the sum of the lengths of all cycles over all functions f:{1,2,...,n}->{1,2,...,n}. Fixed points are taken to have length zero. a(n) = Sum_{k=2..n} A066324(n,k)*(k-1). - _Geoffrey Critzer_, Aug 19 2013
%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="/A001864/b001864.txt">Table of n, a(n) for n = 1..100</a>
%H Hien D. Nguyen and G. J. McLachlan, <a href="https://arxiv.org/abs/1607.04807">Progress on a Conjecture Regarding the Triangular Distribution</a>, arXiv preprint arXiv:1607.04807 [stat.OT], 2016.
%H J. Riordan, <a href="/A001863/a001863.pdf">Letter to N. J. A. Sloane, Aug. 1970</a>
%H J. Riordan and N. J. A. Sloane, <a href="http://dx.doi.org/10.1017/S1446788700007527">Enumeration of rooted trees by total height</a>, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.
%H N. J. A. Sloane, <a href="/A000435/a000435.pdf">Illustration of terms a(3) and a(4) in A000435</a>
%H D. Zvonkine, <a href="http://www.math.jussieu.fr/~zvonkine/">Home Page</a>
%H D. Zvonkine, <a href="http://arxiv.org/abs/math/0403092">An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere</a>, arXiv:0403092v2 [math.AG], 2004.
%H D. Zvonkine, <a href="http://arxiv.org/abs/math/0506248">Enumeration of ramified coverings of the sphere and 2-dimensional gravity</a>, arXiv:math/0506248 [math.AG], 2005.
%H D. Zvonkine, <a href="http://mi.mathnet.ru/eng/mmj274">Counting ramified coverings and intersection theory on Hurwitz spaces II (local structure of Hurwitz spaces and combinatorial results)</a>, Moscow Mathematical Journal, vol. 7 (2007), no. 1, 135-162.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F a(n) = n*A000435(n).
%F E.g.f: (LambertW(-x)/(1+LambertW(-x)))^2. - _Vladeta Jovovic_, Apr 10 2001
%F a(n) = Sum_{k=1..n-1} binomial(n, k)*(n-k)^(n-k)*k^k. - _Benoit Cloitre_, Mar 22 2003
%F a(n) ~ sqrt(Pi/2)*n^(n+1/2). - _Vaclav Kotesovec_, Aug 07 2013
%F a(n) = n! * Sum_{k=0..n-2} n^k/k!. - _Jianing Song_, Aug 08 2022
%p A001864 := proc(n) local k; add(n!*n^k/k!, k=0..n-2); end;
%t Table[Sum[Binomial[n,k](n-k)^(n-k) k^k,{k,1,n-1}],{n,20}] (* _Harvey P. Dale_, Oct 10 2011 *)
%t a[n_] := n*(n-1)*Exp[n]*Gamma[n-1, n] // Round; Table[a[n], {n, 1, 18}] (* _Jean-François Alcover_, Jun 24 2013 *)
%o (PARI) a(n)=sum(k=1,n-1,binomial(n,k)*(n-k)^(n-k)*k^k)
%o (Python)
%o from math import comb
%o def A001864(n): return (sum(comb(n,k)*(n-k)**(n-k)*k**k for k in range(1,(n+1>>1)))<<1) + (0 if n&1 else comb(n,m:=n>>1)*m**n) # _Chai Wah Wu_, Apr 25-26 2023
%Y Cf. A000435, A001863.
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_
|
