A008295 Triangle read by rows: T(n,k) is the number of partially labeled rooted trees with n vertices, k of which are labeled, 0 <= k <= n.

1, 1, 1, 1, 2, 2, 2, 5, 9, 9, 4, 13, 34, 64, 64, 9, 35, 119, 326, 625, 625, 20, 95, 401, 1433, 4016, 7776, 7776, 48, 262, 1316, 5799, 21256, 60387, 117649, 117649, 115, 727, 4247, 22224, 100407, 373895, 1071904, 2097152, 2097152

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• tabl
• nice

Comments

T(n, k) where n counts the vertices and 0 <= k <= n counts the labels. - Sean A. Irvine, Mar 22 2018

Examples

			Triangle begins with T(0,0):
n\k 0  1   2    3    4    5    6
0   1
1   1  1
2   1  2   2
3   2  5   9    9
4   4 13  34   64   64
5   9 35 119  326  625  625
6  20 95 401 1433 4016 7776 7776
		

References

• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 134.

Links

• Sean A. Irvine, Table of n, a(n) for n = 0..527
• J. Riordan, The numbers of labeled colored and chromatic trees, Acta Mathematica 97 (1957) 211.
• Index entries for sequences related to rooted trees

Crossrefs

Main diagonal is A000169.

Columns k=0..6 are A000081, A000107, A000524, A000444, A000525, A064781, A064782.

Cf. A034799.

Programs

Mathematica

m = 9; r[_] = 0;
Do[r[x_] = x Exp[Sum[r[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, m}];
r[x_, y_] = -ProductLog[(-E^(-r[x])) r[x] - (r[x] y)/E^r[x]];
(CoefficientList[#, y] Range[0, Exponent[#, y]]!)& /@ CoefficientList[r[x, y] + O[x]^m, x] /. {} -> {1} // Flatten // Quiet (* Jean-François Alcover, Oct 23 2019 *)

Formula

E.g.f.: r(x,y) = T(n,k) * y^k * x^n / k! satisfies r(x,y) * exp(r(x)) = (1+y) * r(x) * exp(r(x,y)) where r(x) is the o.g.f. for A000081. - Sean A. Irvine, Mar 22 2018

Extensions

More terms from Sean A. Irvine, Mar 22 2018

Name edited by Andrew Howroyd, Mar 23 2023