cp's OEIS Frontend

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

%I A054357 #51 Jan 09 2024 10:54:18
%S A054357 1,1,2,3,6,10,28,63,190,546,1708,5346,17428,57148,191280,646363,
%T A054357 2210670,7626166,26538292,93013854,328215300,1165060668,4158330416,
%U A054357 14915635378,53746119972,194477856100,706437056648,2575316704200,9419571138368
%N A054357 Number of unlabeled 2-ary cacti having n polygons. Also number of bicolored plane trees with n edges.
%C A054357 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
%H A054357 Indranil Ghosh, <a href="/A054357/b054357.txt">Table of n, a(n) for n = 0..1000</a>
%H A054357 Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, <a href="https://doi.org/10.1006/aama.1999.0665">Enumeration of m-ary cacti</a>, Advances in Applied Mathematics, 24 (2000), 22-56.
%H A054357 Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Partition_related_number_triangles#rot">Partition related number triangles</a>
%H A054357 <a href="/index/Ca#cacti">Index entries for sequences related to cacti</a>
%F A054357 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
%F A054357 a(n) ~ 2^(2*n) / (sqrt(Pi) * n^(5/2)). - _Vaclav Kotesovec_, Jul 17 2017
%t A054357 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 *)
%o A054357 (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
%o A054357 (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
%o A054357 (Python)
%o A054357 from sympy import binomial, divisors, totient
%o A054357 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
%o A054357 print([a(n) for n in range(31)]) # _Indranil Ghosh_, Jul 17 2017
%Y A054357 Column k=2 of A303912.
%Y A054357 Row sums of A209805.
%Y A054357 Cf. A002995, A054358, A111275.
%K A054357 nonn
%O A054357 0,3
%A A054357 _Simon Plouffe_
%E A054357 More terms from _Len Smiley_, Sep 06 2005
%E A054357 More terms from _Vladeta Jovovic_, Oct 04 2007