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,4

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

Wikipedia, Cactus graph.

Index entries for sequences related to cacti.

Example

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

Prog

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

Crossrefs

Cf. A003168, A007297, A361236, A361243.

Sequence in context: A341900 A300049 A209005 * A068870 A345682 A005519

Adjacent sequences: A361239 A361240 A361241 * A361243 A361244 A361245

Keyword

nonn

Author

Andrew Howroyd, Mar 07 2023

Status

approved