login
A339650
Triangle read by rows: T(n,k) is the number of trees with n leaves of exactly k colors and all non-leaf nodes having degree 3.
7
1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 6, 3, 0, 1, 10, 30, 36, 15, 0, 2, 27, 140, 310, 300, 105, 0, 2, 74, 663, 2376, 3990, 3150, 945, 0, 4, 226, 3186, 17304, 44850, 59805, 39690, 10395, 0, 6, 710, 15642, 123508, 462735, 925890, 1018710, 582120, 135135
OFFSET
0,9
COMMENTS
See table 4.2 in the Johnson reference.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012.
FORMULA
T(n,k) = Sum_{i=0..k} (-1)^(k-i)*binomial(k,i)*A339649(n,i).
EXAMPLE
Triangle begins:
1;
0, 1;
0, 1, 1;
0, 1, 2, 1;
0, 1, 4, 6, 3;
0, 1, 10, 30, 36, 15;
0, 2, 27, 140, 310, 300, 105;
0, 2, 74, 663, 2376, 3990, 3150, 945;
0, 4, 226, 3186, 17304, 44850, 59805, 39690, 10395;
...
PROG
(PARI) \\ here U(n, k) is column k of A339649 as a vector.
R(n, k)={my(v=vector(n)); v[1]=k; for(n=2, n, v[n]=sum(j=1, (n-1)\2, v[j]*v[n-j]) + if(n%2, 0, binomial(v[n/2]+1, 2))); v}
U(n, k)={my(g=x*Ser(R(n, k))); Vec(1 + g + (subst(g + O(x*x^(n\3)), x, x^3) - g^3)/3)}
M(n, m=n)={my(v=vector(m+1, k, U(n, k-1)~)); Mat(vector(m+1, k, k--; sum(i=0, k, (-1)^(k-i)*binomial(k, i)*v[1+i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}
CROSSREFS
Columns k=1..4 are A129860, A220829, A220830, A220831.
Main diagonal is A001147(n-2) for n >= 2.
Row sums are A339651.
Cf. A319541 (rooted), A339649, A339780.
Sequence in context: A295683 A165519 A266972 * A266493 A075374 A293024
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Dec 14 2020
STATUS
approved