A380633 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes of degree at most 3 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, 1, 0, 1, 3, 3, 0, 1, 3, 6, 0, 1, 4, 11, 2, 0, 1, 4, 17, 5, 0, 1, 5, 26, 17, 0, 1, 5, 36, 37, 2, 0, 1, 6, 50, 78, 12, 0, 1, 6, 65, 140, 44, 0, 1, 7, 85, 248, 131, 4, 0, 1, 7, 106, 396, 325, 23

Offset

0,18

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)

Wikipedia, Cactus graph.

Index entries for sequences related to cacti.

Formula

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

Example

Triangle begins:
  1;
  0;
  0;
  0, 1;
  0, 1;
  0, 1;
  0, 1, 1;
  0, 1, 1;
  0, 1, 2;
  0, 1, 2,  1;
  0, 1, 3,  3;
  0, 1, 3,  6;
  0, 1, 4, 11,  2;
  0, 1, 4, 17,  5;
  0, 1, 5, 26, 17;
  0, 1, 5, 36, 37, 2;
  ...

Prog

(PARI)
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*(1 + g), p2=raise(p, 2)); g=x*y*(p^2/(1 - p) + (1 + p)*p2/(1 - p2))/2); g}
G(n, y=1)={my(g=R(n, y), p = x*(1+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]))}

Crossrefs

Columns 0..3 are A000007, A000012(n+3), A004526(n+4), A003453(n+4).

Row sums are A380805.

Cf. A000672, A380631 (with vertices of any degree).

Sequence in context: A292047 A292049 A320341 * A054523 A161363 A293136

Adjacent sequences: A380629 A380631 A380632 * A380634 A380635 A380636

Keyword

nonn,tabf,new

Author

Andrew Howroyd, Feb 24 2025

Status

approved