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
Examples
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 ... ...
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.
Crossrefs
Programs
-
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 *) -
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,]))}
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.
Comments