A202081 The number of simple labeled graphs on n nodes whose connected components are cycles, stars, wheels, or paths.

1, 1, 2, 8, 46, 298, 2206, 19009, 187076, 2053349, 24800484, 327067043, 4677505768, 72075818159, 1189985755128, 20952274850927, 391829421176768, 7755079821666945, 161926610838369418, 3556807008080385549, 81979632030102053376, 1978135038931568355707

Offset: 0

Author

Geoffrey Critzer, Dec 10 2011

Keywords

• nonn

Comments

Here a cycle is of length 3 or more, a star has at least 4 (total) vertices, a wheel has at least 4 (total) vertices, and a path can be an isolated vertex.

References

• R. P. Stanley, Enumerative Combinatorics Volume 2, Cambridge 1999, problem 5.15

Links

• G. C. Greubel, Table of n, a(n) for n = 0..440

Crossrefs

Cf. A001205, A053530, A053531, A011800.

Programs

Mathematica

nn = 16; a = x/(2 (1 - x)) + x/2; b = x^4/4! + Sum[(n (n - 2)!/2) x^n/n!, {n, 5, nn}]; c = x Exp[x] - x^3/2 - x^2 - x; d = -x/2 - x^2/4; Range[0, nn]! CoefficientList[Series[Exp[a]*Exp[b]*Exp[c]*Exp[d]/(1 - x)^(1/2), {x, 0, nn}], x]

Formula

E.g.f.: exp(x/2+x/(2*(1-x))) * exp(-x^2/2-x^3/4-x^4/8)/(1-x)^(x/2) * exp(-x-x^2-x^3/2 + x*exp(x)) * exp(-x/2-x^2/4)/(1-x)^(1/2). [corrected by Jason Yuen, Feb 17 2025]