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,6

Comments

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

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.

Formula

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

Example

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;
  ...

Prog

(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))) );
  print(g-p);
  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]))}

Crossrefs

Row sums are A381468.

Columns k=0..1 are A000055, A001429.

Cf. A380631, A380634.

Sequence in context: A283189 A032157 A153926 * A035425 A139074 A179418

Adjacent sequences: A381449 A381450 A381461 * A381468 A381469 A381477

Keyword

nonn,tabf,new

Author

Andrew Howroyd, Feb 24 2025

Status

approved