A005199 - OEIS

%I M3285 #23 Aug 02 2020 21:20:41

%S 0,1,1,4,6,18,35,93,214,549,1362,3534,9102,23951,63192,168561,451764,

%T 1219290,3305783,9008027,24643538,67681372,186504925,515566016,

%U 1429246490,3972598378,11068477743,30908170493,86488245455,242481159915,681048784377,1916051725977,5399062619966

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

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

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

%H Washington Bomfim, <a href="/A005199/b005199.txt">Table of n, a(n) for n = 1..120</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 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

%o (PARI) g(m) = {my(f); if(m==0, return(1)); f = vector(m+1); f[1]=1;

%o 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] };

%o global(max_n = 130); A000081 = vector(max_n, n, g(n-1));

%o F(n,t)={my(s=0, D, c, P_1); forpart(P_1 = n, D = Set(P_1); c = vector(#D);

%o for(k=1, #D, c[k] = #select(x->x == D[k], Vec(P_1)));

%o s += prod(k=1, #D, binomial( A000081[D[k]-1] + c[k] - 1, c[k]) )

%o ,[2,n],[t,t]); s};

%o seq(n) = sum(t=1,n\2, t*F(n,t) ); \\   _Washington Bomfim_, Jul 08 2020

%Y Cf. A000081, A336087.

%K nonn

%O 1,4

%A _N. J. A. Sloane_

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