A005196 a(n) = Sum_t t*F(n,t), where F(n,t) (see A095133) is the number of forests with n (unlabeled) nodes and exactly t trees.

1, 3, 6, 13, 24, 49, 93, 190, 381, 803, 1703, 3755, 8401, 19338, 45275, 108229, 262604, 647083, 1613941, 4072198, 10374138, 26663390, 69056163, 180098668, 472604314, 1247159936, 3307845730, 8814122981, 23585720703, 63359160443, 170815541708, 462049250165

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..300
• E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121. [The 17th entry is wrong]
• Eric Weisstein's World of Mathematics, Forest

Crossrefs

Cf. A000055, A005195, A095133.

Programs

Maple

with(numtheory):
b:= proc(n) option remember; local d, j; `if` (n<=1, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
t:= proc(n) option remember; local k; `if` (n=0, 1,
      b(n)-(add(b(k)*b(n-k), k=0..n)-`if`(irem(n, 2)=0, b(n/2), 0))/2)
    end:
g:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(g(n-i*j, i-1, p-j) *
       binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
    end:
a:= n-> add(k*g(n, n, k), k=1..n):
seq(a(n), n=1..40);  # Alois P. Heinz, Aug 20 2012

Mathematica

nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);ft=Table[a[i]-Sum[a[j]a[i-j],{j,1,i/2}]+If[OddQ[i],0,a[i/2](a[i/2]+1)/2],{i,1,nn}];CoefficientList[Series[D[Product[1/(1-y x^i)^ft[[i]],{i,1,nn}],y]/.y->1,{x,0,20}],x]  (* Geoffrey Critzer, Oct 13 2012, after code given by Robert A. Russell in A000055 *)

Formula

To get a(n), take row n of the triangle in A095133, multiply successive terms by 1, 2, 3, ... and sum. E.g., a(4) = 1*2 + 2*2 + 3*1 + 4*1 = 13.

Extensions

More terms from Vladeta Jovovic, Jun 03 2004

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