A060404 G.f.: Sum_{k >= 1} (phi(k)/k)*log(1-f(x^k)), where f(x) = (1 - sqrt(1 - 4*x)) / (2*x) - 1 is the g.f. for the Catalan numbers (A000108) C_1, C_2, C_3, ...

0, 1, 3, 8, 25, 78, 270, 926, 3305, 11868, 43232, 158586, 586530, 2181088, 8154710, 30620868, 115435625, 436654794, 1656793374, 6303490610, 24041649128, 91899730068, 352002058402, 1350767683698, 5192237233602, 19989786008160

Offset: 0

Author

N. J. A. Sloane, Apr 05 2001

Keywords

• nonn

Comments

Counts cycles of objects where the individual objects are anything enumerated by the Catalan numbers C_1, C_2, ...

The number of unrooted two-face n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005

References

• V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• P. Flajolet and M. Soria, The Cycle Construction In SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
• V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36, No.4 (2006), 364-387.

Crossrefs

Cf. A103943.

Programs

Mathematica

max = 25; f[x_] := (1 - Sqrt[1 - 4*x])/(2*x) - 1; gf = Sum[(EulerPhi[k]/k)*Log[1 - f[x^k]], {k, 1, max}]; CoefficientList[ Series[-gf, {x, 0, max}], x] (* Jean-François Alcover, Jan 21 2013 *)

PARI

a(n) = sumdiv(n, d, eulerphi(n/d)*(2^(2*d-1) - binomial(2*d-1, d)))/n; \\ Andrew Howroyd, Apr 02 2017

Formula

a(n) = (1/n) * Sum_{d|n} phi(n/d) * A000346(d-1) for n>0. - Andrew Howroyd, Apr 02 2017