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

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,1

Links

Table of n, a(n) for n=0..35.

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

Formula

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=2m+1 is H_m(x)^2/2. The e.g.f. for column d=2m is G_{m-1}(x)*(exp(H_{m-1}(x)) - 1 - H_{m-1}(x)). (End)

Example

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

Crossrefs

Cf. A001852, A034855, A356292, A355671.

Sequence in context: A354781 A097850 A238855 * A164982 A081837 A348996

Adjacent sequences: A034851 A034852 A034853 * A034855 A034856 A034857

Keyword

nonn,tabl,easy,nice

Author

N. J. A. Sloane

Extensions

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

Name corrected by Geoffrey Critzer, Aug 02 2022

Status

approved