

A000435


Normalized total height of all nodes in all rooted trees with n labeled nodes.
(Formerly M4558 N1940)


21



0, 1, 8, 78, 944, 13800, 237432, 4708144, 105822432, 2660215680, 73983185000, 2255828154624, 74841555118992, 2684366717713408, 103512489775594200, 4270718991667353600, 187728592242564421568, 8759085548690928992256, 432357188322752488126152, 22510748754252398927872000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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^(n1) rooted trees on n nodes} h(V)/n.
In the trees which have [0, n1] = (0, 1, ..., n1) as their ordered set of nodes, the number of nodes at distance i from node 0 is f(n,i) = (n1)...(ni)(i+1)n^(j1), 0 <= i < n1, i+j = n1 (and f(n,n1) = (n1)!): (n1)...(ni) counts the words coding the paths of length i from any node to 0, n^(j1) 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) = (n1)...(ni)n^j, i+j = n1, 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..n1} 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 outdegree 1. A digraph where all outdegrees are 1 can be called a functional digraph due to the correspondence with endofunctions.  Andrew Howroyd, Feb 06 2024


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

A. Rényi and G. Szekeres, On the height of trees, Journal of the Australian Mathematical Society 7.04 (1967): 497507. See (4.7).
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]


FORMULA

a(n) = (n1)! * Sum_{k=0..n2} n^k/k!.


EXAMPLE

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.


MAPLE

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


MATHEMATICA

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


PROG

(PARI) x='x+O('x^30); concat(0, Vec(serlaplace(lambertw(x)log(1+lambertw(x))))) \\ Altug Alkan, Sep 05 2018
(Python)
from math import comb
def A000435(n): return ((sum(comb(n, k)*(nk)**(nk)*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 2526 2023


CROSSREFS



KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



