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

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

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. A000055, A095133 (by number of trees), A136605 (by number of edges), A144958 (first differences).

A diagonal of A144215.

Sequence in context: A003214 A331693 A123423 * A228835 A052843 A120707

Adjacent sequences: A005192 A005193 A005194 * A005196 A005197 A005198

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Sep 05 2002

Status

approved