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

Author

Vladeta Jovovic, Apr 01 2001

Keywords

• nonn
• easy

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

Crossrefs

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

Programs

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

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)