A005195 Number of forests with n unlabeled nodes. (Formerly M0776)

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, 8599, 20514, 49905, 122963, 307199, 775529, 1977878, 5086638, 13184156, 34402932, 90328674, 238474986, 632775648, 1686705630, 4514955632, 12132227370, 32717113805, 88519867048, 240235675303

Offset

0,3

Comments

Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015

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

References

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.

N. J. A. Sloane, Transforms

Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Eric Weisstein's World of Mathematics, Forest.

Index entries for sequences related to forests

Formula

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

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.

a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 1.023158422... . - Vaclav Kotesovec, Nov 16 2014

First differences are A144958. - Gus Wiseman, Apr 29 2024

Example

From Gus Wiseman, Apr 29 2024: (Start)
Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 10 forests:
  {}  {}  {}    {}       {}          {}
          {12}  {12}     {12}        {12}
                {13,23}  {12,34}     {12,34}
                         {13,23}     {13,23}
                         {13,24,34}  {12,35,45}
                         {14,24,34}  {13,24,34}
                                     {14,24,34}
                                     {13,24,35,45}
                                     {14,25,35,45}
                                     {15,25,35,45}
(End)

Mathematica

EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1 - x^Range[m])^seq), {x, 0, m}], x]];
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)];
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 *)

Crossrefs

Cf. A095133 (by number of trees), A136605 (by number of edges).

A diagonal of A144215.

The connected case is A000055.

The labeled version is A001858.

The covering case is A144958, labeled A105784.

For triangles instead of cycles we have A006785, covering A372169.

Unique cycle: A372192 (labeled A372193), covering A372191 (labeled A372195).

A006125 counts simple graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

Cf. A000272, A002807, A054548, A137917, A367863, A372176.

Sequence in context: A003214 A331693 A123423 * A228835 A052843 A120707

Adjacent sequences: A005192 A005193 A005194 * A005196 A005197 A005198

Keyword

nonn,easy,nice,changed

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Sep 05 2002

Status

approved