A034855 -id:A034855 - cp's OEIS frontend

A235595 Triangle read by rows: the triangle in A034855, with the n-th row normalized by dividing it by n.

1, 1, 2, 1, 9, 6, 1, 40, 60, 24, 1, 195, 560, 420, 120, 1, 1056, 5550, 6240, 3240, 720, 1, 6321, 59472, 94710, 68880, 27720, 5040, 1, 41392, 692440, 1527456, 1426320, 792960, 262080, 40320, 1, 293607, 8753040, 26418168, 30560544, 21213360, 9676800, 2721600, 362880, 1, 2237920, 119723130, 490458240, 691331760, 570810240, 323114400, 125798400, 30844800, 3628800

Offset: 2

N. J. A. Sloane, Jan 14 2014

T(n,k) is the number of forests of labeled rooted trees with n nodes and height k Cf. A210725. Equivalently, T(n,k) is the number of nilpotent partial functions on [n] with index k+1. - Geoffrey Critzer, Nov 26 2021

			Triangle begins:
1.
1, 2,
1, 9, 6,
1, 40, 60, 24,
1, 195, 560, 420, 120,
1, 1056, 5550, 6240, 3240, 720,
1, 6321, 59472, 94710, 68880, 27720, 5040,
1, 41392, 692440, 1527456,1426320, 792960, 262080, 40320,
1, 293607, 8753040, 26418168, 30560544, 21213360, 9676800, 2721600, 362880,
...

Alois P. Heinz, Rows n = 2..142, flattened

Cf. A000435, A034855, A001854, A210725, A234953, A235596, A236396.

Row sums give A000272.

b:= proc(n, h) option remember; `if`(min(n, h)=0, 1, add(
      binomial(n-1, j-1)*j*b(j-1, h-1)*b(n-j, h), j=1..n))
    end:
T:= (n,k)-> b(n-1, k-1)-b(n-1, k-2):
seq(seq(T(n, d), d=1..n-1), n=2..12);  # Alois P. Heinz, Aug 21 2017

gf[k_] := gf[k] = If[k == 0, x, x*E^gf[k-1]]; a[n_, k_] := n!*Coefficient[Series[gf[k], {x, 0, n+1}], x, n]; t[n_, k_] := (a[n, k] - a[n, k-1])/n; Table[t[n, k], {n, 2, 11}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Mar 18 2014, after Alois P. Heinz *)

from sympy import binomial
from sympy.core.cache import cacheit
@cacheit
def b(n, h): return 1 if min(n, h)==0 else sum([binomial(n - 1, j - 1)*j*b(j - 1, h - 1)*b(n - j, h) for j in range(1, n + 1)])
def T(n, k): return b(n - 1, k - 1) - b(n - 1, k - 2)
for n in range(2, 13): print([T(n, d) for d in  range(1, n)]) # Indranil Ghosh, Aug 26 2017, after Maple code

A234953(n) = Sum_{k=1..n} k*T(n,k).

A001854 Total height of all rooted trees on n labeled nodes.

Original entry on oeis.org

0, 2, 15, 148, 1785, 26106, 449701, 8927192, 200847681, 5053782070, 140679853941, 4293235236324, 142553671807729, 5116962926162738, 197459475792232725, 8152354312656732976, 358585728464893234305, 16741214317684425260142, 826842457727306803110997, 43073414675338753123113980

Offset: 1

N. J. A. Sloane

nonn

Take any one of the n^(n-1) rooted trees on n labeled nodes, compute its height (maximal edge distance to root), sum over all trees.

Theorem [Renyi-Szekeres, (4,7)]. The average height if the tree is chosen at random is sqrt(2*n*Pi). - David desJardins, Jan 20 2017

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

Alois P. Heinz, Table of n, a(n) for n = 1..387
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
Index entries for sequences related to trees

Cf. A000435, A034855, A236396.

Also A234953(n) = a(n)/n.

