|
|
A339067
|
|
Triangle read by rows: T(n,k) is the number of linear forests with n nodes and k rooted trees.
|
|
11
|
|
|
1, 1, 1, 2, 2, 1, 4, 5, 3, 1, 9, 12, 9, 4, 1, 20, 30, 25, 14, 5, 1, 48, 74, 69, 44, 20, 6, 1, 115, 188, 186, 133, 70, 27, 7, 1, 286, 478, 503, 388, 230, 104, 35, 8, 1, 719, 1235, 1353, 1116, 721, 369, 147, 44, 9, 1, 1842, 3214, 3651, 3168, 2200, 1236, 560, 200, 54, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
T(n,k) is the number of trees with n nodes rooted at two noninterchangeable nodes at a distance k-1 from each other.
|
|
LINKS
|
|
|
FORMULA
|
G.f. of k-th column: t(x)^k where t(x) is the g.f. of A000081.
|
|
EXAMPLE
|
Triangle begins:
1;
1, 1;
2, 2, 1;
4, 5, 3, 1;
9, 12, 9, 4, 1;
20, 30, 25, 14, 5, 1;
48, 74, 69, 44, 20, 6, 1;
115, 188, 186, 133, 70, 27, 7, 1;
286, 478, 503, 388, 230, 104, 35, 8, 1;
719, 1235, 1353, 1116, 721, 369, 147, 44, 9, 1;
...
|
|
MAPLE
|
b:= proc(n) option remember; `if`(n<2, n, (add(add(d*b(d),
d=numtheory[divisors](j))*b(n-j), j=1..n-1))/(n-1))
end:
T:= proc(n, k) option remember; `if`(k=1, b(n), (t->
add(T(j, t)*T(n-j, k-t), j=1..n-1))(iquo(k, 2)))
end:
# Using function PMatrix from A357368. Adds row and column for n, k = 0.
|
|
MATHEMATICA
|
b[n_] := b[n] = If[n < 2, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}])/(n - 1)];
T[n_, k_] := T[n, k] = If[k == 1, b[n], With[{t = Quotient[k, 2]}, Sum[T[j, t]*T[n - j, k - t], {j, 1, n - 1}]]];
|
|
PROG
|
TreeGf(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
ColSeq(n, k)={my(t=TreeGf(max(0, n+1-k))); Vec(t^k, -n)}
M(n, m=n)=Mat(vector(m, k, ColSeq(n, k)~))
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) }
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|