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.
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
Examples
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; ...
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.
Crossrefs
Programs
-
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]))}
Formula
T(n,k) = Sum_{i=0..k} (-1)^(k-i)*binomial(k,i)*A339649(n,i).
Comments