A381470 Number of simple connected graphs on n unlabeled nodes with exactly 2 non-overlapping cycles.

1, 4, 21, 85, 345, 1289, 4713, 16622, 57535, 195212, 653318, 2158866, 7063333, 22906699, 73742762, 235863378, 750187968, 2374249283, 7481414941, 23482536967, 73449564533, 229016163367, 712044375528, 2208131225648, 6831543467752, 21089958138852, 64978894444220

Offset: 6

Author

Andrew Howroyd, Feb 25 2025

Keywords

• nonn

Comments

All such graphs are cactus graphs (with bridges allowed).

Examples

			The a(6) = 1 graph is:
    o       o
   / \     / \
  o---o---o---o
.
The a(7) = 4 graphs are:
    o     o---o     o   o   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 = 6..1000
• Wikipedia, Cactus graph.
• Index entries for sequences related to cacti.

Crossrefs

Column k=2 of A381467.

Cf. A000081, A000083, A001429.

Programs

PARI

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n), t2=subst(t,x,x^2), g=t*(t^2/(1-t) + t2*(1+t)/(1-t2))/2, g2=subst(g,x,x^2)); Vec(g^2/(1-t) + g2*(1+t)/(1-t2))/2}