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,2

References

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

Links

Table of n, a(n) for n=0..28.

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

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!.

Crossrefs

Cf. A003514, A060516, A060533-A060537.

Sequence in context: A182427 A171956 A271743 * A239595 A037379 A055049

Adjacent sequences: A060532 A060533 A060534 * A060536 A060537 A060538

Keyword

easy,nonn

Author

Vladeta Jovovic, Apr 01 2001

Status

approved