A339784 -id:A339784 - cp's OEIS frontend

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

Andrew Howroyd, Dec 16 2020

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.

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

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

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

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

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

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.

cp's OEIS Frontend

A220835 Erroneous version of A339784.

Views

Author

Keywords

Comments

Links

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula