A296532 -id:A296532 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 5, 11, 1, 1, 1, 1, 8, 33, 49, 1, 1, 1, 1, 9, 63, 230, 204, 1, 1, 1, 1, 12, 105, 664, 1827, 984, 1, 1, 1, 1, 13, 159, 1419, 7462, 15466, 4807, 1, 1, 1, 1, 16, 221, 2637, 21085, 90896, 137085, 24739, 1

Offset: 0

Andrew Howroyd, Mar 05 2023

The number of noncrossing k-gonal cacti is given by column 2*(k-1) of A070914. This sequence enumerates these cacti with rotations being considered equivalent.
Equivalently, T(n,k) is the number of connected acyclic k-uniform noncrossing antichains with n blocks covering (k-1)*n+1 nodes where the intersection of two blocks is at most 1 node modulo cyclic rotation of the nodes.
Noncrossing trees correspond to the case of k = 2.

			=====================================================
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     4       5        8        9        12 ...
  4 | 1    11      33       63      105       159 ...
  5 | 1    49     230      664     1419      2637 ...
  6 | 1   204    1827     7462    21085     48048 ...
  7 | 1   984   15466    90896   334707    941100 ...
  8 | 1  4807  137085  1159587  5579961  19354687 ...
  9 | 1 24739 1260545 15369761 96589350 413533260 ...
  ...

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 k=1..4 are A000012, A296532, A361237, A361238.
Row n=3 is A042948.
Cf. A070914, A303694, A303912, A361239, A361242.

\\ here u is Fuss-Catalan sequence with p = 2*k-1.
u(n,k,r) = {r*binomial(n*(2*k-1) + r, n)/(n*(2*k-1) + r)}
T(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(0,k) = T(1,k) = T(2,k) = 1.

A296533 Number of nonequivalent noncrossing trees with n edges up to rotation and reflection.

Original entry on oeis.org

1, 1, 1, 3, 7, 28, 108, 507, 2431, 12441, 65169, 351156, 1926372, 10746856, 60762760, 347664603, 2009690895, 11723160835, 68937782355, 408323575275, 2434289046255, 14598013278960, 88011196469040, 533216762488020, 3245004785069892, 19829769013792908

Offset: 0

Andrew Howroyd, Dec 14 2017

nonn

The number of all noncrossing trees with n edges is given by A001764.

The number of nodes will be n + 1.

			Case n=3:
   o---o   o---o   o---o
   |       | \       \
   o---o   o   o   o---o
In total there are 3 distinct noncrossing trees up to rotation and reflection.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Bernold Fiedler, Real-time blow-up and connection graphs of rational vector fields on the Riemann sphere, arXiv:2504.20503 [math.DS], 2025. See p. 24.
Marc Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

Cf. A001764, A005034, A006013, A296532 (up to rotation only).

a[n_] := (If[OddQ[n], 3*Binomial[(1/2)*(3*n - 1), (n - 1)/2], Binomial[3*n/2, n/2]] + Binomial[3*n, n]/(2*n + 1))/(2*(n + 1));
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 27 2017, after Andrew Howroyd *)

a(n)={(binomial(3*n, n)/(2*n+1) + if(n%2, 3*binomial((3*n-1)/2, (n-1)/2),  binomial(3*n/2, n/2)))/(2*(n+1))}

a(2n) = (A296532(2n) + A001764(n))/2, a(2n-1) = (A296532(2n-1) + A006013(n-1))/2.

a(2n) = A005034(2n).

A361359 Number of nonequivalent noncrossing caterpillars with n edges up to rotation.

Original entry on oeis.org

1, 1, 1, 4, 11, 49, 196, 868, 3721, 16306, 70891, 309739, 1350831, 5897934, 25740386, 112368153, 490489041, 2141121271, 9346382981, 40799215354, 178097506051, 777437032059, 3393689486976, 14814237183658, 64667544141561, 282288713218896, 1232255125682671

Offset: 0

Andrew Howroyd, Mar 09 2023

The number of all noncrossing caterpillars with n edges is given by A361356.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (6,-3,-26,36,-2,-18,6,5,-4,1).

Cf. A296532 (noncrossing trees), A361356, A361358, A361360 (up to rotation and reflection).

G(x)={ my(f = x*(2 - x)/(1 - 5*x + 3*x^2 - x^3), g = 1 + x + x^2*(3 - 2*x + (4 - 3*x + x^2)*f + (1 + 2*x)*f^2)/(1 - x)^2); (intformal(g) - 3)/x + x*subst((1 + 2*x*f)/(1-x)^2, x, x^2)/2 }
{ Vec(G(x) + O(x^30)) }

G.f.: (1 - 5*x - 2*x^2 + 27*x^3 - 20*x^4 - 13*x^5 + 23*x^6 - 5*x^7 - 6*x^8 + 3*x^9)/((1 - x)*(1 - 5*x + 3*x^2 - x^3)*(1 - 5*x^2 + 3*x^4 - x^6)).

a(n) = 6*a(n-1) - 3*a(n-2) - 26*a(n-3) + 36*a(n-4) - 2*a(n-5) - 18*a(n-6) + 6*a(n-7) + 5*a(n-8) - 4*a(n-9) + a(n-10) for n >= 10.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A296533 Number of nonequivalent noncrossing trees with n edges up to rotation and reflection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A361359 Number of nonequivalent noncrossing caterpillars with n edges up to rotation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula