A339067 Triangle read by rows: T(n,k) is the number of linear forests with n nodes and k rooted trees.

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

Offset: 1

Author

Andrew Howroyd, Dec 03 2020

Keywords

• nonn
• tabl

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.

Also the convolution triangle of A000081. - Peter Luschny, Oct 07 2022

Examples

			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;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..200, flattened

Crossrefs

Columns 1..6 are A000081, A000106, A000242, A000300, A000343, A000395.

Row sums are A000107.

T(2n-1,n) gives A339440.

Cf. A033185, A038002, A217781, A339428.

Programs

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:
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Dec 04 2020
# Using function PMatrix from A357368. Adds row and column for n, k = 0.
PMatrix(10, A000081); # Peter Luschny, Oct 07 2022

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}]]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz *)

PARI

\\ TreeGf is A000081.
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])) }

Formula

G.f. of k-th column: t(x)^k where t(x) is the g.f. of A000081.

Sum_{k=1..n} k * T(n,k) = A038002(n). - Alois P. Heinz, Dec 04 2020