|
%I M0776 #56 Aug 09 2021 21:29:29
%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
%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
%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. A000055, A095133 (by number of trees), A136605 (by number of edges), A144958 (first differences).
%Y A diagonal of A144215.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Sep 05 2002
|
