A002996 a(n) = Sum_{k|n} mu(k)*Catalan(n/k) (mu = Moebius function A008683).

1, 1, 4, 12, 41, 126, 428, 1416, 4857, 16753, 58785, 207868, 742899, 2674010, 9694799, 35356240, 129644789, 477633711, 1767263189, 6564103612, 24466266587, 91482504853, 343059613649, 1289903937896, 4861946401410, 18367352329251, 69533550911142, 263747949075908, 1002242216651367

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Moebius transform of A000108.

References

• A. Errera, Analysis situs - Un problème d'énumération, Mémoires Acad. Bruxelles, Classe des sciences, Série 2, Vol. XI, Fasc. 6, No. 1421 (1931), 26 pp.
• A. Errera, De quelques problèmes d'analysis situs, Comptes Rend. Congr. Nat. Sci. Bruxelles, (1930), 106-110.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n=1..200
• A. Errera, Analysis situs. Un problème d'énumération.
• A. Errera, Reviews of two articles on Analysis Situs, from Fortschritte [Annotated scanned copy]

Crossrefs

Cf. A002995, A027750.

Programs

Haskell

a002996 n = sum $ zipWith (*) (map a008683 divs) (map a000108 $ reverse divs)
   where divs = a027750_row n
-- Reinhard Zumkeller, Dec 22 2013

Mathematica

Table[Sum[MoebiusMu[k] CatalanNumber[n/k],{k,Divisors[n]}],{n,30}] (* Harvey P. Dale, Oct 07 2014 *)

PARI

a(n)=sumdiv(n, d, moebius(n/d)*binomial(2*d,d)/(d+1)); \\ Joerg Arndt, Jun 15 2013

Formula

G.f.: 1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) = 1/(1 - x/(1 - x/(1 - x/(1 - ...)))). - Ilya Gutkovskiy, May 06 2017

Extensions

More terms from James Sellers, Sep 08 2000

References corrected by M. F. Hasler, Aug 24 2012