A303912 -id:A303912 - cp's OEIS frontend

A054357 Number of unlabeled 2-ary cacti having n polygons. Also number of bicolored plane trees with n edges.

1, 1, 2, 3, 6, 10, 28, 63, 190, 546, 1708, 5346, 17428, 57148, 191280, 646363, 2210670, 7626166, 26538292, 93013854, 328215300, 1165060668, 4158330416, 14915635378, 53746119972, 194477856100, 706437056648, 2575316704200, 9419571138368

Offset: 0

Simon Plouffe

nonn

a(n) = the number of inequivalent non-crossing partitions of n points (equally spaced) on a circle, under rotations of the circle. This may be considered the number of non-crossing partitions of n unlabeled points on a circle, so this sequence has the same relation to the Catalan numbers (A000108) as the number of partitions of an integer (A000041) has to the Bell numbers (A000110). - Len Smiley, Sep 06 2005

Indranil Ghosh, Table of n, a(n) for n = 0..1000
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Tilman Piesk, Partition related number triangles
Index entries for sequences related to cacti

Column k=2 of A303912.
Row sums of A209805.
Cf. A002995, A054358, A111275.

a[n_] := If[n == 0, 1, (Binomial[2*n, n]/(n + 1) + DivisorSum[n, Binomial[2*#, #]*EulerPhi[n/#]*Boole[# < n] & ])/n]; Table[a[n], {n, 0, 28}] (* Jean-François Alcover, Jul 17 2017 *)

a(n)=if(n==0, 1, (binomial(2*n, n)/(n + 1) + sumdiv(n, d, binomial(2*d, d)*eulerphi(n/d)*(dIndranil Ghosh, Jul 17 2017

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/n - binomial(2*n, n)/(n+1)) \\ Andrew Howroyd, May 02 2018

from sympy import binomial, divisors, totient
def a(n): return 1 if n==0 else (binomial(2*n, n)//(n + 1) + sum(binomial(2*d, d)*totient(n//d)*(dIndranil Ghosh, Jul 17 2017

a(n) = (1/n)*(Sum_{d|n} phi(n/d)*binomial(2*d, d)) - binomial(2*n, n)/(n+1) for n > 0. - Andrew Howroyd, May 02 2018

a(n) ~ 2^(2*n) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Jul 17 2017

More terms from Len Smiley, Sep 06 2005

More terms from Vladeta Jovovic, Oct 04 2007

A303913 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled asymmetric k-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 3, 2, 0, 1, 1, 0, 6, 10, 8, 0, 1, 1, 0, 10, 28, 54, 18, 0, 1, 1, 0, 15, 60, 193, 222, 61, 0, 1, 1, 0, 21, 110, 505, 1140, 1107, 170, 0, 1, 1, 0, 28, 182, 1095, 3876, 7688, 5346, 538, 0, 1, 1, 0, 36, 280, 2093, 10326, 33125, 52364, 27399, 1654, 0

Offset: 0

Andrew Howroyd, May 02 2018

A k-ary cactus is a planar k-gonal cactus with vertices on each polygon numbered 1..k counterclockwise with shared vertices having the same number. In total there are always exactly k ways to number a given cactus since all polygons are connected. See the reference for a precise definition. - Andrew Howroyd, Feb 18 2020

			Array begins:
===============================================================
n\k| 1   2     3      4       5        6        7         8
---+-----------------------------------------------------------
0  | 1   1     1      1       1        1        1         1 ...
1  | 1   1     1      1       1        1        1         1 ...
2  | 0   0     0      0       0        0        0         0 ...
3  | 0   1     3      6      10       15       21        28 ...
4  | 0   2    10     28      60      110      182       280 ...
5  | 0   8    54    193     505     1095     2093      3654 ...
6  | 0  18   222   1140    3876    10326    23394     47208 ...
7  | 0  61  1107   7688   33125   107056   285383    662620 ...
8  | 0 170  5346  52364  290700  1149126  3621150   9702008 ...
9  | 0 538 27399 373560 2661100 12845166 47813367 147765409 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], 1998-1999.
Wikipedia, Cactus graph
Index entries for sequences related to cacti

Columns k=2..7 are A054358, A054422, A052395, A054364, A054367, A054370.

Cf. A303694, A303912.

T[0, _] = 1;
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] Binomial[k #, #] &]/n - (k-1) Binomial[n k, n]/((k-1) n + 1);
Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, May 22 2018 *)

T(n,k)={if(n==0, 1, sumdiv(n, d, moebius(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1))}

T(n,k) = (Sum_{d|n} mu(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1) for n > 0.

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.

A052393 Number of unlabeled ternary cacti having n triangles.

Original entry on oeis.org

1, 1, 3, 6, 19, 57, 258, 1110, 5475, 27429, 143379, 764970, 4173906, 23140816, 130205922, 741650802, 4270593219, 24825326199, 145535320383, 859627488966, 5112006997539, 30586307211945, 184023410798910, 1112800162657902, 6760426635625170

Offset: 0

Simon Plouffe

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=3 of A303912.

Cf. A054422, A054423.

a[n_] := If[n == 0, 1, (Binomial[3*n, n]/(2*n+1) + DivisorSum[n, Binomial[ 3*#, #]*EulerPhi[n/#]*Boole[# < n]&])/n]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Jul 17 2017 *)

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(3*d, d))/n - 2*binomial(3*n, n)/(2*n+1)) \\ Andrew Howroyd, May 02 2018

a(n) = (1/n)*(Sum_{d|n} phi(n/d)*binomial(3*d, d)) - 2*binomial(3*n, n)/(2*n+1) for n > 0. - Andrew Howroyd, May 02 2018

a(n) ~ 3^(3*n + 1/2) / (sqrt(Pi) * 2^(2*n + 2) * n^(5/2)). - Vaclav Kotesovec, Jul 17 2017

More terms from Jean-François Alcover, Jul 17 2017

A052394 Number of unlabeled 4-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 4, 10, 44, 197, 1228, 7692, 52828, 373636, 2735952, 20506258, 156922676, 1221179926, 9642496488, 77092885016, 623121750844, 5085013101164, 41850600967984, 347060754685888, 2897800158952304, 24344668688424333, 205667187527660076, 1746375819789491996, 14898241072028602276

Offset: 0

Simon Plouffe

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=4 of A303912.

Cf. A054362, A052395.

a[n_] := If[n == 0, 1, (Binomial[4*n, n]/(3*n + 1) + DivisorSum[n, Binomial[4*#, #]*EulerPhi[n/#]*Boole[# < n] & ])/n]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Jul 17 2017 *)

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(4*d, d))/n - 3*binomial(4*n, n)/(3*n+1)) \\ Andrew Howroyd, May 02 2018

a(n) = (1/n)*(Sum_{d|n} phi(n/d)*binomial(4*d, d)) - 3*binomial(4*n, n)/(3*n+1) for n > 0. - Andrew Howroyd, May 02 2018

a(n) ~ 2^(8*n + 1/2) / (sqrt(Pi) * n^(5/2) * 3^(3*n + 3/2)). - Vaclav Kotesovec, Jul 17 2017

More terms from Jean-François Alcover, Jul 17 2017

A054363 Number of unlabeled 5-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 5, 15, 85, 510, 4051, 33130, 291925, 2661255, 25059670, 241724380, 2379912355, 23833198140, 242173108050, 2491817151160, 25921371278805, 272256630756265, 2884054952424115, 30784716141936525, 330853932861650870, 3577823885433087690, 38907658120970944700

Offset: 0

Simon Plouffe

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=5 of A303912.

Cf. A054364, A054365.

a[n_] := If[n == 0, 1, (Binomial[5*n, n]/(4*n + 1) + DivisorSum[n, Binomial[5*#, #]*EulerPhi[n/#]*Boole[# < n] & ])/n]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Jul 17 2017 *)

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(5*d, d))/n - 4*binomial(5*n, n)/(4*n+1)) \\ Andrew Howroyd, May 02 2018

a(n) = (1/n)*(Sum_{d|n} phi(n/d)*binomial(5*d, d)) - 4*binomial(5*n, n)/(4*n+1) for n > 0. - Andrew Howroyd, May 02 2018

a(n) ~ 5^(5*n + 1/2) / (sqrt(Pi) * n^(5/2) * 2^(8*n + 7/2)). - Vaclav Kotesovec, Jul 17 2017

More terms from Jean-François Alcover, Jul 17 2017

A054366 Number of unlabeled 6-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 6, 21, 146, 1101, 10632, 107062, 1151802, 12845442, 147845706, 1743640908, 20988257544, 256987965379, 3192893716320, 40171643847696, 510997002280522, 6563060603543658, 85017387536789916, 1109744672540225367, 14585261039005676046

Offset: 0

Simon Plouffe

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=6 of A303912.

Cf. A054367, A054368.

a[n_] := If[n == 0, 1, (Binomial[6*n, n]/(5 n + 1) + DivisorSum[n, Binomial[6*#, #]*EulerPhi[n/#]*Boole[# < n] & ])/n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 17 2017 *)

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(6*d, d))/n - 5*binomial(6*n, n)/(5*n+1)) \\ Andrew Howroyd, May 02 2018

a(n) = (1/n)*(Sum_{d|n} phi(n/d)*binomial(6*d, d)) - 5*binomial(6*n, n)/(5*n+1) for n > 0. - Andrew Howroyd, May 02 2018

a(n) ~ sqrt(3) * 6^(6*n) / (sqrt(Pi) * n^(5/2) * 5^(5*n + 3/2)). - Vaclav Kotesovec, Jul 17 2017

More terms from Jean-François Alcover, Jul 17 2017

A054369 Number of unlabeled 7-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 7, 28, 231, 2100, 23884, 285390, 3626295, 47813815, 650367788, 9066061200, 128987761308, 1866877313448, 27417589615234, 407771633434368, 6131640607962135, 93096368350684727, 1425633586192690945, 21998953427963954554, 341803227016091180620

Offset: 0

Simon Plouffe

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=7 of A303912.

Cf. A054370, A054371.

a[n_] := If[n == 0, 1, (Binomial[7*n, n]/(6 n + 1) + DivisorSum[n, Binomial[7*#, #]*EulerPhi[n/#]*Boole[# < n] & ])/n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 17 2017 *)

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(7*d, d))/n - 6*binomial(7*n, n)/(6*n+1)) \\ Andrew Howroyd, May 02 2018

a(n) = (1/n)*(Sum_{d|n} phi(n/d)*binomial(7*d, d)) - 6*binomial(7*n, n)/(6*n+1) for n > 0. - Andrew Howroyd, May 02 2018

a(n) ~ 7^(7*n + 1/2) / (2 * sqrt(3*Pi) * n^(5/2) * 6^(6*n + 1)). - Vaclav Kotesovec, Jul 17 2017

More terms from Jean-François Alcover, Jul 17 2017

cp's OEIS Frontend

A054357 Number of unlabeled 2-ary cacti having n polygons. Also number of bicolored plane trees with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A303913 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled asymmetric k-ary cacti having n polygons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A052393 Number of unlabeled ternary cacti having n triangles.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A052394 Number of unlabeled 4-ary cacti having n polygons.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054363 Number of unlabeled 5-ary cacti having n polygons.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054366 Number of unlabeled 6-ary cacti having n polygons.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI