cp's OEIS Frontend

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.

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