

A054357


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


18



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

a(n) = the number of inequivalent noncrossing partitions of n points (equally spaced) on a circle, under rotations of the circle. This may be considered the number of noncrossing 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


LINKS

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


FORMULA

a(n) = (1/n)*(Sum_{dn} 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


MATHEMATICA

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}] (* JeanFrançois Alcover, Jul 17 2017 *)


PROG

(PARI) a(n)=if(n==0, 1, (binomial(2*n, n)/(n + 1) + sumdiv(n, d, binomial(2*d, d)*eulerphi(n/d)*(d<n)))/n); \\ Indranil Ghosh, Jul 17 2017
(PARI) 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
(Python)
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)*(d<n) for d in divisors(n)]))/n
print map(a, range(31)) # Indranil Ghosh, Jul 17 2017


CROSSREFS

Column k=2 of A303912.
Row sums of A209805.
Cf. A002995, A054358, A111275.
Sequence in context: A192440 A327711 A274964 * A056606 A186408 A062527
Adjacent sequences: A054354 A054355 A054356 * A054358 A054359 A054360


KEYWORD

nonn,changed


AUTHOR

Simon Plouffe


EXTENSIONS

More terms from Len Smiley, Sep 06 2005
More terms from Vladeta Jovovic, Oct 04 2007


STATUS

approved



