|
%I #24 Apr 20 2023 14:56:47
%S 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,
%T 11,8,28,126,495,1260,1620,636,23,9,36,196,987,3600,8010,8208,2316,46,
%U 10,45,288,1778,8568,28275,53240,43188,8610,98,11,55,405,2970,17934,80136,232500,366680,232947,32763,207
%N 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.
%C Not all k colors need to be used. The total number of nodes will be 2n-1.
%C See table 2.1 in the Johnson reference.
%H Andrew Howroyd, <a href="/A319539/b319539.txt">Table of n, a(n) for n = 1..1275</a>
%H Virginia Perkins Johnson, <a href="https://people.math.sc.edu/czabarka/Theses/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. South Carolina, 2012.
%F T(1,k) = k.
%F 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)).
%F G.f. of k-th column R(x) satisfies R(k) = k*x + (R(x)^2 + R(x^2))/2.
%e Array begins:
%e ===========================================================
%e n\k| 1 2 3 4 5 6 7
%e ---+-------------------------------------------------------
%e 1 | 1 2 3 4 5 6 7 ...
%e 2 | 1 3 6 10 15 21 28 ...
%e 3 | 1 6 18 40 75 126 196 ...
%e 4 | 2 18 75 215 495 987 1778 ...
%e 5 | 3 54 333 1260 3600 8568 17934 ...
%e 6 | 6 183 1620 8010 28275 80136 194628 ...
%e 7 | 11 636 8208 53240 232500 785106 2213036 ...
%e 8 | 23 2316 43188 366680 1979385 7960638 26037431 ...
%e 9 | 46 8610 232947 2590420 17287050 82804806 314260765 ...
%e ...
%p A:= proc(n, k) option remember; `if`(n<2, k*n, `if`(n::odd, 0,
%p (t-> t*(1-t)/2)(A(n/2, k)))+add(A(i, k)*A(n-i, k), i=1..n/2))
%p end:
%p seq(seq(A(n, 1+d-n), n=1..d), d=1..12); # _Alois P. Heinz_, Sep 23 2018
%t 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}]];
%t Table[A[n, d-n+1], {d, 1, 12}, {n, 1, d}] // Flatten (* _Jean-François Alcover_, Sep 02 2019, after _Alois P. Heinz_ *)
%o (PARI) \\ here R(n,k) gives k-th column as a vector.
%o 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}
%o {my(T=Mat(vector(8, k, R(8, k)~))); for(n=1, #T~, print(T[n,]))}
%Y Columns 1..5 are A001190, A083563, A220816, A220817, A220818.
%Y Main diagonal is A319580.
%Y Cf. A241555, A319254, A319541.
%K nonn,tabl,look
%O 1,2
%A _Andrew Howroyd_, Sep 22 2018
|
