|
%I M4558 N1940 #203 Feb 07 2024 11:55:25
%S 0,1,8,78,944,13800,237432,4708144,105822432,2660215680,73983185000,
%T 2255828154624,74841555118992,2684366717713408,103512489775594200,
%U 4270718991667353600,187728592242564421568,8759085548690928992256,432357188322752488126152,22510748754252398927872000
%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 database!
%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_{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
%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) 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
%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, <a href="/A000435/b000435.txt">Table of n, a(n) for n = 1..1000</a> (first 100 terms from 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 and 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 and 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; <a href="/A000435/a000435_4.pdf">Local copy, pdf file only, no active links</a>
%H I. P. Goulden and D. M. Jackson, <a href="http://arxiv.org/abs/math/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 I. P. Goulden, D. M. Jackson, and A. Vainshtein, <a href="https://arxiv.org/abs/math/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 Brady Haran, <a href="https://www.youtube.com/watch?v=mNk_MfFKnuY">The Number Collector (with Neil Sloane)</a>, Numberphile Podcast (2019)
%H Andrew Lohr and Doron Zeilberger, <a href="http://math.colgate.edu/~integers/s32/s32.Abstract.html">On the limiting distributions of the total height on families of trees</a>, Integers (2018) 18, Article #A32.
%H T. Kyle Petersen, <a href="https://doi.org/10.1007/978-3-030-18308-0_7">Exponential generating functions and Bell numbers</a>, Inquiry-Based Enumerative Combinatorics (2019) Chapter 7, Undergraduate Texts in Mathematics, Springer, Cham, 98-99.
%H A. Rényi and G. Szekeres, <a href="https://doi.org/10.1017/S1446788700004432">On the height of trees</a>, Journal of the Australian Mathematical Society 7.04 (1967): 497-507. See (4.7).
%H Marko Riedel et al., <a href="http://math.stackexchange.com/questions/1071564/">Connected endofunctions with no fixed points</a>, Mathematics Stack Exchange, 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_3.pdf">Illustration of a(3) and a(4)</a>
%H Yukun Yao and Doron Zeilberger, <a href="https://arxiv.org/abs/1806.02680">An Experimental Mathematics Approach to the Area Statistic of Parking Functions</a>, arXiv:1806.02680 [math.CO], 2018.
%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 3.
%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_{k=0..n-2} n^k/k!.
%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=0..n-1} k*A259334(n,k). - _David desJardins_, Jan 20 2017
%F a(n) = (n-1)*A001863(n). - _M. F. Hasler_, Dec 10 2018
%e For n = 3 there are 3^2 = 9 rooted labeled trees on 3 nodes, namely (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 (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 *)
%o (PARI) x='x+O('x^30); concat(0, Vec(serlaplace(lambertw(-x)-log(1+lambertw(-x))))) \\ _Altug Alkan_, Sep 05 2018
%o (PARI) A000435(n)=(n-1)*A001863(n) \\ _M. F. Hasler_, Dec 10 2018
%o (Python)
%o from math import comb
%o 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
%Y Cf. A001863, A001864, A001854, A002862 (unlabeled version), A234953, A259334.
%Y Column k=1 of A350452.
%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
%E Edited by _M. F. Hasler_, Dec 10 2018
| 