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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001864 Total height of rooted trees with n labeled nodes.
(Formerly M2138 N0850)
12
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)
OFFSET
1,2
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
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 and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.
D. Zvonkine, Home Page
D. Zvonkine, Enumeration of ramified coverings of the sphere and 2-dimensional gravity, arXiv:math/0506248 [math.AG], 2005.
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
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 *)
PROG
(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
CROSSREFS
Sequence in context: A246190 A246610 A119491 * A099045 A181174 A209290
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved

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 February 20 20:16 EST 2024. Contains 370217 sequences. (Running on oeis4.)