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

Offset: 0

Author

Andrew Howroyd, Dec 16 2020

Keywords

• nonn
• tabl

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.

Examples

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

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

Crossrefs

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

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

Programs

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

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.