A361242 Number of nonequivalent noncrossing cacti with n nodes up to rotation.

1, 1, 1, 2, 7, 26, 144, 800, 4995, 32176, 215914, 1486270, 10471534, 75137664, 547756650, 4047212142, 30255934851, 228513227318, 1741572167716, 13380306774014, 103542814440878, 806476983310180, 6318519422577854, 49769050291536486, 393933908000862866

Offset: 0

Author

Andrew Howroyd, Mar 07 2023

Keywords

• nonn

Comments

A noncrossing cactus is a connected noncrossing graph (A007297) that is a cactus graph (a tree of edges and polygons).

Since every cactus is an outerplanar graph, every cactus has at least one drawing as a noncrossing graph.

Examples

			The a(3) = 2 nonequivalent cacti have the following blocks:
   {{1,2}, {1,3}},
   {{1,2,3}}.
Graphically these can be represented:
        1           1
      /  \        /  \
     2    3      2----3
.
The a(4) = 7 nonequivalent cacti have the following blocks:
  {{1,2}, {1,3}, {1,4}},
  {{1,2}, {1,3}, {3,4}},
  {{1,2}, {1,4}, {2,3}},
  {{1,2}, {2,4}, {3,4}},
  {{1,2}, {1,3,4}},
  {{1,2}, {2,3,4}},
  {{1,2,3,4}}.
Graphically these can be represented:
   1---4    1   4    1---4    1   4
   | \      | \ |    |        | / |
   2   3    2   3    2---3    2   3
.
   1---4    1   4    1---4
   | \ |    | / |    |   |
   2   3    2---3    2---3
		

Links

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

Crossrefs

Cf. A003168, A007297, A361236, A361243.

Programs

PARI

\\ Here F(n) is the g.f. of A003168.
F(n) = {1 + serreverse(x/((1+2*x)*(1+x)^2) + O(x*x^n))}
seq(n) = {my(f=F(n-1)); Vec(1 + intformal(f) - sum(d=2, n, eulerphi(d) * log(1-subst(x*f^2 + O(x^(n\d+1)),x,x^d)) / d), -n-1)}