A054358 -id:A054358 - 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.

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