A339788 Triangle read by rows: T(n,k) is the number of forests with n unlabeled vertices and maximum vertex degree k, (0 <= k < n).

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 7, 6, 2, 1, 1, 3, 11, 13, 6, 2, 1, 1, 4, 17, 30, 15, 6, 2, 1, 1, 4, 25, 60, 39, 15, 6, 2, 1, 1, 5, 36, 128, 94, 41, 15, 6, 2, 1, 1, 5, 50, 254, 232, 103, 41, 15, 6, 2, 1, 1, 6, 70, 523, 561, 270, 105, 41, 15, 6, 2, 1

Offset

1,8

Comments

A forest is an acyclic graph.

(The component trees here are not rooted. - N. J. A. Sloane, Dec 19 2020)

Links

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

Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Formula

T(n,k) = A144215(n,k) - A144215(n,k-1) for k > 0.

Example

Triangle begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,   1;
  1, 2,  4,   2,   1;
  1, 3,  7,   6,   2,   1;
  1, 3, 11,  13,   6,   2,  1;
  1, 4, 17,  30,  15,   6,  2,  1;
  1, 4, 25,  60,  39,  15,  6,  2, 1;
  1, 5, 36, 128,  94,  41, 15,  6, 2, 1;
  1, 5, 50, 254, 232, 103, 41, 15, 6, 2, 1;
  ...

Prog

(PARI) \\ Here V(n, k) gives column k of A144528.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
MSet(p, k)={my(n=serprec(p, x)-1); if(min(k, n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k, n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n, k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={my(v=vector(m, k, EulerT(V(n, k-1)[2..1+n])~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) }

Crossrefs

Row sums are A005195.

Cf. A144215 (max degree <= k), A144528, A238414 (trees), A263293 (graphs).

Sequence in context: A034851 A172453 A172479 * A122085 A209612 A209805

Adjacent sequences: A339785 A339786 A339787 * A339789 A339790 A339791

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 18 2020

Status

approved