|
| |
|
|
A000435
|
|
Normalized total height of rooted trees with n labeled nodes.
(Formerly M4558 N1940)
|
|
5
| |
|
|
0, 1, 8, 78, 944, 13800, 237432, 4708144, 105822432, 2660215680, 73983185000, 2255828154624, 74841555118992, 2684366717713408, 103512489775594200, 4270718991667353600, 187728592242564421568, 8759085548690928992256
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| This is the sequence that started it all: the first sequence in the data base!
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 (f(n,k), k >= i), the sequence is sum ((g(n,i), 1<=i<n) - 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 that ball was also the second ball to be selected once is a(n)/n^n. See also A001865. - Matthew Vandermast (ghodges14(AT)comcast.net), Jun 15 2004
a(n) is the number of connected endofunctions with no fixed points. a(n) = A001865(n)-A000169(n). - Geoffrey Critzer, Dec 13 2011
|
|
|
REFERENCES
| 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.
Goulden, I. P.; Jackson, D. M.; and Vainshtein, A., 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.)
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
| T. D. Noe, Table of n, a(n) for n=1..100
I. P. Goulden and D. M. Jackson, A proof of a conjecture ...
Goulden, I. P.; Jackson, D. M.; and Vainshtein, A., The number of ramified coverings of the sphere ...
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, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Illustration of a(3) and a(4)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
|
|
|
FORMULA
| (n-1)! Sum (n^k/k!, k=0..n-2).
a(n) = A001864(n)/n.
E.g.f.: LambertW(-x)-ln(1+LambertW(-x)) - Vladeta Jovovic (vladeta(AT)eunet.rs), Apr 10 2001
a(n) = A001865(n)-n^(n-1).
|
|
|
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 (vladeta(AT)eunet.rs), Jul 21 2005)
|
|
|
MATHEMATICA
| f[n_] := (n - 1)! Sum [n^k/k!, {k, 0, n - 2}]; Array[f, 18] [From Robert G. Wilson v (rgwv(AT)rgwv.com), Aug 10 2010]
|
|
|
CROSSREFS
| Cf. A001863, A001864.
Sequence in context: A111533 A132164 A058480 * A052698 A052603 A071556
Adjacent sequences: A000432 A000433 A000434 * A000436 A000437 A000438
|
|
|
KEYWORD
| nonn,easy,nice,changed
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Additional references from Valery Liskovets (liskov(AT)im.bas-net.by).
Editorial changes by N. J. A. Sloane, Feb 03 2012.
|
| |
|
|
