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

%I #24 Oct 07 2022 05:27:49

%S 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,

%T 115,188,186,133,70,27,7,1,286,478,503,388,230,104,35,8,1,719,1235,

%U 1353,1116,721,369,147,44,9,1,1842,3214,3651,3168,2200,1236,560,200,54,10,1

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

%C T(n,k) is the number of trees with n nodes rooted at two noninterchangeable nodes at a distance k-1 from each other.

%C Also the convolution triangle of A000081. - _Peter Luschny_, Oct 07 2022

%H Alois P. Heinz, <a href="/A339067/b339067.txt">Rows n = 1..200, flattened</a>

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

%F Sum_{k=1..n} k * T(n,k) = A038002(n). - _Alois P. Heinz_, Dec 04 2020

%e Triangle begins:

%e 1;

%e 1, 1;

%e 2, 2, 1;

%e 4, 5, 3, 1;

%e 9, 12, 9, 4, 1;

%e 20, 30, 25, 14, 5, 1;

%e 48, 74, 69, 44, 20, 6, 1;

%e 115, 188, 186, 133, 70, 27, 7, 1;

%e 286, 478, 503, 388, 230, 104, 35, 8, 1;

%e 719, 1235, 1353, 1116, 721, 369, 147, 44, 9, 1;

%e ...

%p b:= proc(n) option remember; `if`(n<2, n, (add(add(d*b(d),

%p d=numtheory[divisors](j))*b(n-j), j=1..n-1))/(n-1))

%p end:

%p T:= proc(n, k) option remember; `if`(k=1, b(n), (t->

%p add(T(j, t)*T(n-j, k-t), j=1..n-1))(iquo(k, 2)))

%p end:

%p seq(seq(T(n, k), k=1..n), n=1..12); # _Alois P. Heinz_, Dec 04 2020

%p # Using function PMatrix from A357368. Adds row and column for n, k = 0.

%p PMatrix(10, A000081); # _Peter Luschny_, Oct 07 2022

%t 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 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}]]];

%t Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Jan 03 2021, after _Alois P. Heinz_ *)

%o (PARI) \\ TreeGf is A000081.

%o 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)}

%o ColSeq(n,k)={my(t=TreeGf(max(0,n+1-k))); Vec(t^k, -n)}

%o M(n, m=n)=Mat(vector(m, k, ColSeq(n,k)~))

%o { my(T=M(12)); for(n=1, #T~, print(T[n,1..n])) }

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

%Y Row sums are A000107.

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

%Y Cf. A033185, A038002, A217781, A339428.

%K nonn,tabl

%O 1,4

%A _Andrew Howroyd_, Dec 03 2020