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

1, 1, 1, 1, 1, 2, 2, 3, 5, 6, 13, 1, 11, 33, 4, 23, 89, 21, 47, 240, 85, 2, 106, 657, 345, 16, 235, 1806, 1289, 109, 551, 5026, 4713, 627, 6, 1301, 13999, 16622, 3259, 64, 3159, 39260, 57535, 15576, 598, 7741, 110381, 195212, 69983, 4394, 18, 19320, 311465, 653318, 299354, 28286, 295

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;
     1;
     1;
     1,     1;
     2,     2;
     3,     5;
     6,    13,     1;
    11,    33,     4;
    23,    89,    21;
    47,   240,    85,     2;
   106,   657,   345,    16;
   235,  1806,  1289,   109;
   551,  5026,  4713,   627,   6;
  1301, 13999, 16622,  3259,  64;
  3159, 39260, 57535, 15576, 598;
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1750 (rows 0..100)
• R. J. Mathar, Counting connected graphs without overlapping cycles, arXiv:1808.06264 [math.CO] (2018).
• Wikipedia, Cactus graph.
• Index entries for sequences related to cacti.

Crossrefs

Row sums are A381468.

Columns k=0..2 are A000055, A001429, A381470.

Cf. A380631, A380634.

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=x+O(x^2)); for(n=2, n, my(p=x*EulerMTS(g), p2=raise(p,2)); g=p + 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 + p + (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).