|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
See table 2.2 in the Johnson reference.
|
|
LINKS
|
|
|
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):
|
|
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}];
|
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|