A380634 -id:A380634 - 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).

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

Original entry on oeis.org

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

Andrew Howroyd, Feb 24 2025

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

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

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.

Row sums are A381468.
Columns k=0..2 are A000055, A001429, A381470.
Cf. A380631, A380634.

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

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

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

Original entry on oeis.org

0, 1, 1, 4, 15, 66, 304, 1503, 7622, 39856, 212447, 1151614, 6324924, 35127396, 196917025, 1112776860, 6332114208, 36252066562, 208665030299, 1206819559836, 7009605269315, 40871341270810, 239144296550695, 1403719120877546, 8263431521645830, 48774908707685849

Offset: 0

Andrew Howroyd, Feb 25 2025

nonn

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

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

Cf. A287891, A380634 (unrooted).

\\ 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)); Vec(x*(p^3 + 3*p*raise(p,2) + 2*raise(p,3))/6 + O(x*x^n), -n-1) }

G.f.: x*(B(x)^3 + 3*B(x)*B(x^2) + 2*B(x^3))/6 where B(x) is the g.f. of A287891.

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula