|
%I M2567 #44 Oct 02 2017 02:14:37
%S 1,3,6,13,24,49,93,190,381,803,1703,3755,8401,19338,45275,108229,
%T 262604,647083,1613941,4072198,10374138,26663390,69056163,180098668,
%U 472604314,1247159936,3307845730,8814122981,23585720703,63359160443,170815541708,462049250165
%N 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.
%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="/A005196/b005196.txt">Table of n, a(n) for n = 1..300</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. [The 17th entry is wrong]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Forest.html">Forest</a>
%F 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.
%p with(numtheory):
%p b:= proc(n) option remember; local d, j; `if` (n<=1, n,
%p (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
%p end:
%p t:= proc(n) option remember; local k; `if` (n=0, 1,
%p b(n)-(add(b(k)*b(n-k), k=0..n)-`if`(irem(n, 2)=0, b(n/2), 0))/2)
%p end:
%p g:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
%p `if`(min(i, p)<1, 0, add(g(n-i*j, i-1, p-j) *
%p binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
%p end:
%p a:= n-> add(k*g(n, n, k), k=1..n):
%p seq(a(n), n=1..40); # _Alois P. Heinz_, Aug 20 2012
%t 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 *)
%Y Cf. A000055, A005195, A095133.
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Jun 03 2004
%E Definition clarified by _N. J. A. Sloane_, May 29 2012
|
