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

1, 3, 7, 17, 39, 96, 232, 583, 1474, 3797, 9864, 25947, 68738, 183612, 493471, 1334143, 3624800, 9893860, 27113492, 74577187, 205806860, 569678759, 1581243203, 4400193551, 12273287277, 34307646762, 96093291818, 269654004899, 758014312091, 2134300171031

Offset: 1

Author

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

Keywords

• nonn

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..600
• 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, A005196, A033185.

Programs

Maple

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

Mathematica

t[1] = 1; t[n_] := t[n] = Module[{d, j}, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]; b[1, 1, 1] = 1; b[n_, i_, p_] := b[n, i, p] = If[p>n, 0, If[n == 0, 1, If[Min[i, p]<1, 0, Sum[b[n-i*j, i-1, p-j]*Binomial[t[i]+j-1, j], {j, 0, Min[n/i, p]}]]]]; a[n_] := Sum[k*b[n, n, k], {k, 1, n}]; Table[a[n] // FullSimplify, {n, 1, 30}] (* Jean-François Alcover, Mar 13 2014, after Alois P. Heinz *)

Formula

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

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.955765285..., c = 2.85007275... . - Vaclav Kotesovec, Sep 10 2014

Extensions

More terms from Alois P. Heinz, Aug 20 2012