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. (Formerly M2567)

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,2

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

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.

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 *)

Crossrefs

Cf. A000055, A005195, A095133.

Sequence in context: A191782 A358905 A027999 * A350851 A320286 A032287

Adjacent sequences: A005193 A005194 A005195 * A005197 A005198 A005199

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Jun 03 2004

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

Status

approved