login
A319539
Array read by antidiagonals: T(n,k) is the number of binary rooted trees with n leaves of k colors and all non-leaf nodes having out-degree 2.
12
1, 2, 1, 3, 3, 1, 4, 6, 6, 2, 5, 10, 18, 18, 3, 6, 15, 40, 75, 54, 6, 7, 21, 75, 215, 333, 183, 11, 8, 28, 126, 495, 1260, 1620, 636, 23, 9, 36, 196, 987, 3600, 8010, 8208, 2316, 46, 10, 45, 288, 1778, 8568, 28275, 53240, 43188, 8610, 98, 11, 55, 405, 2970, 17934, 80136, 232500, 366680, 232947, 32763, 207
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
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
Columns 1..5 are A001190, A083563, A220816, A220817, A220818.
Main diagonal is A319580.
Sequence in context: A192001 A122176 A159881 * A098546 A126277 A253273
KEYWORD
nonn,tabl,look
AUTHOR
Andrew Howroyd, Sep 22 2018
STATUS
approved