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.

1, 1, 1, 1, 4, 3, 2, 14, 27, 15, 3, 48, 180, 240, 105, 6, 171, 1089, 2604, 2625, 945, 11, 614, 6333, 24180, 42075, 34020, 10395, 23, 2270, 36309, 207732, 554820, 755370, 509355, 135135, 46, 8518, 207255, 1710108, 6578550, 13408740, 14963130, 8648640, 2027025

Offset: 1

Author

Andrew Howroyd, Sep 22 2018

Keywords

• nonn
• tabl

Comments

See table 2.2 in the Johnson reference.

Examples

			Triangle begins:
   1;
   1,    1;
   1,    4,     3;
   2,   14,    27,     15;
   3,   48,   180,    240,    105;
   6,  171,  1089,   2604,   2625,    945;
  11,  614,  6333,  24180,  42075,  34020,  10395;
  23, 2270, 36309, 207732, 554820, 755370, 509355, 135135;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012.

Crossrefs

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

Main diagonal is A001147.

Row sums give A319590.

Cf. A241555, A319376, A319539.

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:
T:= (n, k)-> add((-1)^i*binomial(k, i)*A(n, k-i), i=0..k):
seq(seq(T(n, k), k=1..n), n=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}]];
T[n_, k_] := Sum[(-1)^i Binomial[k, i] A[n, k - i], {i, 0, k}];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 02 2019, after Alois P. Heinz *)

PARI

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

Formula

T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319539(n,i).