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

1, 6, 3, 10, 48, 84, 182, 372, 699, 1222, 2007, 3132, 4688, 6780, 9528, 13068, 17553, 23154, 30061, 38484, 48654, 60824, 75270, 92292, 112215, 135390, 162195, 193036, 228348, 268596, 314276, 365916, 424077, 489354, 562377, 643812, 734362, 834768, 945810

Offset

0,2

References

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

Links

Colin Barker, Table of n, a(n) for n = 0..1000

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

Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Formula

G.f.: - (4*x^12 - 12*x^11 + 6*x^10 + 50*x^9 - 180*x^8 + 282*x^7 - 208*x^6 + 30*x^5 + 72*x^4 - 62*x^3 + 18*x^2 - 1)/((x - 1)^6).

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

From Colin Barker, Nov 10 2016: (Start)

a(n) = 60 + 48*(1+n) - 12*(1+n)*(2+n) + (1+n)*(2+n)*(3+n)*(4+n)*(5+n)/120 for n>6.

a(n) = 6*a(n-1)- 15*a(n-2) + 20*a(n-3) - 15*a(n-4) + 6*a(n-5) - a(n-6) for n>12.

(End)

Prog

(PARI) Vec(-(4*x^12-12*x^11+6*x^10+50*x^9-180*x^8+282*x^7-208*x^6+30*x^5+72*x^4-62*x^3+18*x^2-1)/((x-1)^6) + O(x^40)) \\ Colin Barker, Nov 10 2016

Crossrefs

Cf. A003514, A060516, A060533, A060535-A060537.

Sequence in context: A336319 A272549 A112456 * A060445 A131894 A368679

Adjacent sequences: A060531 A060532 A060533 * A060535 A060536 A060537

Keyword

nonn,easy

Author

Vladeta Jovovic, Apr 01 2001

Status

approved