A005197 - OEIS

%I M2663 #32 Aug 25 2017 16:39:28

%S 1,3,7,17,39,96,232,583,1474,3797,9864,25947,68738,183612,493471,

%T 1334143,3624800,9893860,27113492,74577187,205806860,569678759,

%U 1581243203,4400193551,12273287277,34307646762,96093291818,269654004899,758014312091,2134300171031

%N 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.

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

%H Alois P. Heinz, <a href="/A005197/b005197.txt">Table of n, a(n) for n = 1..600</a>

%H E. M. Palmer and A. J. Schwenk, <a href="http://dx.doi.org/10.1016/0095-8956(79)90073-X">On the number of trees in a random forest</a>, J. Combin. Theory, B 27 (1979), 109-121.

%F 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.

%F a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.955765285..., c = 2.85007275... . - _Vaclav Kotesovec_, Sep 10 2014

%p with(numtheory):

%p t:= proc(n) option remember; local d, j; `if`(n<=1, n,

%p       (add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))

%p     end:

%p b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,

%p       `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j) *

%p        binomial(t(i)+j-1, j), j=0..min(n/i, p)))))

%p     end:

%p a:= a-> add(k*b(n, n, k), k=1..n):

%p seq(a(n), n=1..40);  # _Alois P. Heinz_, Aug 20 2012

%t 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_ *)

%Y Cf. A000081, A005196, A033185.

%K nonn

%O 1,2

%A _N. J. A. Sloane_. Definition clarified by _N. J. A. Sloane_, May 29 2012

%E More terms from _Alois P. Heinz_, Aug 20 2012