A258123 Irregular triangle read by rows: T(n,k) is the number of trees with n vertices that have k vertices of maximum degree (n, k>=1).

1, 0, 1, 1, 1, 1, 2, 0, 1, 4, 1, 0, 1, 8, 2, 0, 0, 1, 15, 6, 1, 0, 0, 1, 32, 11, 3, 0, 0, 0, 1, 68, 25, 10, 2, 0, 0, 0, 1, 156, 47, 25, 6, 0, 0, 0, 0, 1, 361, 105, 58, 24, 2, 0, 0, 0, 0, 1, 869, 227, 124, 69, 11, 0, 0, 0, 0, 0, 1, 2105, 556, 256, 185, 52, 4, 0, 0, 0, 0, 0, 1

Offset: 1

Author

Emeric Deutsch, Aug 19 2015

Keywords

• nonn
• tabf

Comments

Sum of entries in row n = A000055(n) = number of trees with n vertices.

Examples

			Triangle starts:
1;
0,1;
1;
1,1;
2,0,1;
4,1,0,1;
8,2,0,0,1;
Row 4 is 1,1; indeed, the star S(4) has degree sequence (0,0,0,1) and the path P(4) has degree sequence (1,1,2,2).
		

Crossrefs

Cf. A000055, A235111, A182907.

Formula

No formula for T(n,k) or generating function is known to the author. Row 5, for example, has been obtained in the following manner. The 3 trees with 5 vertices have M-indices 9,12,16 (the M-index of a tree T is the smallest of the Matula numbers of the rooted trees isomorphic (as a tree) to T; see A235111). In A182907 one finds the degree sequence (and the degree sequence polynomial) of a rooted tree with known Matula number. To the Matula numbers 9, 12, 16, there correspond the degree sequence polynomials 3x^2 + 2x, x^3 + x^2 + 3x, x^4 + 4x, respectively. From here, number of vertices of maximum degree are 3, 1, and 1, respectively. In other words, 2 trees have 1 vertex of maximum degree, 0 trees have 2 vertices of maximum degree, and 1 tree has 3 vertices of maximum degree; this leads us to row 5: 2, 0, 1.