OFFSET
1,2
COMMENTS
Not all k colors need to be used. The total number of nodes will be 2n-1.
See table 2.1 in the Johnson reference.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1275
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012.
FORMULA
T(1,k) = k.
T(n,k) = (1/2)*([n mod 2 == 0]*T(n/2,k) + Sum_{j=1..n-1} T(j,k)*T(n-j,k)).
G.f. of k-th column R(x) satisfies R(k) = k*x + (R(x)^2 + R(x^2))/2.
EXAMPLE
Array begins:
===========================================================
n\k| 1 2 3 4 5 6 7
---+-------------------------------------------------------
1 | 1 2 3 4 5 6 7 ...
2 | 1 3 6 10 15 21 28 ...
3 | 1 6 18 40 75 126 196 ...
4 | 2 18 75 215 495 987 1778 ...
5 | 3 54 333 1260 3600 8568 17934 ...
6 | 6 183 1620 8010 28275 80136 194628 ...
7 | 11 636 8208 53240 232500 785106 2213036 ...
8 | 23 2316 43188 366680 1979385 7960638 26037431 ...
9 | 46 8610 232947 2590420 17287050 82804806 314260765 ...
...
MAPLE
A:= proc(n, k) option remember; `if`(n<2, k*n, `if`(n::odd, 0,
(t-> t*(1-t)/2)(A(n/2, k)))+add(A(i, k)*A(n-i, k), i=1..n/2))
end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..12); # Alois P. Heinz, Sep 23 2018
MATHEMATICA
A[n_, k_] := A[n, k] = If[n<2, k*n, If[OddQ[n], 0, (#*(1-#)/2&)[A[n/2, k]]] + Sum[A[i, k]*A[n-i, k], {i, 1, n/2}]];
Table[A[n, d-n+1], {d, 1, 12}, {n, 1, d}] // Flatten (* Jean-François Alcover, Sep 02 2019, after Alois P. Heinz *)
PROG
(PARI) \\ here R(n, k) gives k-th column 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}
{my(T=Mat(vector(8, k, R(8, k)~))); for(n=1, #T~, print(T[n, ]))}
CROSSREFS
AUTHOR
Andrew Howroyd, Sep 22 2018
STATUS
approved