A001864 Total height of rooted trees with n labeled nodes.

0, 2, 24, 312, 4720, 82800, 1662024, 37665152, 952401888, 26602156800, 813815035000, 27069937855488, 972940216546896, 37581134047987712, 1552687346633913000, 68331503866677657600, 3191386068123595166656, 157663539876436721860608

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

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

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 = 1..100
• Hien D. Nguyen and G. J. McLachlan, Progress on a Conjecture Regarding the Triangular Distribution, arXiv preprint arXiv:1607.04807 [stat.OT], 2016.
• J. Riordan, Letter to N. J. A. Sloane, Aug. 1970
• J. Riordan and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.
• N. J. A. Sloane, Illustration of terms a(3) and a(4) in A000435
• D. Zvonkine, Home Page
• D. Zvonkine, 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, arXiv:0403092v2 [math.AG], 2004.
• D. Zvonkine, Enumeration of ramified coverings of the sphere and 2-dimensional gravity, arXiv:math/0506248 [math.AG], 2005.
• D. Zvonkine, Counting ramified coverings and intersection theory on Hurwitz spaces II (local structure of Hurwitz spaces and combinatorial results), Moscow Mathematical Journal, vol. 7 (2007), no. 1, 135-162.
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Cf. A000435, A001863.

Programs

Maple

A001864 := proc(n) local k; add(n!*n^k/k!, k=0..n-2); end;

Mathematica

Table[Sum[Binomial[n,k](n-k)^(n-k) k^k,{k,1,n-1}],{n,20}] (* Harvey P. Dale, Oct 10 2011 *)
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 *)

PARI

a(n)=sum(k=1,n-1,binomial(n,k)*(n-k)^(n-k)*k^k)

Python

from math import comb
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

Formula

a(n) = n*A000435(n).

E.g.f: (LambertW(-x)/(1+LambertW(-x)))^2. - Vladeta Jovovic, Apr 10 2001

a(n) = Sum_{k=1..n-1} binomial(n, k)*(n-k)^(n-k)*k^k. - Benoit Cloitre, Mar 22 2003

a(n) ~ sqrt(Pi/2)*n^(n+1/2). - Vaclav Kotesovec, Aug 07 2013

a(n) = n! * Sum_{k=0..n-2} n^k/k!. - Jianing Song, Aug 08 2022