nn=20;a=NestList[ x Exp[#]&,x,nn];f[list_]:=Sum[list[[i]]*i,{i,1,Length[list]}];Drop[Map[f,Transpose[Table[Range[0,nn]!CoefficientList[Series[a[[i+1]]-a[[i]],{x,0,nn}],x],{i,1,nn-1}]]],1]  (* Geoffrey Critzer, Mar 14 2013 *)

a(n) = Sum_{k=1..n-1} A034855(n,k)*k. - Geoffrey Critzer, Mar 14 2013

A000435(n)/a(n) ~ 1/2 (see A000435 and the Renyi-Szekeres result mentioned in the Comments). - David desJardins, Jan 20 2017

More terms from Geoffrey Critzer, Mar 14 2013

A234953 Normalized total height of all rooted trees on n labeled nodes.

Original entry on oeis.org

0, 1, 5, 37, 357, 4351, 64243, 1115899, 22316409, 505378207, 12789077631, 357769603027, 10965667062133, 365497351868767, 13163965052815515, 509522144541045811, 21093278144993719665, 930067462093579181119, 43518024090910884374263, 2153670733766937656155699

Offset: 1

N. J. A. Sloane, Jan 14 2014

nonn

Equals A001854(n)/n. That is, similar to A001854, except here the root always has the fixed label 1.

This was in one of my thesis notebooks from 1964 (see the scans in A000435), but because it wasn't of central importance it was never added to the OEIS.

Alois P. Heinz, Table of n, a(n) for n = 1..387

Cf. A001854, A034855, A235595, A236396.

gf[k_] := gf[k] = If[k == 0, x, x*E^gf[k-1]]; a[n_, k_] := n!*Coefficient[Series[gf[k], {x, 0, n+1}], x, n]; a[n_] := Sum[k*(a[n, k] - a[n, k-1]), {k, 1, n-1}]/n; Array[a, 20] (* Jean-François Alcover, Mar 18 2014, after Alois P. Heinz *)

from sympy import binomial
from sympy.core.cache import cacheit
@cacheit
def b(n, h): return 1 if min(n, h)==0 else sum([binomial(n - 1, j - 1)*j*b(j - 1, h - 1)*b(n - j, h) for j in range(1, n + 1)])
def T(n, k): return b(n - 1, k - 1) - b(n - 1, k - 2)
def a(n): return sum([k*T(n, k) for k in range(1, n)])
print([a(n) for n in range(1, 31)]) # Indranil Ghosh, Aug 26 2017

a(n) = Sum_{k=1..n-1} k*A034855(n,k)/n = Sum_{k=1..n-1} k*A235595(n,k).

A034977 Expansion of 1/(1-64*x)^(1/8), related to octo-factorial numbers A045755.

Original entry on oeis.org

1, 8, 288, 13056, 652800, 34467840, 1884241920, 105517547520, 6014500208640, 347504456499200, 20294260259553280, 1195516422562775040, 70933974405391319040, 4234212626044897198080, 254052757562693831884800, 15310912855778348268257280, 926310227774590070229565440

Offset: 0

Wolfdieter Lang

Seiichi Manyama, Table of n, a(n) for n = 0..500
Armin Straub, Victor H. Moll, and Tewodros Amdeberhan, The p-adic valuation of k-central binomial coefficients, Acta Arith. 140 (1) (2009), 31-41, eq. (1.10).
Index entries for sequences related to factorial numbers.

Cf. A004993, A034855, A045755, A203142.

[n le 1 select 8^(n-1) else 8*(8*n-15)*Self(n-1)/(n-1): n in [1..40]]; // G. C. Greubel, Oct 21 2022

CoefficientList[Series[1/(1-64x)^(1/8),{x,0,30}],x] (* Harvey P. Dale, May 20 2011 *)

[2^(6*n)*rising_factorial(1/8,n)/factorial(n) for n in range(40)] # G. C. Greubel, Oct 21 2022

a(n) = 8^n*A045755(n)/n!, n >= 1, where A045755(n) = (8*n-7)!^8 = Product_{j=1..n} (8*j-7).
G.f.: (1-64*x)^(-1/8).
D-finite with recurrence: n*a(n) = 8*(8*n-7)*a(n-1). - R. J. Mathar, Jan 28 2020
a(n) ~ 2^(6*n) * n^(-7/8) / Gamma(1/8). - Amiram Eldar, Aug 18 2025

a(11) corrected by Harvey P. Dale, May 20 2011

A236396 Triangle read by rows: T(n,k) = number of rooted labeled trees with n nodes and height <= k, for n >= 1, 0 <= k <= n-1.

Original entry on oeis.org

1, 0, 2, 0, 3, 9, 0, 4, 40, 64, 0, 5, 205, 505, 625, 0, 6, 1176, 4536, 7056, 7776, 0, 7, 7399, 46249, 89929, 112609, 117649, 0, 8, 50576, 526352, 1284032, 1835072, 2056832, 2097152, 0, 9, 372537, 6604497, 20351601, 33188481, 40325121, 42683841, 43046721

Offset: 1

N. J. A. Sloane, Jan 28 2014

If we replace each row by its differences we get A034855.

			Triangle begins:
[1],
[0, 2],
[0, 3, 9],
[0, 4, 40, 64],
[0, 5, 205, 505, 625],
[0, 6, 1176, 4536, 7056, 7776],
[0, 7, 7399, 46249, 89929, 112609, 117649],
[0, 8, 50576, 526352, 1284032, 1835072, 2056832, 2097152],
...

Alois P. Heinz, Rows n = 1..100, flattened
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478. [broken link]
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.

Cf. A034855, A001854, A235595, A234953.

gf:= proc(k) gf(k):= `if`(k=0, x, x*exp(gf(k-1))) end:
A:= proc(n, k) A(n, k):= n!*coeff(series(gf(k), x, n+1), x, n) end:
[seq([seq(A(n, d), d=0..n-1)], n=1..12)];

gf[k_] := gf[k] = If[k == 0, x, x*E^gf[k-1]]; a[n_, k_] := n!*Coefficient[Series[gf[k], {x, 0, n+1}], x, n]; Table[Table[a[n, d], {d, 0, n-1}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Mar 07 2014, after Maple *)

A291203 Number F(n,h,t) of forests of t labeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 1, 0, 3, 6, 0, 6, 0, 0, 0, 0, 0, 1, 0, 4, 24, 12, 0, 36, 24, 0, 24, 0, 0, 0, 0, 0, 0, 1, 0, 5, 80, 90, 20, 0, 200, 300, 60, 0, 300, 120, 0, 120, 0, 0, 0, 0, 0, 0, 0, 1, 0, 6, 240, 540, 240, 30, 0, 1170, 3000, 1260, 120, 0, 3360, 2520, 360, 0, 2520, 720, 0, 720, 0

Offset: 0

Alois P. Heinz, Aug 20 2017

Positive elements in column t=1 give A034855.
Elements in rows h=0 give A023531.
Elements in rows h=1 give A059297.
Positive row sums per layer give A235595.
Positive column sums per layer give A061356.

			n h\t: 0   1   2  3  4 5 : A235595 : A061356          : A000272
-----+-------------------+---------+------------------+--------
0 0  : 1                 :         :                  : 1
-----+-------------------+---------+------------------+--------
1 0  : 0   1             :      1  :   .              :
1 1  : 0                 :         :   1              : 1
-----+-------------------+---------+------------------+--------
2 0  : 0   0   1         :      1  :   .   .          :
2 1  : 0   2             :      2  :   .              :
2 2  : 0                 :         :   2   1          : 3
-----+-------------------+---------+------------------+--------
3 0  : 0   0   0  1      :      1  :   .   .   .      :
3 1  : 0   3   6         :      9  :   .   .          :
3 2  : 0   6             :      6  :   .              :
3 3  : 0                 :         :   9   6   1      : 16
-----+-------------------+---------+------------------+--------
4 0  : 0   0   0  0  1   :      1  :   .   .   .  .   :
4 1  : 0   4  24 12      :     40  :   .   .   .      :
4 2  : 0  36  24         :     60  :   .   .          :
4 3  : 0  24             :     24  :   .              :
4 4  : 0                 :         :  64  48  12  1   : 125
-----+-------------------+---------+------------------+--------
5 0  : 0   0   0  0  0 1 :      1  :   .   .   .  . . :
5 1  : 0   5  80 90 20   :    195  :   .   .   .  .   :
5 2  : 0 200 300 60      :    560  :   .   .   .      :
5 3  : 0 300 120         :    420  :   .   .          :
5 4  : 0 120             :    120  :   .              :
5 5  : 0                 :         : 625 500 150 20 1 : 1296
-----+-------------------+---------+------------------+--------

Alois P. Heinz, Layers n = 0..48, flattened

Cf. A000007, A000012, A000142, A000272, A000551, A001477, A001788, A001854, A002378, A023531, A034855, A038154, A059297, A061356, A089946, A126804, A234953, A235595, A235596, A243014, A291204, A291336, A291529.

b:= proc(n, t, h) option remember; expand(`if`(n=0 or h=0, x^(t*n), add(
       binomial(n-1, j-1)*j*x^t*b(j-1, 0, h-1)*b(n-j, t, h), j=1..n)))
    end:
g:= (n, h)-> b(n, 1, h)-`if`(h=0, 0, b(n, 1, h-1)):
F:= (n, h, t)-> coeff(g(n, h), x, t):
seq(seq(seq(F(n, h, t), t=0..n-h), h=0..n), n=0..8);

b[n_, t_, h_] := b[n, t, h] = Expand[If[n == 0 || h == 0, x^(t*n), Sum[
     Binomial[n-1, j-1]*j*x^t*b[j-1, 0, h-1]*b[n-j, t, h], {j, 1, n}]]];
g[n_, h_] := b[n, 1, h] - If[h == 0, 0, b[n, 1, h - 1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
Table[Table[Table[F[n, h, t], {t, 0, n - h}], {h, 0, n}], {n, 0, 8}] // Flatten (* Jean-François Alcover, Mar 17 2022, after Alois P. Heinz *)

Sum_{i=0..n} F(n,i,n-i) = A243014(n) = 1 + A038154(n).
Sum_{d=0..n} Sum_{i=0..d} F(n,i,d-i) = A000272(n+1).
Sum_{h=0..n} Sum_{t=0..n-h} t * F(n,h,t) = A089946(n-1) for n>0.
Sum_{h=0..n} Sum_{t=0..n-h} (h+1) * F(n,h,t) = A234953(n+1) for n>0.
Sum_{h=0..n} Sum_{t=0..n-h} (h+1)*(n+1) * F(n,h,t) = A001854(n+1) for n>0.
Sum_{t=0..n-1} F(n,1,t) = A235596(n+1).
F(2n,n,n) = A126804(n) for n>0.
F(n,0,n) = 1 = A000012(n).
F(n,1,1) = n = A001477(n) for n>1.
F(n,n-1,1) = n! = A000142(n) for n>0.
F(n,1,n-1) = A002378(n-1) for n>0.
F(n,2,1) = A000551(n).
F(n,3,1) = A000552(n).
F(n,4,1) = A000553(n).
F(n,1,2) = A001788(n-1) for n>2.
F(n,0,0) = A000007(n).

A034854 Triangle giving number of labeled trees with n >= 3 nodes and diameter d >= 2.

Original entry on oeis.org

3, 4, 12, 5, 60, 60, 6, 210, 720, 360, 7, 630, 6090, 7560, 2520, 8, 1736, 47040, 112560, 80640, 20160, 9, 4536, 363384, 1496880, 1829520, 907200, 181440, 10, 11430, 2913120, 19207440, 36892800, 28274400, 10886400, 1814400

Offset: 0

N. J. A. Sloane

			Triangle begins:
  3;
  4,   12;
  5,   60,   60;
  6,  210,  720,  360;
  7,  630, 6090, 7560, 2520;
  ...

J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.[broken link]
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
Index entries for sequences related to trees

Cf. A001852, A034855, A356292, A355671.

Reference gives recurrence.
From Geoffrey Critzer, Aug 02 2022: (Start)
Sum_{d even} a(n,d) = A356292(n) and Sum_{d odd} a(n,d) = A355671(n).
Let G_k(x) be the e.g.f. counting the number of rooted labeled trees with height <= k. Then G_k(x) is defined recursively by G_0(x) = x, G_k(x) = x*exp(G_{k-1}(x)). Let H_k(x) be the e.g.f. counting rooted labeled trees of height k. Then H_0(x) = x, H_k(x) = G_k(x) - G_{k-1}(x) for k >= 1. The e.g.f. for column d = 2*m+1 is H_m(x)^2/2. The e.g.f. for column d = 2*m is G_{m-1}(x)*(exp(H_{m-1}(x)) - 1 - H_{m-1}(x)). (End)

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 27 2004

Name corrected by Geoffrey Critzer, Aug 02 2022

A216242 Triangular array read by rows: T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} with a height of k; n>=1, 0<=k<=n-1.

Original entry on oeis.org

1, 2, 2, 6, 15, 6, 24, 124, 84, 24, 120, 1185, 1160, 540, 120, 720, 13086, 17610, 10560, 3960, 720, 5040, 165361, 296772, 214410, 104160, 32760, 5040, 40320, 2363320, 5536440, 4692576, 2686320, 1115520, 302400, 40320, 362880, 37780497, 113680800, 111488328, 72080064, 35637840, 12942720, 3084480, 362880

Offset: 1

Geoffrey Critzer, Mar 14 2013

Here, the height of a function f (represented as a directed graph) is the maximum distance from a recurrent element to any non-recurrent element. An element 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.
Row sums = n^n (A000312).
First column (k = 0) counts the n! bijective functions.
T(n,n-1) = n! (A000142).

			Triangle T(n,k) begins:
     1;
     2,       2;
     6,      15,       6;
    24,     124,      84,      24;
   120,    1185,    1160,     540,     120;
   720,   13086,   17610,   10560,    3960,    720;
  5040,  165361,  296772,  214410,  104160,  32760,   5040;
  ...

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

Cf. A001854, A034855.

G:= proc(k) G(k):= `if`(k=0, 0, x*exp(G(k-1))) end:
T:= (n, k)-> n!*coeff(series(1/(1-G(k+1))-1/(1-G(k)), x, n+1), x, n):
seq(seq(T(n, k), k=0..n-1), n=1..10); # Alois P. Heinz, Mar 14 2013

nn=8;a=NestList[x Exp[#]&,0,nn];f[list_]:=Sum[list[[i]]*i,{i,1,Length[list]}];g[list_]:=Select[list,#>0&];Map[g,Transpose[Table[Range[0,nn]!CoefficientList[Series[1/(1-a[[i+1]])-1/(1-a[[i]]),{x,0,nn}],x],{i,1,nn-1}]]]//Grid

Define G(k) recursively by G(k) = x*exp(G(k-1)) for k>0, G(0) = 0.

E.g.f. for column k is 1/(1-G(k+1)) - 1/(1-G(k)).

cp's OEIS Frontend

A235595 Triangle read by rows: the triangle in A034855, with the n-th row normalized by dividing it by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A001854 Total height of all rooted trees on n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A234953 Normalized total height of all rooted trees on n labeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

A034977 Expansion of 1/(1-64*x)^(1/8), related to octo-factorial numbers A045755.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A236396 Triangle read by rows: T(n,k) = number of rooted labeled trees with n nodes and height <= k, for n >= 1, 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A291203 Number F(n,h,t) of forests of t labeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A034854 Triangle giving number of labeled trees with n >= 3 nodes and diameter d >= 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula