login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054357 Number of unlabeled 2-ary cacti having n polygons. Also number of bi-colored 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 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 (pdf, dvi).

Tilman Piesk, Partition related number triangles

Index entries for sequences related to cacti

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 map(a, xrange(31)) # Indranil Ghosh, Jul 17 2017

CROSSREFS

Column k=2 of A303912.

Row sums of A209805.

Cf. A002995, A054358, A111275.

Sequence in context: A212606 A192440 A274964 * A056606 A186408 A062527

Adjacent sequences:  A054354 A054355 A054356 * A054358 A054359 A054360

KEYWORD

nonn

AUTHOR

Simon Plouffe

EXTENSIONS

More terms from Len Smiley, Sep 06 2005

More terms from Vladeta Jovovic, Oct 04 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 20 11:12 EDT 2018. Contains 305614 sequences. (Running on oeis4.)