cp's OEIS Frontend

A005195 Number of forests with n unlabeled nodes.

%I A005195 M0776 #67 Feb 16 2025 08:32:28
%S A005195 1,1,2,3,6,10,20,37,76,153,329,710,1601,3658,8599,20514,49905,122963,
%T A005195 307199,775529,1977878,5086638,13184156,34402932,90328674,238474986,
%U A005195 632775648,1686705630,4514955632,12132227370,32717113805,88519867048,240235675303
%N A005195 Number of forests with n unlabeled nodes.
%C A005195 Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - _N. J. A. Sloane_, Dec 04 2015
%C A005195 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 A005195 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.
%D A005195 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005195 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 A005195 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 A005195 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 A005195 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A005195 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 A005195 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 A005195 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Forest.html">Forest.</a>
%H A005195 <a href="/index/Fo#forests">Index entries for sequences related to forests</a>
%F A005195 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 A005195 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 A005195 a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 1.023158422... . - _Vaclav Kotesovec_, Nov 16 2014
%F A005195 First differences are A144958. - _Gus Wiseman_, Apr 29 2024
%e A005195 From _Gus Wiseman_, Apr 29 2024: (Start)
%e A005195 Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 10 forests:
%e A005195   {}  {}  {}    {}       {}          {}
%e A005195           {12}  {12}     {12}        {12}
%e A005195                 {13,23}  {12,34}     {12,34}
%e A005195                          {13,23}     {13,23}
%e A005195                          {13,24,34}  {12,35,45}
%e A005195                          {14,24,34}  {13,24,34}
%e A005195                                      {14,24,34}
%e A005195                                      {13,24,35,45}
%e A005195                                      {14,25,35,45}
%e A005195                                      {15,25,35,45}
%e A005195 (End)
%t A005195 EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1 - x^Range[m])^seq), {x, 0, m}], x]];
%t A005195 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 A005195 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 A005195 Cf. A095133 (by number of trees), A136605 (by number of edges).
%Y A005195 A diagonal of A144215.
%Y A005195 The connected case is A000055.
%Y A005195 The labeled version is A001858.
%Y A005195 The covering case is A144958, labeled A105784.
%Y A005195 For triangles instead of cycles we have A006785, covering A372169.
%Y A005195 Unique cycle: A236570 (labeled A372193), covering A372191 (labeled A372195).
%Y A005195 A006125 counts simple graphs, unlabeled A000088.
%Y A005195 A006129 counts covering graphs, unlabeled A002494.
%Y A005195 Cf. A000272, A002807, A054548, A137917, A367863, A372176.
%K A005195 nonn,easy,nice
%O A005195 0,3
%A A005195 _N. J. A. Sloane_
%E A005195 More terms from _Vladeta Jovovic_, Sep 05 2002