login
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.
11
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,5
COMMENTS
See table 2.2 in the Johnson reference.
LINKS
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012.
FORMULA
T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319539(n,i).
EXAMPLE
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;
...
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 *)
PROG
(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]))}
CROSSREFS
Columns 1..5 are A001190, A220819, A220820, A220821, A220822.
Main diagonal is A001147.
Row sums give A319590.
Sequence in context: A099406 A274601 A202696 * A239020 A293211 A330778
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Sep 22 2018
STATUS
approved