A259334 -id:A259334 - cp's OEIS frontend

A000435 Normalized total height of all nodes in all rooted trees with n labeled nodes.

0, 1, 8, 78, 944, 13800, 237432, 4708144, 105822432, 2660215680, 73983185000, 2255828154624, 74841555118992, 2684366717713408, 103512489775594200, 4270718991667353600, 187728592242564421568, 8759085548690928992256, 432357188322752488126152, 22510748754252398927872000

Offset: 1

N. J. A. Sloane

This is the sequence that started it all: the first sequence in the database!
The height h(V) of a node V in a rooted tree is its distance from the root. a(n) = Sum_{all nodes V in all n^(n-1) rooted trees on n nodes} h(V)/n.
In the trees which have [0, n-1] = (0, 1, ..., n-1) as their ordered set of nodes, the number of nodes at distance i from node 0 is f(n,i) = (n-1)...(n-i)(i+1)n^(j-1), 0 <= i < n-1, i+j = n-1 (and f(n,n-1) = (n-1)!): (n-1)...(n-i) counts the words coding the paths of length i from any node to 0, n^(j-1) counts the Pruefer codes of the rest, words build by iterated deletion of the greater node of degree 1 ... except the last one, (i+1), necessary pointing at the path. If g(n,i) = (n-1)...(n-i)n^j, i+j = n-1, f(n,i) = g(n,i) - g(n,i+1), g(n,i) = Sum_{k>=i} f(n,k), the sequence is Sum_{i=1..n-1} g(n,i). - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 26 2001
If one randomly selects one ball from an urn containing n different balls, with replacement, until exactly one ball has been selected twice, the probability that this ball was also the second ball to be selected once is a(n)/n^n. See also A001865. - Matthew Vandermast, Jun 15 2004
a(n) is the number of connected endofunctions with no fixed points. - Geoffrey Critzer, Dec 13 2011
a(n) is the number of weakly connected simple digraphs on n labeled nodes where every node has out-degree 1. A digraph where all out-degrees are 1 can be called a functional digraph due to the correspondence with endofunctions. - Andrew Howroyd, Feb 06 2024

			For n = 3 there are 3^2 = 9 rooted labeled trees on 3 nodes, namely (with o denoting a node, O the root node):
   o
   |
   o     o   o
   |      \ /
   O       O
The first can be labeled in 6 ways and contains nodes at heights 1 and 2 above the root, so contributes 6*(1+2) = 18 to the total; the second can be labeled in 3 ways and contains 2 nodes at height 1 above the root, so contributes 3*2=6 to the total, giving 24 in all. Dividing by 3 we get a(3) = 24/3 = 8.
For n = 4 there are 4^3 = 64 rooted labeled trees on 4 nodes, namely (with o denoting a node, O the root node):
   o
   |
   o     o        o   o
   |     |         \ /
   o     o   o      o     o o o
   |      \ /       |      \|/
   O       O        O       O
  (1)     (2)      (3)     (4)
Tree (1) can be labeled in 24 ways and contains nodes at heights 1, 2, 3 above the root, so contributes 24*(1+2+3) = 144 to the total;
tree (2) can be labeled in 24 ways and contains nodes at heights 1, 1, 2 above the root, so contributes 24*(1+1+2) = 96 to the total;
tree (3) can be labeled in 12 ways and contains nodes at heights 1, 2, 2 above the root, so contributes 12*(1+2+2) = 60 to the total;
tree (4) can be labeled in 4 ways and contains nodes at heights 1, 1, 1 above the root, so contributes 4*(1+1+1) = 12 to the total;
giving 312 in all. Dividing by 4 we get a(4) = 312/4 = 78.

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

Robert G. Wilson v, Table of n, a(n) for n = 1..1000 (first 100 terms from T. D. Noe)
Vijayakumar Ambat, Article in the Malayalam newspaper Ayala Manorama - Padhippura, 12 June 2015, that mentions the OEIS, and in particular this sequence.
V. I. Arnold, Topological classification of complex trigonometric polynomials and the combinatorics of graphs with the same number of edges and vertices, Functional Anal. Appl., 30 (1996), 1-17.
Shalosh B. Ekhad and Doron Zeilberger, Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees, arXiv:1607.05776 [math.CO], 2016.
Shalosh B. Ekhad and Doron Zeilberger, Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees, Version on DZ's home page with more links; Local copy, pdf file only, no active links
I. P. Goulden and D. M. Jackson, A proof of a conjecture for the number of ramified coverings of the sphere by the torus, arXiv:math/9902009 [math.AG], 1999.
I. P. Goulden, D. M. Jackson, and A. Vainshtein, The number of ramified coverings of the sphere by the torus and surfaces of higher genera, arXiv:math/9902125 [math.AG], 1999.
I. P. Goulden, D. M. Jackson, and A. Vainshtein, The number of ramified coverings of the sphere by the torus and surfaces of higher genera Ann. Comb. 4 (2000), no. 1, 27-46. (See Theorem 1.1.)
Brady Haran, The Number Collector (with Neil Sloane), Numberphile Podcast (2019)
Andrew Lohr and Doron Zeilberger, On the limiting distributions of the total height on families of trees, Integers (2018) 18, Article #A32.
T. Kyle Petersen, Exponential generating functions and Bell numbers, Inquiry-Based Enumerative Combinatorics (2019) Chapter 7, Undergraduate Texts in Mathematics, Springer, Cham, 98-99.
A. Rényi and G. Szekeres, On the height of trees, Journal of the Australian Mathematical Society 7.04 (1967): 497-507. See (4.7).
Marko Riedel et al., Connected endofunctions with no fixed points, Mathematics Stack Exchange, Dec 2014.
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, Page from 1964 notebook showing start of OEIS [includes A000027, A000217, A000292, A000332, A000389, A000579, A000110, A007318, A000058, A000215, A000289, A000324, A234953 (= A001854(n)/n), A000435, A000169, A000142, A000272, A000312, A000111]
N. J. A. Sloane, Cover of same notebook
N. J. A. Sloane, Lengths of Cycle Times in Random Neural Networks, Ph. D. Dissertation, Cornell University, February 1967; also Report No. 10, Cognitive Systems Research Program, Cornell University, 1967. This sequence appears on page 119.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Illustration of a(3) and a(4)
Yukun Yao and Doron Zeilberger, An Experimental Mathematics Approach to the Area Statistic of Parking Functions, arXiv:1806.02680 [math.CO], 2018.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 3.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A001863, A001864, A001854, A002862 (unlabeled version), A234953, A259334.

