The OEIS is supported by the many generous donors to the OEIS Foundation.



Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001864 Total height of rooted trees with n labeled nodes.
(Formerly M2138 N0850)
0, 2, 24, 312, 4720, 82800, 1662024, 37665152, 952401888, 26602156800, 813815035000, 27069937855488, 972940216546896, 37581134047987712, 1552687346633913000, 68331503866677657600, 3191386068123595166656, 157663539876436721860608 (list; graph; refs; listen; history; text; internal format)



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


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).


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


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


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


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)


Cf. A000435, A001863.

Sequence in context: A246190 A246610 A119491 * A099045 A181174 A209290

Adjacent sequences: A001861 A001862 A001863 * A001865 A001866 A001867




N. J. A. Sloane



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 09:50 EST 2022. Contains 358517 sequences. (Running on oeis4.)