login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000435 Normalized total height of all nodes in all rooted trees with n labeled nodes.
(Formerly M4558 N1940)
11

%I M4558 N1940

%S 0,1,8,78,944,13800,237432,4708144,105822432,2660215680,73983185000,

%T 2255828154624,74841555118992,2684366717713408,103512489775594200,

%U 4270718991667353600,187728592242564421568,8759085548690928992256

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

%C This is the sequence that started it all: the first sequence in the data base!

%C 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.

%C 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

%C 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

%C a(n) is the number of connected endofunctions with no fixed points. - _Geoffrey Critzer_, Dec 13 2011

%C a(n) (mod 10): 0, 1, 8, 8, 4, 0, 2, 4, 2, 0, 0, 4, 2, 8, ..., ; disregarding the first 5 terms, this sequence cycles through the twenty terms {0, 2, 4, 2, 0, 0, 4, 2, 8, 0, 0, 8, 6, 2, 0, 0, 6, 8, 8, 0}. - _Robert G. Wilson v_, Jan 09 2014

%C The number of decimal digits of a(n) begins: 1, 1, 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 16, 18, 19, 21, ..., . - _Robert G. Wilson v_, Jan 09 2014

%D Rényi, A., and G. Szekeres. "On the height of trees." Journal of the Australian Mathematical Society 7.04 (1967): 497-507. See (4.7).

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Robert G. Wilson v and T. D. Noe, <a href="/A000435/b000435.txt">Table of n, a(n) for n = 1..1000</a> (first 100 terms supplied by T. D. Noe)

%H Vijayakumar Ambat, <a href="/A000435/a000435.jpg">Article in the Malayalam newspaper Ayala Manorama - Padhippura, 12 June 2015</a>, that mentions the OEIS, and in particular this sequence.

%H V. I. Arnold, <a href="http://dx.doi.org/10.1007/BF02509551">Topological classification of complex trigonometric polynomials and the combinatorics of graphs with the same number of edges and vertices</a>, Functional Anal. Appl., 30 (1996), 1-17.

%H Shalosh B. Ekhad, Doron Zeilberger, <a href="http://arxiv.org/abs/1607.05776">Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees</a>, arXiv:1607.05776 [math.CO], 2016.

%H Shalosh B. Ekhad, Doron Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/a435.html">Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees</a>, Version on DZ's home page with more links.

%H I. P. Goulden and D. M. Jackson, <a href="http://arXiv.org/abs/math.AG/9902009">A proof of a conjecture for the number of ramified coverings of the sphere by the torus</a>, arXiv:math/9902009 [math.AG], 1999.

%H Goulden, I. P.; Jackson, D. M.; and Vainshtein, A., <a href="http://arXiv.org/abs/math.CO/9902125">The number of ramified coverings of the sphere by the torus and surfaces of higher genera</a>, arXiv:math/9902125 [math.AG], 1999.

%H I. P. Goulden, D. M. Jackson, and A. Vainshtein, <a href="http://dx.doi.org/10.1006/jcta.1999.2993">The number of ramified coverings of the sphere by the torus and surfaces of higher genera</a> Ann. Comb. 4 (2000), no. 1, 27-46. (See Theorem 1.1.)

%H Marko Riedel et. al. <a href="http://math.stackexchange.com/questions/1071564/">Connected endofunctions with no fixed points</a>, MathStackExchange, Dec 2014.

%H J. Riordan, <a href="/A001863/a001863.pdf">Letter to N. J. A. Sloane, Aug. 1970</a>

%H J. Riordan and N. J. A. Sloane, <a href="http://dx.doi.org/10.1017/S1446788700007527">Enumeration of rooted trees by total height</a>, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.

%H N. J. A. Sloane, <a href="/A000435/a000435_1.pdf">Page from 1964 notebook showing start of OEIS</a> [includes A000027, A000217, A000292, A000332, A000389, A000579, A000110, A007318, A000058, A000215, A000289, A000324, A234953 (= A001854(n)/n), A000435, A000169, A000142, A000272, A000312, A000111]

%H N. J. A. Sloane, <a href="/A000435/a000435_2.pdf">Cover of same notebook</a>

%H N. J. A. Sloane, <a href="/A000435/a000435_Thesis.pdf">Lengths of Cycle Times in Random Neural Networks</a>, Ph. D. Dissertation, Cornell University, February 1967; also Report No. 10, Cognitive Systems Research Program, Cornell University, 1967. This sequence appears on page 119.

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).

%H N. J. A. Sloane, <a href="/A000435/a000435.pdf">Illustration of a(3) and a(4)</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n) = (n-1)! * Sum (n^k/k!, k=0..n-2).

%F a(n) = A001864(n)/n.

%F E.g.f.: LambertW(-x)-log(1+LambertW(-x)). - _Vladeta Jovovic_, Apr 10 2001

%F a(n) = A001865(n) - n^(n-1).

%F a(n) = A001865(n) - A000169(n). - _Geoffrey Critzer_, Dec 13 2011

%F a(n) ~ sqrt(Pi/2)*n^(n-1/2). - _Vaclav Kotesovec_, Aug 07 2013

%F a(n)/A001854(n) ~ 1/2 [See Renyi-Szekeres, (4.7)]. Also a(n) = Sum (k*A259334(n,k), k=0..n-1). - David desJardins, Jan 20 2017.

%e For n = 3 there are 3^2 = 9 rooted labeled trees on 3 nodes, namely

%e (with o denoting a node, O the root node):

%e o

%e |

%e o..o..o

%e |...\/

%e O....O

%e 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.

%e For n = 4 there are 4^3 = 64 rooted labeled trees on 4 nodes, namely

%e (with o denoting a node, O the root node):

%e o

%e |

%e o..o.....o..o

%e |..|......\/

%e o..o..o....o..o..o..o

%e |...\/.....|...\.|./

%e O....O.....O.....O

%e (1).(2)...(3)...(4)

%e 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;

%e 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;

%e 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;

%e 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;

%e giving 312 in all. Dividing by 4 we get a(4)=312/4=78.

%p A000435 := n-> (n-1)!*add (n^k/k!, k=0..n-2);

%p seq(simplify((n-1)*GAMMA(n-1,n)*exp(n)),n=1..20); # _Vladeta Jovovic_, Jul 21 2005)

%t f[n_] := (n - 1)! Sum [n^k/k!, {k, 0, n - 2}]; Array[f, 18] (* _Robert G. Wilson v_, Aug 10 2010 *)

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

%Y Cf. A001863, A001864, A001854, A234953, A259334.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_

%E Additional references from _Valery A. Liskovets_

%E Editorial changes by _N. J. A. Sloane_, Feb 03 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 08:02 EST 2018. Contains 299447 sequences. (Running on oeis4.)