cp's OEIS Frontend

A319541 Triangle read by rows: T(n,k) is the number of binary rooted trees with n leaves of exactly k colors and all non-leaf nodes having out-degree 2.

%I A319541 #22 Apr 20 2023 14:56:43
%S A319541 1,1,1,1,4,3,2,14,27,15,3,48,180,240,105,6,171,1089,2604,2625,945,11,
%T A319541 614,6333,24180,42075,34020,10395,23,2270,36309,207732,554820,755370,
%U A319541 509355,135135,46,8518,207255,1710108,6578550,13408740,14963130,8648640,2027025
%N A319541 Triangle read by rows: T(n,k) is the number of binary rooted trees with n leaves of exactly k colors and all non-leaf nodes having out-degree 2.
%C A319541 See table 2.2 in the Johnson reference.
%H A319541 Alois P. Heinz, <a href="/A319541/b319541.txt">Rows n = 1..141, flattened</a>
%H A319541 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 A319541 T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319539(n,i).
%e A319541 Triangle begins:
%e A319541    1;
%e A319541    1,    1;
%e A319541    1,    4,     3;
%e A319541    2,   14,    27,     15;
%e A319541    3,   48,   180,    240,    105;
%e A319541    6,  171,  1089,   2604,   2625,    945;
%e A319541   11,  614,  6333,  24180,  42075,  34020,  10395;
%e A319541   23, 2270, 36309, 207732, 554820, 755370, 509355, 135135;
%e A319541   ...
%p A319541 A:= proc(n, k) option remember; `if`(n<2, k*n, `if`(n::odd, 0,
%p A319541       (t-> t*(1-t)/2)(A(n/2, k)))+add(A(i, k)*A(n-i, k), i=1..n/2))
%p A319541     end:
%p A319541 T:= (n, k)-> add((-1)^i*binomial(k, i)*A(n, k-i), i=0..k):
%p A319541 seq(seq(T(n, k), k=1..n), n=1..12);  # _Alois P. Heinz_, Sep 23 2018
%t A319541 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 A319541 T[n_, k_] := Sum[(-1)^i Binomial[k, i] A[n, k - i], {i, 0, k}];
%t A319541 Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Sep 02 2019, after _Alois P. Heinz_ *)
%o A319541 (PARI) \\ here R(n,k) is k-th column of A319539 as a vector.
%o A319541 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 A319541 M(n)={my(v=vector(n, k, R(n,k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*v[i])))}
%o A319541 {my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}
%Y A319541 Columns 1..5 are A001190, A220819, A220820, A220821, A220822.
%Y A319541 Main diagonal is A001147.
%Y A319541 Row sums give A319590.
%Y A319541 Cf. A241555, A319376, A319539.
%K A319541 nonn,tabl
%O A319541 1,5
%A A319541 _Andrew Howroyd_, Sep 22 2018