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

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.

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.

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

Example

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;

Crossrefs

Cf. A000055, A000081, A000220.

Sequence in context: A337821 A143078 A106405 * A363856 A369354 A360115

Adjacent sequences: A228598 A228599 A228600 * A228602 A228603 A228604

Keyword

nonn,tabl,look

Author

Emeric Deutsch, Oct 20 2013

Status

approved