A339779 - OEIS

A339779

Array read by antidiagonals: T(n,k) is the number of homeomorphically irreducible leaf colored trees with n leaves of k colors.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 2, 0, 1, 5, 10, 10, 11, 3, 0, 1, 6, 15, 20, 36, 30, 7, 0, 1, 7, 21, 35, 90, 144, 105, 13, 0, 1, 8, 28, 56, 190, 476, 706, 380, 32, 0, 1, 9, 36, 84, 357, 1251, 3034, 3774, 1555, 73, 0, 1, 10, 45, 120, 616, 2814, 9845, 21380, 22140, 6650, 190, 0

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,8

COMMENTS

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

Not all colors need to be used.

The Johnson reference has a mistake in formula 4.3. In particular, the final term should be subtracted rather than added. Compare with the first formula given here. The table of results given in the reference is consequently also incorrect.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012. [Table 4.3 is an incorrect version of this table].

FORMULA

T(n,k) = k*g(n-1,k) + g(n,k) - Sum_{j=1..n-1} g(j,k)*g(n-j,k) for n > 1 where g(n,k) is A319254(n,k).

G.f. of k-th column: 1 + k*x*r(x) + r(x) - r(x)^2 where r(x) is the g.f. of the k-th column of A319254.

EXAMPLE

Array begins:

============================================================

n\k| 0 1 2 3 4 5 6 7

---+--------------------------------------------------------

0 | 1 1 1 1 1 1 1 1 ...

1 | 0 1 2 3 4 5 6 7 ...

2 | 0 1 3 6 10 15 21 28 ...

3 | 0 1 4 10 20 35 56 84 ...

4 | 0 2 11 36 90 190 357 616 ...

5 | 0 3 30 144 476 1251 2814 5656 ...

6 | 0 7 105 706 3034 9845 26383 61572 ...

7 | 0 13 380 3774 21380 85995 274800 744556 ...

8 | 0 32 1555 22140 163670 812160 3086481 9692480 ...

9 | 0 73 6650 137096 1322960 8092945 36550458 132954360 ...

...

PROG

(PARI) \\ here R(n, k) is k-th column of A319254.

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

{my(T=Mat(vector(9, k, U(8, k-1)~))); for(n=1, #T~, print(T[n, ]))}

CROSSREFS

Columns k=1..4 are A007827, A339782, A339783, A339784.

Cf. A319254 (planted), A339649 (degree <= 3), A339780.

Sequence in context: A321791 A339649 A349841 * A373449 A373424 A277504

Adjacent sequences: A339776 A339777 A339778 * A339780 A339781 A339782

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Dec 16 2020

STATUS

approved