A339649 Array read by antidiagonals: T(n,k) is the number of leaf colored trees with n leaves of k colors and all non-leaf nodes having degree 3.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 1, 0, 1, 5, 10, 10, 6, 1, 0, 1, 6, 15, 20, 21, 12, 2, 0, 1, 7, 21, 35, 55, 63, 31, 2, 0, 1, 8, 28, 56, 120, 220, 227, 78, 4, 0, 1, 9, 36, 84, 231, 600, 1040, 891, 234, 6, 0, 1, 10, 45, 120, 406, 1386, 3530, 5480, 3876, 722, 11, 0

Offset: 0

Author

Andrew Howroyd, Dec 14 2020

Keywords

• nonn
• tabl

Comments

Not all k colors need to be used. The total number of nodes will be 2n-1.

See table 4.1 in the Johnson reference.

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 1   6    21     55     120     231      406 ...
5  | 0 1  12    63    220     600    1386     2842 ...
6  | 0 2  31   227   1040    3530    9772    23366 ...
7  | 0 2  78   891   5480   23250   77112   214718 ...
8  | 0 4 234  3876  31420  165510  655599  2122099 ...
9  | 0 6 722 17790 190360 1243825 5878446 22102577 ...
     ...
		

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.

Crossrefs

Columns k=1..4 are A129860, A220826, A220827, A220828.

Cf. A319539 (rooted), A339650, A339779.

Programs

PARI

\\ here U(n,k) gives column k 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)}
{my(T=Mat(vector(8, k, U(8, k-1)~))); for(n=1, #T~, print(T[n,]))}

Formula

G.f. of column k: 1 + R(x) + (R(x^3) - R(x)^3)/3 where R(x) is the g.f. of column k of A319539.