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

%I #24 Jan 08 2023 02:41:05

%S 1,3,0,3,9,12,19,27,36,46,57,69,82,96,111,127,144,162,181,201,222,244,

%T 267,291,316,342,369,397,426,456,487,519,552,586,621,657,694,732,771,

%U 811,852,894,937,981,1026,1072,1119,1167,1216,1266,1317,1369,1422

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

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

%H Colin Barker, <a href="/A060533/b060533.txt">Table of n, a(n) for n = 0..1000</a>

%H Vladeta Jovovic, <a href="/A060533/a060533.pdf">Generating functions for homeomorphically irreducible multigraphs on n labeled nodes</a>.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).

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

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

%F From _Colin Barker_, Nov 10 2016: (Start)

%F a(n) = (1 + n)*(2 + n)/2 - 9 for n>4.

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

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

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

%o (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

%Y Cf. A003514, A060516, A060534-A060537.

%K nonn,easy

%O 0,2

%A _Vladeta Jovovic_, Apr 01 2001