A228601 Triangle read by rows: T(n,k) is the number of trees with n vertices and having k distinct rootings (1 <= k <= n).

1, 1, 0, 0, 1, 0, 0, 2, 0, 0, 0, 1, 1, 1, 0, 0, 2, 1, 2, 1, 0, 0, 1, 2, 4, 1, 2, 1, 0, 2, 1, 7, 4, 4, 4, 1, 0, 1, 2, 7, 7, 9, 10, 8, 3, 0, 2, 3, 12, 10, 17, 19, 20, 17, 6, 0, 1, 2, 12, 14, 28, 37, 45, 46, 35, 15, 0, 2, 1, 18, 21, 46, 60, 87, 106, 103, 78, 29

Offset: 1

Author

Emeric Deutsch, Oct 20 2013

Keywords

• nonn
• tabl
• look

Comments

The entries in the triangle have been obtained - painstakingly - from the Read & Wilson reference (pp. 63-73); the white vertices indicate the possible distinct rootings for the given tree.

Examples

			Row 4 is 0,2,0,0 because the trees with 4 vertices are (i) the path tree abcd with 2 distinct rootings (at a and at b) and (ii) the star tree with 4 vertices having, obviously, 2 distinct rootings.
Triangle starts:
  1;
  1, 0;
  0, 1, 0;
  0, 2, 0, 0;
  0, 1, 1, 1, 0;
  0, 2, 1, 2, 1, 0;
  0, 1, 2, 4, 1, 2, 1;
		

References

• R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

Links

• Sean A. Irvine, Rows n=1..44 of triangle, flattened
• F. Harary, R. W. Robinson, Isomorphic factorizations VIII: bisectable trees, Combinatorica 4 (2) (1984) 169-179.

Crossrefs

Cf. A000055, A000081, A000220.

Formula

Sum of entries in row n = A000055(n).

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

T(n,n) = A000220(n).

Let A214568(x,y) be the bivariate g.f. of A214568, then this g.f. is A214568(x,y) -( [A214568(x,y)]^2 + A214568(x^2,y^2) )/2 + A214568(x^2,y), see eq. (4.8) by Harary-Robinson. - R. J. Mathar, Sep 16 2015