login
A005195
Number of forests with n unlabeled nodes.
(Formerly M0776)
59
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.
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: A236570 (labeled A372193), covering A372191 (labeled A372195).
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Sequence in context: A003214 A331693 A123423 * A228835 A052843 A120707
KEYWORD
nonn,easy,nice
EXTENSIONS
More terms from Vladeta Jovovic, Sep 05 2002
STATUS
approved