A380631 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with k cycles and each node a member of exactly one cycle, 0 <= k <= floor(n/3).

1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 0, 1, 2, 2, 0, 1, 3, 5, 0, 1, 3, 10, 0, 1, 4, 17, 6, 0, 1, 4, 26, 18, 0, 1, 5, 38, 51, 0, 1, 5, 52, 106, 18, 0, 1, 6, 70, 205, 87, 0, 1, 6, 90, 350, 286, 0, 1, 7, 115, 579, 741, 66, 0, 1, 7, 142, 887, 1660, 406

Offset: 0

Author

Andrew Howroyd, Feb 24 2025

Keywords

• nonn
• tabf

Comments

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

Examples

			Triangle begins:
  1;
  0;
  0;
  0, 1;
  0, 1;
  0, 1;
  0, 1, 1;
  0, 1, 1;
  0, 1, 2;
  0, 1, 2,  2;
  0, 1, 3,  5;
  0, 1, 3, 10;
  0, 1, 4, 17,   6;
  0, 1, 4, 26,  18;
  0, 1, 5, 38,  51;
  0, 1, 5, 52, 106, 18;
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1750 (rows 0..100)
• Wikipedia, Cactus graph.
• Index entries for sequences related to cacti.

Crossrefs

Columns 0..2 are A000007, A000012(n+3), A008619(n+6).

Row sums are A380632.

Cf. A380633, A380634, A381467.

Programs

PARI

EulerMTS(p)={my(n=serprec(p,x)-1,vars=variables(p)); exp(sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i))}
raise(p,d) = {my(n=serprec(p,x)-1); substvec(p + O(x^(n\d+1)), [x,y], [x^d,y^d])}
R(n,y)={my(g = O(x^3)); for(n=1, (n-1)\2, my(p=x*EulerMTS(g), p2=raise(p,2)); g=p*y*(p^2/(1 - p) + (1 + p)*p2/(1 - p2))/2); g}
G(n,y=1)={my(g=R(n,y), p = x*EulerMTS(g) + O(x*x^n));
  my( r=((1 + p)^2/(1 - raise(p,2)) - 1)/2 );
  my( c=-sum(d=1, n, eulerphi(d)/d*log(raise(1-p,d))) );
  1 + (raise(g,2) - g^2 + y*(r + c - 2*p - p^2 - raise(p,2)))/2 }
T(n)={[Vecrev(p) | p<-Vec(G(n,y))]}
{ my(A=T(15)); for(i=1, #A, print(A[i])) }

Formula

T(3*n, n) = A380634(n).