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,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

Adjacent sequences: A339647 A339648 A339649 * A339651 A339652 A339653

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 14 2020

Status

approved