OFFSET
0,3
COMMENTS
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
LINKS
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
FORMULA
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
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}] (* Jean-Franç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([a(n) for n in range(31)]) # Indranil Ghosh, Jul 17 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from Len Smiley, Sep 06 2005
More terms from Vladeta Jovovic, Oct 04 2007
STATUS
approved