A305132 Number of connected graphs on n unlabeled nodes with exactly 2 cycles joined along two or more edges but not more than half each cycle and all nodes having degree at most 4.

1, 3, 11, 36, 116, 366, 1151, 3583, 11093, 34141, 104489, 318139, 963899, 2907276, 8731919, 26125538, 77889504, 231466147, 685811867, 2026481941, 5973064855, 17565416721, 51547293439, 150977445294, 441409701444, 1288409915625, 3754926609800, 10927779696264

Offset: 5

Author

Andrew Howroyd, May 26 2018

Keywords

• nonn

Comments

The resulting graph will actually have three cycles. See A121331 for the special case of all three cycles having the same length.

Equivalently, the number of connected simple graphs with n unlabeled nodes and n + 1 edges and all nodes having degree at most 4 (A112410) less those graphs described by A125669, A125670 and A125671.

Examples

			Illustration of graphs for n=5 and n=6:
    o          o--o       o           o--o
   /|\        /|\        /|\         /|  |
  o o o      o o o      o o o--o    o o  |
   \|/        \|/        \|/         \|  |
    o          o          o           o--o
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 5..200

Crossrefs

Cf. A112410, A121331, A125669, A125670, A125671, A125672, A125673.

Programs

PARI

\\ here G is A000598 as series
G(n)={my(g=O(x)); for(n=1, n, g = 1 + x*(g^3/6 + subst(g, x, x^2)*g/2 + subst(g, x, x^3)/3) + O(x^n)); g}
C1(n)={subst(Pol(x^3*d1^3/(1-x*d1)^3 + 3*x^3*d1*d2/((1-x*d1)*(1-x^2*d2)) + 2*x^3*d3/(1-x^3*d3) + O(x*x^n)), x, 1)/12}
C2(n)={subst(Pol(((x*d1+x^2*d2)/(1-x^2*d2))^3 + 3*(x*d1+x^2*d2)*x^2*d2/(1-x^2*d2)^2 + 2*(x^3*d3 + x^6*d6)/(1-x^6*d6) + O(x*x^n)), x, 1)/12}
seq(n)={my(s=G(n)); my(d=x*(s^2+subst(s, x, x^2))/2); my(g(p,e)=subst(p + O(x*x^(n\e)), x, x^e)); Vec(O(x^n/x) + g(s,1)^2*substvec(C1(n-2),[d1,d2,d3],[g(d,1), g(d,2), g(d,3)]) + g(s,2)*substvec(C2(n-2), [d1,d2,d3,d6], [g(d,1), g(d,2), g(d,3), g(d,6)]))}

Formula

a(n) >= A125672(n) + A125673(n).