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