A001863 Normalized total height of rooted trees with n nodes. (Formerly M3614 N1466)

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

Offset

1,3

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

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

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

Prog

(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
(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
(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

Crossrefs

Cf. A000435, A000169, A001864.

Sequence in context: A124824 A000311 A244451 * A300698 A244524 A209923

Adjacent sequences: A001860 A001861 A001862 * A001864 A001865 A001866

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Status

approved