A381467 -id:A381467 - cp's OEIS frontend

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

Andrew Howroyd, Feb 24 2025

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

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

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

Columns 0..2 are A000007, A000012(n+3), A008619(n+6).
Row sums are A380632.
Cf. A380633, A380634, A381467.

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

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

A380634 Number of unlabeled 2,3 cacti (triangular cacti with bridges) with n triangles and every node contained in exactly one triangle.

Original entry on oeis.org

1, 1, 1, 2, 6, 18, 66, 265, 1140, 5186, 24588, 120062, 600884, 3066490, 15907266, 83665520, 445317808, 2394928214, 12997988041, 71116953074, 391931826699, 2174062325068, 12130745830640, 68049392678632, 383601371168527, 2172093593344465, 12349917974708867

Offset: 0

Andrew Howroyd, Feb 24 2025

nonn

The number of vertices is 3*n and for n > 0, the number of bridges is n-1.

			The a(3) = 2 cactus graphs are:
    o       o       o        o   o---o   o
   / \     / \     / \      / \   \ /   / \
  o---o---o---o---o---o    o---o---o---o---o

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

Cf. A091487, A287891, A380631, A381467.

\\ here R(n) gives A287891 as g.f.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
raise(p,d) = {my(n=serprec(p,x)-1); subst(p + O(x^(n\d+1)), x, x^d)}
R(n)={my(p=1+O(x)); for(n=1, n, p = 1 + x*Ser(EulerT(Vec(p*(p^2 + raise(p,2))/2)))); p}
seq(n)={ my(p=R(n-1), g=p*(p^2 + raise(p,2))/2); Vec(1 + x*(x*(raise(g,2) - g^2) + p*raise(p,2) + (p^3 + 2*raise(p,3))/3)/2) }

a(n) = A380631(3*n,n) = A381467(3*n,n).

A381468 Number of simple connected graphs on n unlabeled nodes with no node a member of more than one cycle.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 20, 48, 133, 374, 1124, 3439, 10923, 35245, 116128, 387729, 1312038, 4485906, 15486546, 53900520, 188998450, 667062919, 2368440477, 8454560144, 30328595227, 109285433191, 395425965732, 1436219868659, 5234881134074, 19143123415166, 70216752517419

Offset: 0

Andrew Howroyd, Feb 24 2025

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..1000
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.

Row sums of A381467.

Cf. A000083, A317722 (with 2-cycles), A380632, A380805.

PARI
```
Vec(G(31,1)) \\ G() defined in A381467.
```

A381470 Number of simple connected graphs on n unlabeled nodes with exactly 2 non-overlapping cycles.

Original entry on oeis.org

1, 4, 21, 85, 345, 1289, 4713, 16622, 57535, 195212, 653318, 2158866, 7063333, 22906699, 73742762, 235863378, 750187968, 2374249283, 7481414941, 23482536967, 73449564533, 229016163367, 712044375528, 2208131225648, 6831543467752, 21089958138852, 64978894444220

Offset: 6

Andrew Howroyd, Feb 25 2025

nonn

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

			The a(6) = 1 graph is:
    o       o
   / \     / \
  o---o---o---o
.
The a(7) = 4 graphs are:
    o     o---o     o   o   o       o---o   o       o   o   o
   / \    |   |    / \ / \ / \     / \     / \     / \ /   / \
  o---o---o---o   o---o   o---o   o---o---o---o   o---o---o---o

Andrew Howroyd, Table of n, a(n) for n = 6..1000
Wikipedia, Cactus graph.
Index entries for sequences related to cacti.

Column k=2 of A381467.

Cf. A000081, A000083, A001429.

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n), t2=subst(t,x,x^2), g=t*(t^2/(1-t) + t2*(1+t)/(1-t2))/2, g2=subst(g,x,x^2)); Vec(g^2/(1-t) + g2*(1+t)/(1-t2))/2}

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A380634 Number of unlabeled 2,3 cacti (triangular cacti with bridges) with n triangles and every node contained in exactly one triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A381468 Number of simple connected graphs on n unlabeled nodes with no node a member of more than one cycle.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A381470 Number of simple connected graphs on n unlabeled nodes with exactly 2 non-overlapping cycles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI