A001863 Normalized total height of rooted trees with n nodes.

0, 1, 4, 26, 236, 2760, 39572, 672592, 13227804, 295579520, 7398318500, 205075286784, 6236796259916, 206489747516416, 7393749269685300, 284714599444490240, 11733037015160276348, 515240326393584058368, 24019843795708471562564, 1184776250223810469888000

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

a(n) is the number of partial functions f from [n-1] into [n-1] such that f^k(1) is undefined for some k>=1. - Geoffrey Critzer, Mar 05 2022

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

• G. C. Greubel, Table of n, a(n) for n = 1..385 (terms 1..100 from T. D. Noe)
• H. Bergeron, E. M. F. Curado, J. P. Gazeau and L. M. C. S. Rodrigues, A note about combinatorial sequences and Incomplete Gamma function, arXiv preprint arXiv: 1309.6910 [math.CO], 2013.
• 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.
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Cf. A000435, A000169, A001864.

Programs

Magma

[0] cat [&+[Factorial(n-2)*n^k div Factorial(k): k in [0..n-2]]: n in [2..24]]; // Vincenzo Librandi, Dec 10 2018

Maple

A001863 := n->add((n-2)!*n^k/k!, k=0..n-2); # for n>1. Equals A001864(n)/(n^2-n)
seq(simplify(GAMMA(n-1,n)*exp(n)),n=2..20); # Vladeta Jovovic, Jul 21 2005

Mathematica

a[n_] := Sum[(n-2)!*n^k/k!, {k, 0, n-2}]; Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Oct 09 2012, from Maple *)
Table[Sum[(n-2)! n^k/k!,{k,0,n-2}],{n,30}] (* Harvey P. Dale, Jun 19 2016 *)

PARI

apply( A001863(n)=sum(k=0,n-2,(n-2)!/k!*n^k), [1..20]) \\ This defines the function A001863; apply(...) provides a check and illustration. - G. C. Greubel, Nov 14 2017, edited by M. F. Hasler, Dec 09 2018

Python

from math import comb
def A001863(n): return 0 if n<2 else ((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))//n//(n-1) # Chai Wah Wu, Apr 25-26 2023

Formula

E.g.f.: -exp(1)*x*(Ei(-1-LambertW(-x))-Ei(-1)) - LambertW(-x) + log(1+LambertW(-x)). - Vladeta Jovovic, Sep 29 2003

a(n)*(n-1) = A000435(n). - M. F. Hasler, Dec 10 2018

E.g.f.: x*diff(A000169(x),x)^2. - Vladimir Kruchinin, Jun 07 2020

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