A060535 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 5 labeled nodes.

1, 10, 15, 30, 165, 430, 1170, 3180, 7935, 18610, 40948, 84570, 164740, 304690, 538630, 915574, 1504135, 2398460, 3725495, 5653790, 8404075, 12261860, 17592335, 24857870, 34638440, 47655326, 64798470, 87157890, 116059590

Offset: 0

Author

Vladeta Jovovic, Apr 01 2001

Keywords

• easy
• nonn

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Links

• Vladeta Jovovic, Generating functions for homeomorphically irreducible multigraphs on n labeled nodes

Crossrefs

Cf. A003514, A060516, A060533-A060537.

Formula

G.f.: (5*x^18 - 20*x^17 + 30*x^16 + 58*x^15 - 745*x^14 + 2790*x^13 - 5270*x^12 + 5010*x^11 - 711*x^10 - 4380*x^9 + 6270*x^8 - 4470*x^7 + 1535*x^6 + 178*x^5 - 450*x^4 + 210*x^3 - 40*x^2 + 1)/(x - 1)^10. E.g.f. for homeomorphically irreducible multigraphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp(x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.