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

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

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

Prog

(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

Crossrefs

Cf. A003514, A060516, A060534-A060537.

Sequence in context: A348670 A104141 A279977 * A177785 A212036 A191619

Adjacent sequences: A060530 A060531 A060532 * A060534 A060535 A060536

Keyword

nonn,easy

Author

Vladeta Jovovic, Apr 01 2001

Status

approved