A361243 -id:A361243 - cp's OEIS frontend

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

Andrew Howroyd, Mar 07 2023

nonn

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.

			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

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

Cf. A003168, A007297, A361236, A361243.

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

A361239 Array read by antidiagonals: T(n,k) is the number of noncrossing k-gonal cacti with n polygons up to rotation and reflection.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 4, 7, 1, 1, 1, 1, 6, 19, 28, 1, 1, 1, 1, 7, 35, 124, 108, 1, 1, 1, 1, 9, 57, 349, 931, 507, 1, 1, 1, 1, 10, 85, 737, 3766, 7801, 2431, 1, 1, 1, 1, 12, 117, 1359, 10601, 45632, 68685, 12441, 1

Offset: 0

Andrew Howroyd, Mar 06 2023

			Array begins:
===================================================
n\k | 1     2      3       4        5         6 ...
----+----------------------------------------------
  0 | 1     1      1       1        1         1 ...
  1 | 1     1      1       1        1         1 ...
  2 | 1     1      1       1        1         1 ...
  3 | 1     3      4       6        7         9 ...
  4 | 1     7     19      35       57        85 ...
  5 | 1    28    124     349      737      1359 ...
  6 | 1   108    931    3766    10601     24112 ...
  7 | 1   507   7801   45632   167741    471253 ...
  8 | 1  2431  68685  580203  2790873   9678999 ...
  9 | 1 12441 630850 7687128 48300850 206780448 ...
  ...

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

Columns 1..4 are A000012, A296533, A361240, A361241.
Row n=3 is A032766.
Cf. A361236, A361243.

\\ R(n,k) gives A361236.
u(n,k,r) = {r*binomial(n*(2*k-1) + r, n)/(n*(2*k-1) + r)}
R(n,k) = {if(n==0, 1, u(n, k, 1)/((k-1)*n+1) + sumdiv(gcd(k,n-1), d, if(d>1, eulerphi(d)*u((n-1)/d, k, 2*k/d)/k)))}
T(n, k) = {(R(n, k) + u(n\2, k, if(n%2, k, 1)))/2}

T(0,k) = T(1,k) = T(2,k) = 1.
T(2*n,k) = (A361236(2*n,k) + binomial((2*k-1)*n + 1, n)/((2*k-1)*n + 1))/2.
T(2*n+1,k) = (A361236(2*n+1,k) + k*binomial((2*k-1)*n + k, n)/((2*k-1)*n + k))/2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI