|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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)]))}
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|