A361239 -id:A361239 - cp's OEIS frontend

A369929 Array read by antidiagonals: T(n,k) is the number of achiral noncrossing partitions composed of n blocks of size k.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 3, 3, 6, 1, 1, 1, 1, 3, 5, 7, 10, 1, 1, 1, 1, 4, 5, 16, 12, 20, 1, 1, 1, 1, 4, 7, 18, 31, 30, 35, 1, 1, 1, 1, 5, 7, 31, 35, 102, 55, 70, 1, 1, 1, 1, 5, 9, 34, 64, 136, 213, 143, 126, 1

Offset: 0

Andrew Howroyd, Feb 07 2024

T(n,2*k-1) is the number of achiral noncrossing k-gonal cacti with n polygons.

			Array begins:
===============================================
n\k| 1  2   3   4    5    6    7    8     9 ...
---+-------------------------------------------
0  | 1  1   1   1    1    1    1    1     1 ...
1  | 1  1   1   1    1    1    1    1     1 ...
2  | 1  1   1   1    1    1    1    1     1 ...
3  | 1  2   2   3    3    4    4    5     5 ...
4  | 1  3   3   5    5    7    7    9     9 ...
5  | 1  6   7  16   18   31   34   51    55 ...
6  | 1 10  12  31   35   64   70  109   117 ...
7  | 1 20  30 102  136  296  368  651   775 ...
8  | 1 35  55 213  285  663  819 1513  1785 ...
9  | 1 70 143 712 1155 3142 4495 9304 12350 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
Michel Bousquet and Cédric Lamathe, On symmetric structures of order two, Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176. See Table 1.
Wikipedia, Fuss-Catalan number.
Wikipedia, Noncrossing partition.

Columns are: A000012, A001405(n-1), A047749 (k=3), A369930 (k=4), A143546 (k=5), A143547 (k=7), A143554 (k=9), A192893 (k=11).

Cf. A070914, A303694, A303929, A361236, A361239, A370060, A370062.

\\ u(n,k,r) are Fuss-Catalan numbers.
u(n,k,r) = {r*binomial(k*n + r, n)/(k*n + r)}
e(n,k) = {sum(j=0, n\2, u(j, k, 1+(n-2*j)*k/2))}
T(n, k)={if(n==0, 1, if(k%2, if(n%2, 2*u(n\2, k, (k+1)/2), u(n/2, k, 1) + u(n/2-1, k, k)), e(n, k) + if(n%2, u(n\2, k, k/2)))/2)}

T(n,k) = 2*A303929(n,k) - A303694(n,k).

T(n,2*k-1) = 2*A361239(n,k) - A361236(n,k).

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

Original entry on oeis.org

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.

A361240 Number of nonequivalent noncrossing triangular cacti with n triangles up to rotation and reflection.

Original entry on oeis.org

1, 1, 1, 4, 19, 124, 931, 7801, 68685, 630850, 5966610, 57808920, 571178751, 5737672339, 58455577800, 602859484608, 6283968796705, 66119472527814, 701526880303315, 7498841163925819, 80696081185766970, 873654670250482120, 9510760874015305314, 104056578392127906720

Offset: 0

Andrew Howroyd, Mar 06 2023

nonn

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

Column 3 of A361239.

Cf. A002294, A118970, A361237.

a(2*n) = (A361237(2*n) + A002294(n))/2; a(2*n+1) = (A361237(2*n+1) + A118970(n))/2.

A361241 Number of nonequivalent noncrossing 4-gonal cacti with n polygons up to rotation and reflection.

Original entry on oeis.org

1, 1, 1, 6, 35, 349, 3766, 45632, 580203, 7687128, 104898024, 1466605630, 20916933674, 303368072539, 4463328542008, 66484512715040, 1001084180891355, 15217675702394661, 233285495922344929, 3603276856175739600, 56033315904277236728, 876698296980033411125

Offset: 0

Andrew Howroyd, Mar 06 2023

nonn

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

Column 4 of A361239.

Cf. A361238.

a(2*n) = (A361238(2*n) + binomial(7*n + 1, n)/(7*n + 1))/2; a(2*n+1) = (A361238(2*n+1) + 4*binomial(7*n + 4, n)/(7*n + 4))/2.

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

Original entry on oeis.org

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

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).

			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

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

Cf. A003168, A007297, A361239, A361242.

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

cp's OEIS Frontend

A369929 Array read by antidiagonals: T(n,k) is the number of achiral noncrossing partitions composed of n blocks of size k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

A361240 Number of nonequivalent noncrossing triangular cacti with n triangles up to rotation and reflection.

Views

Author

Keywords

Links

Crossrefs

Formula

A361241 Number of nonequivalent noncrossing 4-gonal cacti with n polygons up to rotation and reflection.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI