login
A228601
Triangle read by rows: T(n,k) is the number of trees with n vertices and having k distinct rootings (1 <= k <= n).
2
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
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
KEYWORD
nonn,tabl,look
AUTHOR
Emeric Deutsch, Oct 20 2013
STATUS
approved