A005199 a(n) = Sum_t t*F(n,t), where F(n,t) is the number of forests with n (unlabeled) nodes and exactly t trees, all of which are planted (that is, rooted trees in which the root has degree 1).

0, 1, 1, 4, 6, 18, 35, 93, 214, 549, 1362, 3534, 9102, 23951, 63192, 168561, 451764, 1219290, 3305783, 9008027, 24643538, 67681372, 186504925, 515566016, 1429246490, 3972598378, 11068477743, 30908170493, 86488245455, 242481159915, 681048784377, 1916051725977, 5399062619966

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

The triangular array F(n,t) (analogous to A095133 for A005196 and A033185 for A005197) is A336087.

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Washington Bomfim, Table of n, a(n) for n = 1..120
• E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.

Crossrefs

Cf. A000081, A336087.

Programs

PARI

g(m) = {my(f); if(m==0, return(1)); f = vector(m+1); f[1]=1;
for(j=1, m, f[j+1]=1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1])); f[m+1] };
global(max_n = 130); A000081 = vector(max_n, n, g(n-1));
F(n,t)={my(s=0, D, c, P_1); forpart(P_1 = n, D = Set(P_1); c = vector(#D);
for(k=1, #D, c[k] = #select(x->x == D[k], Vec(P_1)));
s += prod(k=1, #D, binomial( A000081[D[k]-1] + c[k] - 1, c[k]) )
,[2,n],[t,t]); s};
seq(n) = sum(t=1,n\2, t*F(n,t) ); \\   Washington Bomfim, Jul 08 2020

Formula

a(n) = Sum_{t=1, floor(n/2)}( t*F(n,t) ), where F(n,t) = Sum_{P_1(n,t)} (Product_{k=2..n} binomial(A000081(k-1) + c_k - 1, c_k)), where P_1(n, t) is the set of the partitions of n with t parts greater than one: 2*c_2 + ... + n*c_n = n; c_2, ..., c_n >= 0. - Washington Bomfim, Jul 08 2020

Extensions

Definition clarified by N. J. A. Sloane, May 29 2012