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

1, 3, 0, 3, 9, 12, 19, 27, 36, 46, 57, 69, 82, 96, 111, 127, 144, 162, 181, 201, 222, 244, 267, 291, 316, 342, 369, 397, 426, 456, 487, 519, 552, 586, 621, 657, 694, 732, 771, 811, 852, 894, 937, 981, 1026, 1072, 1119, 1167, 1216, 1266, 1317, 1369, 1422

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 (3,-3,1).

Crossrefs

Cf. A003514, A060516, A060534-A060537.

Programs

Mathematica

i=5;s=1;lst={s};Do[s+=n+i;If[s>=0, AppendTo[lst, s]], {n, 0, 6!, 1}];lst (* Vladimir Joseph Stephan Orlovsky, Oct 30 2008 *)

PARI

Vec((3*x^7-7*x^6+6*x^5+3*x^4-11*x^3+6*x^2-1)/(x-1)^3 + O(x^60)) \\ Colin Barker, Nov 10 2016

Formula

G.f.: (3*x^7 - 7*x^6 + 6*x^5 + 3*x^4 - 11*x^3 + 6*x^2 - 1)/(x - 1)^3.

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) = (1 + n)*(2 + n)/2 - 9 for n>4.

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n>7. (End)

Sum_{n>=3} 1/a(n) = 1/72 + 2*tan(sqrt(73)*Pi/2)*Pi/sqrt(73). - Amiram Eldar, Jan 08 2023