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.

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

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

Columns 1..5 are A001190, A083563, A220816, A220817, A220818.

Main diagonal is A319580.

Cf. A241555, A319254, A319541.

Sequence in context: A192001 A122176 A159881 * A098546 A126277 A253273

Adjacent sequences: A319536 A319537 A319538 * A319540 A319541 A319542

Keyword

nonn,tabl,look

Author

Andrew Howroyd, Sep 22 2018

Status

approved