|
|
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
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n-1} binomial(n, k)*(n-k)^(n-k)*k^k. - Benoit Cloitre, Mar 22 2003
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|