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

1, 1, 1, 2, 1, 1, 4, 3, 2, 1, 9, 6, 6, 2, 1, 20, 16, 15, 8, 3, 1, 48, 37, 41, 22, 12, 3, 1, 115, 96, 106, 69, 38, 15, 4, 1, 286, 239, 284, 194, 124, 52, 20, 4, 1, 719, 622, 750, 564, 377, 189, 77, 24, 5, 1, 1842, 1607, 2010, 1584, 1144, 618, 292, 100, 30, 5, 1

Offset

1,4

Comments

Linear forests (A339067) are considered up to reversal of the linear order.

T(n,k) is the number of unlabeled trees on n nodes rooted at two indistinguishable nodes at distance k-1 from each other.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Formula

G.f of column k: (r(x)^k + r(x)^(k mod 2)*r(x^2)^floor(k/2))/2 where r(x) is the g.f. of A000081.

Example

Triangle read by rows:
    1;
    1,   1;
    2,   1,   1;
    4,   3,   2,   1;
    9,   6,   6,   2,   1;
   20,  16,  15,   8,   3,   1;
   48,  37,  41,  22,  12,   3,  1;
  115,  96, 106,  69,  38,  15,  4,  1;
  286, 239, 284, 194, 124,  52, 20,  4, 1;
  719, 622, 750, 564, 377, 189, 77, 24, 5, 1;
  ...

Prog

(PARI) \\ TreeGf is A000081 as g.f.
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(r=TreeGf(max(0, n+1-k))); Vec(r^k + r^(k%2)*subst(r, x, x^2)^(k\2), -n)/2}
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

Columns 1..4 are A000081, A027852, A280788(n-3), A339302.

Row sums are A303840(n+2).

Row sums excluding the first column are A303833.

Cf. A339067.

Sequence in context: A332056 A074744 A341474 * A369588 A010360 A262357

Adjacent sequences: A339300 A339301 A339302 * A339304 A339305 A339306

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 04 2020

Status

approved