Column k=1 of A350452.

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

f[n_] := (n - 1)! Sum [n^k/k!, {k, 0, n - 2}]; Array[f, 18] (* Robert G. Wilson v, Aug 10 2010 *)
nx = 18; Rest[ Range[0, nx]! CoefficientList[ Series[ LambertW[-x] - Log[1 + LambertW[-x]], {x, 0, nx}], x]] (* Robert G. Wilson v, Apr 13 2013 *)

x='x+O('x^30); concat(0, Vec(serlaplace(lambertw(-x)-log(1+lambertw(-x))))) \\ Altug Alkan, Sep 05 2018

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

from math import comb
def A000435(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))//n # Chai Wah Wu, Apr 25-26 2023

a(n) = (n-1)! * Sum_{k=0..n-2} n^k/k!.
a(n) = A001864(n)/n.
E.g.f.: LambertW(-x) - log(1+LambertW(-x)). - Vladeta Jovovic, Apr 10 2001
a(n) = A001865(n) - n^(n-1).
a(n) = A001865(n) - A000169(n). - Geoffrey Critzer, Dec 13 2011
a(n) ~ sqrt(Pi/2)*n^(n-1/2). - Vaclav Kotesovec, Aug 07 2013
a(n)/A001854(n) ~ 1/2 [See Renyi-Szekeres, (4.7)]. Also a(n) = Sum_{k=0..n-1} k*A259334(n,k). - David desJardins, Jan 20 2017
a(n) = (n-1)*A001863(n). - M. F. Hasler, Dec 10 2018

Additional references from Valery A. Liskovets
Editorial changes by N. J. A. Sloane, Feb 03 2012
Edited by M. F. Hasler, Dec 10 2018

A089946 Secondary diagonal of array A089944, in which the n-th row is the n-th binomial transform of the natural numbers.

Original entry on oeis.org

1, 4, 24, 200, 2160, 28812, 458752, 8503056, 180000000, 4287177620, 113515167744, 3308603804376, 105288694411264, 3632897460937500, 135107988821114880, 5388090449900829728, 229385780960233586688, 10383890888434362036516, 498073600000000000000000

Offset: 0

Paul D. Hanna, Nov 23 2003

nonn

Also the hyperbinomial transform of A089945 (the main diagonal of A089944): a(n) = Sum_{k=0..n} C(n,k)*(n-k+1)^(n-k-1)*A089945(k).
With offset 1, a(n) = total number of children of the root in all (n+1)^(n-1) trees on {0,1,2,...,n} rooted at 0. For example, with edges directed away from the root, the trees on {0,1,2} are {0->1,0->2},{0->1->2},{0->2->1} and contain a total of a(2)=4 children of 0. - David Callan, Feb 01 2007
With offset 1, a(n) is the number of labeled rooted trees in all rooted forests on n nodes. The E.g.f. is B(T(x)) where  B(x)=x*exp(x) and T(x) is Euler's tree function. - Geoffrey Critzer, Oct 07 2011

Alois P. Heinz, Table of n, a(n) for n = 0..386
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
F. A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424.
F. A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424. (Annotated scanned copy)
F. A. Haight, Letter to N. J. A. Sloane, n.d.

Cf. A089944, A089945.

A diagonal of A259334.

[2*(n+1) * (n+2)^(n-1): n in [0..50]]; // G. C. Greubel, Nov 14 2017

t=Sum[n^(n-1)x^n/n!, {n,1,20}]; Drop[Range[0,20]!*CoefficientList[ Series[t*Exp[t], {x,0,20}], x], 1] (* Geoffrey Critzer, Oct 07 2011 *)
Table[2*(n+1)*(n+2)^(n-1), {n, 0, 50}] (* G. C. Greubel, Nov 14 2017 *)

PARI
```
a(n)=if(n<0,0,2*(n+1)*(n+2)^(n-1));
```

a(n) = 2*(n+1) * (n+2)^(n-1).
a(n) = Sum_{k=0..n} C(n, k) * (n-k+1)^(n-k-1) * (2*k+1) * (k+1)^(k-1).
E.g.f.: (-LambertW(x)/x)^2 * (1 - LambertW(x)) / (1 + LambertW(x)).

cp's OEIS Frontend

A000435 Normalized total height of all nodes in all rooted trees with n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A089946 Secondary diagonal of array A089944, in which the n-th row is the n-th binomial transform of the natural numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula