A216971 -id:A216971 - cp's OEIS frontend

A001864 Total height of rooted trees with n labeled nodes.

0, 2, 24, 312, 4720, 82800, 1662024, 37665152, 952401888, 26602156800, 813815035000, 27069937855488, 972940216546896, 37581134047987712, 1552687346633913000, 68331503866677657600, 3191386068123595166656, 157663539876436721860608

Offset: 1

N. J. A. Sloane

a(n) is the total number of nonrecurrent elements mapped into a recurrent element in all functions f:{1,2,...,n}->{1,2,...,n}. a(n) = Sum_{k=1..n-1} A216971(n,k)*k. - Geoffrey Critzer, Jan 01 2013

a(n) is the sum of the lengths of all cycles over all functions f:{1,2,...,n}->{1,2,...,n}. Fixed points are taken to have length zero. a(n) = Sum_{k=2..n} A066324(n,k)*(k-1). - Geoffrey Critzer, Aug 19 2013

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

T. D. Noe, Table of n, a(n) for n = 1..100
Hien D. Nguyen and G. J. McLachlan, Progress on a Conjecture Regarding the Triangular Distribution, arXiv preprint arXiv:1607.04807 [stat.OT], 2016.
J. Riordan, Letter to N. J. A. Sloane, Aug. 1970
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, Illustration of terms a(3) and a(4) in A000435
D. Zvonkine, Home Page
D. Zvonkine, An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere, arXiv:0403092v2 [math.AG], 2004.
D. Zvonkine, Enumeration of ramified coverings of the sphere and 2-dimensional gravity, arXiv:math/0506248 [math.AG], 2005.
D. Zvonkine, Counting ramified coverings and intersection theory on Hurwitz spaces II (local structure of Hurwitz spaces and combinatorial results), Moscow Mathematical Journal, vol. 7 (2007), no. 1, 135-162.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000435, A001863.

A001864 := proc(n) local k; add(n!*n^k/k!, k=0..n-2); end;

Table[Sum[Binomial[n,k](n-k)^(n-k) k^k,{k,1,n-1}],{n,20}] (* Harvey P. Dale, Oct 10 2011 *)
a[n_] := n*(n-1)*Exp[n]*Gamma[n-1, n] // Round; Table[a[n], {n, 1, 18}]  (* Jean-François Alcover, Jun 24 2013 *)

a(n)=sum(k=1,n-1,binomial(n,k)*(n-k)^(n-k)*k^k)

from math import comb
def A001864(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) # Chai Wah Wu, Apr 25-26 2023

a(n) = n*A000435(n).
E.g.f: (LambertW(-x)/(1+LambertW(-x)))^2. - Vladeta Jovovic, Apr 10 2001
a(n) = Sum_{k=1..n-1} binomial(n, k)*(n-k)^(n-k)*k^k. - Benoit Cloitre, Mar 22 2003
a(n) ~ sqrt(Pi/2)*n^(n+1/2). - Vaclav Kotesovec, Aug 07 2013
a(n) = n! * Sum_{k=0..n-2} n^k/k!. - Jianing Song, Aug 08 2022

A219694 Triangular array read by rows: T(n,k) is the number of functions f:{1,2,...,n} -> {1,2,...,n} that have exactly k nonrecurrent elements; n>=1, 0<=k<=n-1.

Original entry on oeis.org

1, 2, 2, 6, 12, 9, 24, 72, 96, 64, 120, 480, 900, 1000, 625, 720, 3600, 8640, 12960, 12960, 7776, 5040, 30240, 88200, 164640, 216090, 201684, 117649, 40320, 282240, 967680, 2150400, 3440640, 4128768, 3670016, 2097152, 362880, 2903040, 11430720, 29393280, 55112400, 79361856, 89282088, 76527504, 43046721

Offset: 1

Geoffrey Critzer, Nov 25 2012

x in {1,2,...,n} is a recurrent element if there is some k such that f^k(x) = x where f^k(x) denotes iterated functional composition. In other words, a recurrent element is in a cycle of the functional digraph. An element that is not recurrent is a nonrecurrent element.

			T(2,1) = 2 because we have 1->1 2->1; and 1->2 2->2.
:    1;
:    2,     2;
:    6,    12,     9;
:   24,    72,    96,     64;
:  120,   480,   900,   1000,    625;
:  720,  3600,  8640,  12960,  12960,   7776;
: 5040, 30240, 88200, 164640, 216090, 201684, 117649;

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A216971.

b:= proc(n) option remember; `if`(n=0, 1, add(
      (j-1)!*b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n-1))(add(
    b(j)*(x*n)^(n-j)*binomial(n-1, j-1), j=0..n)):
seq(T(n), n=1..10);  # Alois P. Heinz, May 22 2016

nn=8;f[list_]:=Select[list,#>0&];t=Sum[n^(n-1)x^n y^n/n!,{n,1,nn}];Drop[Map[f,Range[0,nn]!CoefficientList[Series[1/(1-x Exp[t]),{x,0,nn}],{x,y}]],1]//Grid

E.g.f.: 1/(1-x*exp(A(x,y))), where A(x,y) = Sum_{n>=1} n^(n-1)*(y*x)^n/n!.

cp's OEIS Frontend

A001864 Total height of rooted trees with n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula