A361243 Number of nonequivalent noncrossing cacti with n nodes up to rotation and reflection.

1, 1, 1, 2, 5, 17, 79, 421, 2537, 16214, 108204, 743953, 5237414, 37574426, 273889801, 2023645764, 15128049989, 114256903169, 870786692493, 6690155544157, 51771411793812, 403238508004050, 3159259746188665, 24884525271410389, 196966954270163612

Offset

0,4

Comments

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

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(4) = 5 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}, {1,3,4}},
  {{1,2,3,4}}.
Graphically these can be represented:
   1---4    1   4    1---4    1---4    1---4
   | \      | \ |    |        | \ |    |   |
   2   3    2   3    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/(1 - x*subst(f + O(x^(n\2+1)), x, x^2)) + 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)/2}

Crossrefs

Cf. A003168, A007297, A361239, A361242.

Sequence in context: A020096 A362109 A187245 * A302194 A289739 A243337

Adjacent sequences: A361240 A361241 A361242 * A361244 A361245 A361246

Keyword

nonn

Author

Andrew Howroyd, Mar 07 2023

Status

approved