cp's OEIS Frontend

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

%I A339067 #24 Oct 07 2022 05:27:49
%S A339067 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 A339067 115,188,186,133,70,27,7,1,286,478,503,388,230,104,35,8,1,719,1235,
%U A339067 1353,1116,721,369,147,44,9,1,1842,3214,3651,3168,2200,1236,560,200,54,10,1
%N A339067 Triangle read by rows: T(n,k) is the number of linear forests with n nodes and k rooted trees.
%C A339067 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 A339067 Also the convolution triangle of A000081. - _Peter Luschny_, Oct 07 2022
%H A339067 Alois P. Heinz, <a href="/A339067/b339067.txt">Rows n = 1..200, flattened</a>
%F A339067 G.f. of k-th column: t(x)^k where t(x) is the g.f. of A000081.
%F A339067 Sum_{k=1..n} k * T(n,k) = A038002(n). - _Alois P. Heinz_, Dec 04 2020
%e A339067 Triangle begins:
%e A339067     1;
%e A339067     1,    1;
%e A339067     2,    2,    1;
%e A339067     4,    5,    3,    1;
%e A339067     9,   12,    9,    4,   1;
%e A339067    20,   30,   25,   14,   5,   1;
%e A339067    48,   74,   69,   44,  20,   6,   1;
%e A339067   115,  188,  186,  133,  70,  27,   7,  1;
%e A339067   286,  478,  503,  388, 230, 104,  35,  8, 1;
%e A339067   719, 1235, 1353, 1116, 721, 369, 147, 44, 9, 1;
%e A339067   ...
%p A339067 b:= proc(n) option remember; `if`(n<2, n, (add(add(d*b(d),
%p A339067       d=numtheory[divisors](j))*b(n-j), j=1..n-1))/(n-1))
%p A339067     end:
%p A339067 T:= proc(n, k) option remember; `if`(k=1, b(n), (t->
%p A339067       add(T(j, t)*T(n-j, k-t), j=1..n-1))(iquo(k, 2)))
%p A339067     end:
%p A339067 seq(seq(T(n, k), k=1..n), n=1..12);  # _Alois P. Heinz_, Dec 04 2020
%p A339067 # Using function PMatrix from A357368. Adds row and column for n, k = 0.
%p A339067 PMatrix(10, A000081); # _Peter Luschny_, Oct 07 2022
%t A339067 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 A339067 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 A339067 Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Jan 03 2021, after _Alois P. Heinz_ *)
%o A339067 (PARI) \\ TreeGf is A000081.
%o A339067 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 A339067 ColSeq(n,k)={my(t=TreeGf(max(0,n+1-k))); Vec(t^k, -n)}
%o A339067 M(n, m=n)=Mat(vector(m, k, ColSeq(n,k)~))
%o A339067 { my(T=M(12)); for(n=1, #T~, print(T[n,1..n])) }
%Y A339067 Columns 1..6 are A000081, A000106, A000242, A000300, A000343, A000395.
%Y A339067 Row sums are A000107.
%Y A339067 T(2n-1,n) gives A339440.
%Y A339067 Cf. A033185, A038002, A217781, A339428.
%K A339067 nonn,tabl
%O A339067 1,4
%A A339067 _Andrew Howroyd_, Dec 03 2020