A361236 -id:A361236 - 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).

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

Original entry on oeis.org

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.

A361237 Number of nonequivalent noncrossing triangular cacti with n triangles up to rotation.

Original entry on oeis.org

1, 1, 1, 5, 33, 230, 1827, 15466, 137085, 1260545, 11930690, 115607310, 1142333751, 11475243990, 116910923720, 1205717972880, 12567935262965, 132238934938755, 1403053736656275, 14997682223032473, 161392162120990570, 1747309339397241620, 19021521745371642498

Offset: 0

Andrew Howroyd, Mar 05 2023

nonn

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

Column 3 of A361236.

Cf. A361240.

A361238 Number of nonequivalent noncrossing 4-gonal cacti with n polygons up to rotation.

Original entry on oeis.org

1, 1, 1, 8, 63, 664, 7462, 90896, 1159587, 15369761, 209785576, 2933152208, 41833725570, 606735330572, 8926655086328, 132969013796640, 2002168332793035, 30435351234214599, 466570991414368225, 7206553709798780480, 112066631802051120600, 1753396593921234013664

Offset: 0

Andrew Howroyd, Mar 05 2023

nonn

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

Column 4 of A361236.

Cf. A361241.

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A361237 Number of nonequivalent noncrossing triangular cacti with n triangles up to rotation.

Views

Author

Keywords

Links

Crossrefs

A361238 Number of nonequivalent noncrossing 4-gonal cacti with n polygons up to rotation.

Views

Author

Keywords

Links

Crossrefs