A319541 - OEIS

%I #22 Apr 20 2023 14:56:43

%S 1,1,1,1,4,3,2,14,27,15,3,48,180,240,105,6,171,1089,2604,2625,945,11,

%T 614,6333,24180,42075,34020,10395,23,2270,36309,207732,554820,755370,

%U 509355,135135,46,8518,207255,1710108,6578550,13408740,14963130,8648640,2027025

%N 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 See table 2.2 in the Johnson reference.

%H Alois P. Heinz, <a href="/A319541/b319541.txt">Rows n = 1..141, flattened</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(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319539(n,i).

%e Triangle begins:

%e    1;

%e    1,    1;

%e    1,    4,     3;

%e    2,   14,    27,     15;

%e    3,   48,   180,    240,    105;

%e    6,  171,  1089,   2604,   2625,    945;

%e   11,  614,  6333,  24180,  42075,  34020,  10395;

%e   23, 2270, 36309, 207732, 554820, 755370, 509355, 135135;

%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 T:= (n, k)-> add((-1)^i*binomial(k, i)*A(n, k-i), i=0..k):

%p seq(seq(T(n, k), k=1..n), n=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 T[n_, k_] := Sum[(-1)^i Binomial[k, i] A[n, k - i], {i, 0, k}];

%t Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Sep 02 2019, after _Alois P. Heinz_ *)

%o (PARI) \\ here R(n,k) is k-th column of A319539 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 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 {my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}

%Y Columns 1..5 are A001190, A220819, A220820, A220821, A220822.

%Y Main diagonal is A001147.

%Y Row sums give A319590.

%Y Cf. A241555, A319376, A319539.

%K nonn,tabl

%O 1,5

%A _Andrew Howroyd_, Sep 22 2018