login
A214568
Triangle read by rows: T(n,k) is the number of rooted trees t with n vertices yielding k distinct rooted trees with n+1 vertices when a pendant edge is added to a vertex of t (1 <= k <= n).
4
1, 0, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 3, 3, 0, 1, 1, 6, 6, 6, 0, 1, 3, 7, 11, 14, 12, 0, 1, 1, 11, 16, 29, 32, 25, 0, 1, 3, 11, 26, 46, 72, 75, 52, 0, 1, 2, 16, 27, 79, 122, 182, 177, 113, 0, 1, 3, 18, 42, 101, 217, 336, 457, 420, 247, 0, 1, 1, 20, 47, 149, 303, 621, 911, 1160, 1005, 548
OFFSET
1,10
COMMENTS
Row n contains n entries.
Sum_{k=1..n} T(n,k) = A000081(n) = number of rooted trees with n vertices.
Sum_{k=1..n} k*T(n,k) = A000107(n).
T(n,n) = A004111(n).
T(n,3) = A032741(n-1) = number of proper divisors of n-1; if d is a proper divisor of n-1 (= number of edges), consider d identical rooted trees with (n-1)/d edges, root degree 1, height 2 and identify their roots.
The bivariate g.f. can be computed with eq. (4.2) of Harary-Robinson. - R. J. Mathar, Sep 16 2015
LINKS
F. Harary, R. W. Robinson, Isomorphic factorizations VIII: bisectable trees, Combinatorica 4 (2) (1984) 169-179.
FORMULA
No formula available. Entries have been obtained by counting (using Maple) the rooted trees (identified by their Matula-Goebel numbers) with the required properties (using A061775 and A214567).
Bivariate g.f. T(x,y) = x * y * Product_{p>=1} Product_{k=1..p} (1 + x^p*y^k / (1-x^p))^(a(p,k)), where a(p,k) is the coefficient of x^p*y^k in T(x,y) [(4.2) from Harari and Robinson]. This allows incremental computation of the rows of the sequence by starting with T(x,y) = x*y (p=1) and increasing p by 1 for each row. - Sean A. Irvine, Oct 10 2017
EXAMPLE
Triangle starts:
1;
0, 1;
0, 1, 1;
0, 1, 1, 2;
0, 1, 2, 3, 3;
0, 1, 1, 6, 6, 6;
0, 1, 3, 7, 11, 14, 12;
0, 1, 1, 11, 16, 29, 32, 25;
Row 4 is 0,1,1,2 because the four rooted trees with 4 vertices generate 2,3,4,and 4 rooted trees with 5 vertices.
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jul 26 2012
STATUS
approved