A336255 Irregular triangular array read by rows. T(n,k) is the number of rooted labeled trees on n nodes with path length exactly k, n>=1, 0<=k<=C(n,2).

1, 0, 2, 0, 0, 3, 6, 0, 0, 0, 4, 24, 12, 24, 0, 0, 0, 0, 5, 60, 120, 140, 120, 60, 120, 0, 0, 0, 0, 0, 6, 120, 540, 840, 1470, 720, 1440, 840, 720, 360, 720, 0, 0, 0, 0, 0, 0, 7, 210, 1680, 4620, 9240, 11382, 13440, 14700, 10920, 12810, 10080, 10080, 5880, 5040, 2520, 5040

Offset: 1

Author

Geoffrey Critzer, Jul 14 2020

Keywords

• nonn
• tabf

Comments

The path length of a tree is the distance from the root to a node summed over all nodes in the tree.

Examples

			1,
0, 2,
0, 0, 3, 6,
0, 0, 0, 4, 24, 12, 24,
0, 0, 0, 0, 5,  60, 120, 140, 120, 60, 120
		

Links

• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 185.

Crossrefs

Row sums give A000169.

Cf. A001864.

Programs

Mathematica

nn = 7; f[z_, u_] := Sum[Sum[a[n, k] u^k z^n/n!, {k, 0, Binomial[n, 2]}], {n, 1,
   nn}]; sol = SolveAlways[ Series[0 == f[z, u] - z Exp[f[u z, u]] , {z, 0, nn}], {z, u}];Level[Table[Table[a[n, k], {k, 0, Binomial[n, 2]}], {n, 1, nn}] /.
   sol, {2}] // Grid

Formula

E.g.f. satisfies A(x,y) = x*exp(A(y*x,y)).

Sum_{k=n-1..C(n,2)} T(n,k)*k = A001864(n).