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

Author

Andrew Howroyd, Dec 14 2020

Keywords

• nonn
• tabl

Comments

See table 4.2 in the Johnson reference.

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

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.

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).