A339780 Triangle read by rows: T(n,k) is the number of homeomorphically irreducible leaf colored trees with n leaves using exactly k colors.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 2, 7, 9, 4, 0, 3, 24, 63, 68, 26, 0, 7, 91, 412, 812, 720, 236, 0, 13, 354, 2673, 8512, 13100, 9672, 2752, 0, 32, 1491, 17571, 84312, 199820, 248904, 156492, 39208, 0, 73, 6504, 117365, 814184, 2782970, 5194580, 5408620, 2953792, 660032

Offset

0,9

Comments

Homeomorphically irreducible trees are trees without vertices of degree 2. All non-leaf nodes then have degree >= 3.

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.

Example

Triangle begins:
  1;
  0,  1;
  0,  1,    1;
  0,  1,    2,     1;
  0,  2,    7,     9,     4;
  0,  3,   24,    63,    68,     26;
  0,  7,   91,   412,   812,    720,    236;
  0, 13,  354,  2673,  8512,  13100,   9672,   2752;
  0, 32, 1491, 17571, 84312, 199820, 248904, 156492, 39208;
  ...

Prog

(PARI) \\ here U(n, k) is A339779 as vector.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}
U(n, k)={my(g=x*Ser(R(n, k))); Vec(1 + g + k*x*g - g^2)}
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(8)); for(n=1, #T~, print(T[n, 1..n])); }

Crossrefs

Columns k=1..4 are A007827(n>0), A339785, A339786, A339787.

Main diagonal is A000311(n>0).

Row sums are A339781.

Cf. A319376 (planted), A339650 (degree <= 3), A339779.

Sequence in context: A029584 A318931 A266878 * A199469 A266832 A373570

Adjacent sequences: A339777 A339778 A339779 * A339781 A339782 A339783

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 16 2020

Status

approved