|
| |
|
|
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^(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
|
|
|
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): 497-507. 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) = (n-1)! * Sum_{k=0..n-2} 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-> (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)
|
|
|
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)*(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
