%I M0776 #66 Aug 01 2024 01:21:56
%S 1,1,2,3,6,10,20,37,76,153,329,710,1601,3658,8599,20514,49905,122963,
%T 307199,775529,1977878,5086638,13184156,34402932,90328674,238474986,
%U 632775648,1686705630,4514955632,12132227370,32717113805,88519867048,240235675303
%N Number of forests with n unlabeled nodes.
%C Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - _N. J. A. Sloane_, Dec 04 2015
%C Number of unlabeled acyclic graphs on n vertices. The labeled version is A001858. The covering case is A144958, connected A000055. - _Gus Wiseman_, Apr 29 2024
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.
%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="/A005195/b005195.txt">Table of n, a(n) for n = 0..1000</a> (first 201 terms from T. D. Noe)
%H S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.
%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.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H Peter Steinbach, <a href="/A000055/a000055_12.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H Peter Steinbach, <a href="/A000664/a000664_5.pdf">Field Guide to Simple Graphs, Volume 4</a>, Part 5 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Forest.html">Forest.</a>
%H <a href="/index/Fo#forests">Index entries for sequences related to forests</a>
%F Euler transform of A000055: Product_{n>0} (1-x^n)^(-A000055(n)). a(n) = 1/n*Sum_{k=1..n} b(k)*a(n-k), where b(k) = Sum_{d divides k} d*A000055(d). - _Vladeta Jovovic_, Sep 05 2002
%F G.f.: exp(sum_{k>0} B(x^k)/k ), where B(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + ... = C(x)-1 and C is the g.f. for A000055.
%F a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 1.023158422... . - _Vaclav Kotesovec_, Nov 16 2014
%F First differences are A144958. - _Gus Wiseman_, Apr 29 2024
%e From _Gus Wiseman_, Apr 29 2024: (Start)
%e Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 10 forests:
%e {} {} {} {} {} {}
%e {12} {12} {12} {12}
%e {13,23} {12,34} {12,34}
%e {13,23} {13,23}
%e {13,24,34} {12,35,45}
%e {14,24,34} {13,24,34}
%e {14,24,34}
%e {13,24,35,45}
%e {14,25,35,45}
%e {15,25,35,45}
%e (End)
%t EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1 - x^Range[m])^seq), {x, 0, m}], x]];
%t b[n_] := b[n] = If[n <= 1, n, Sum[ Sum[ d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}]/(n - 1)];
%t a55[n_] := a55[n] = If[n == 0, 1, b[n] - (Sum[ b[k]*b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; A000055 = Table[ a55[n], {n, 1, 31}]; EulerTransform[ A000055 ] (* _Jean-François Alcover_, Mar 15 2012 *)
%Y Cf. A095133 (by number of trees), A136605 (by number of edges).
%Y A diagonal of A144215.
%Y The connected case is A000055.
%Y The labeled version is A001858.
%Y The covering case is A144958, labeled A105784.
%Y For triangles instead of cycles we have A006785, covering A372169.
%Y Unique cycle: A236570 (labeled A372193), covering A372191 (labeled A372195).
%Y A006125 counts simple graphs, unlabeled A000088.
%Y A006129 counts covering graphs, unlabeled A002494.
%Y Cf. A000272, A002807, A054548, A137917, A367863, A372176.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Sep 05 2002