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

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

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..3 are A000007, A000012(n+3), A004526(n+4), A003453(n+4).

Row sums are A380805.

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

Programs

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]))}

Formula

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