login
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.
3
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,2
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.
LINKS
FORMULA
a(n) >= A125672(n) + A125673(n).
EXAMPLE
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
PROG
(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)]))}
KEYWORD
nonn
AUTHOR
Andrew Howroyd, May 26 2018
STATUS
approved