A002740 Number of tree-rooted bridgeless planar maps with two vertices and n faces. (Formerly M2078 N0821)

0, 0, 0, 2, 15, 84, 420, 1980, 9009, 40040, 175032, 755820, 3233230, 13728792, 57946200, 243374040, 1017958725, 4242920400, 17631691440, 73078721100, 302202005490, 1247182879800, 5137916074200, 21132472200840, 86794082253450, 356013544661424, 1458583920435600, 5969389748449400

Offset

0,4

Comments

a(n) is the sum of the major indices of all Dyck words of length 2n-2. The major index of a Dyck word is the sum of the positions of those 1's that are followed by a 0. Example: a(4)=15 because the Dyck words of length 6 are 010101, 010011, 001101, 001011 and 000111 having major indices 6,2,4,3 and 0, respectively. a(n) = Sum_{k=0..n(n-1)} k*A129175(n,k). - Emeric Deutsch, Apr 20 2007

References

J. Ser, Les Calculs Formels des Séries de Factorielles, Gauthier-Villars, Paris, 1933, p. 97.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Mireille Bousquet-Mélou, New enumerative results on two-dimensional directed animals, Discr. Math., Vol. 180, No. 1-3 (1998), pp. 73-106. See Cor. 6.6.

Luca Ferrari and Emanuele Munarini, Enumeration of saturated chains in Dyck lattices, arXiv preprint arXiv:1203.6807 [math.CO], 2012.

J. Fürlinger and J. Hofbauer, q-Catalan numbers, J. Comb. Theory, Series A, Vol. 40, No. 2 (1985), pp. 248-264.

Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k, arXiv:2204.14023 [math.CO], 2022.

J. Ser, Les Calculs Formels des Séries de Factorielles, Gauthier-Villars, Paris, 1933 [Local copy].

J. Ser, Les Calculs Formels des Séries de Factorielles, Gauthier-Villars, Paris, 1933. (Annotated scans of some selected pages)

Mark Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5 (2005), Paper A07.

T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus III: Nonseparable maps, J. Combinatorial Theory Ser. B, Vol. 18, No. 3 (1975), pp. 222-259. See Table VIIIb.

Formula

G.f.: (1/2)*(1-(1 - 6*t + 6*t^2)/(1-4*t)^(3/2)).

a(n+3) = (2*(n+2))!/(2*n!*(n+3)!). - Wolfdieter Lang

a(n+2) = Sum_{k=0..n} k*binomial(k+n, k). - Benoit Cloitre, Oct 25 2003

a(n) = Sum_{k=2..n} Sum_{j=1..n} binomial(2*n,n)/(2*(n+1)), n >= 0. - Zerinvary Lajos, May 09 2007

a(n) = (n-2)*binomial(2n-2, n-2)/2 + 0^n. - Wesley Ivan Hurt, Sep 24 2014

E.g.f.: (1 + exp(2*x) * ((2*x - 1) * BesselI(0,2*x) - x * BesselI(1,2*x))) / 2. - Ilya Gutkovskiy, Nov 03 2021

From Amiram Eldar, Mar 22 2022: (Start)

Sum_{n>=3} 1/a(n) = 3 - 4*Pi/(3*sqrt(3)).

Sum_{n>=3} (-1)^(n+1)/a(n) = 16*log(phi)/sqrt(5) - 3, where phi is the golden ratio (A001622). (End)

Maple

with(combinat):for n from 0 to 22 do printf(`%d, `, n*sum(binomial(2*n, n)/(n+1)/2, k=2..n)) od: # Zerinvary Lajos, Mar 13 2007
a:=n->sum(sum(binomial(2*n, n)/(n+1)/2, j=1..n), k=2..n): seq(a(n), n=0..25); # Zerinvary Lajos, May 09 2007
A002740:=n->(n-2)*binomial(2*n-2, n-2)/2+0^n: seq(A002740(n), n=0..30); # Wesley Ivan Hurt, Sep 24 2014

Mathematica

a[n_] := (n-1)(n-2)Binomial[2(n-1), n-1]/(2n); a[0] = 0; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Nov 16 2011 *)

Prog

(MuPAD) combinat::catalan(n) *binomial(n, 2) $ n = 0..22 // Zerinvary Lajos, Feb 15 2007
(PARI) a(n)=if(n<3, 0, (2*(n-1))!/(2*n!*(n-3)!)); /* Joerg Arndt, Sep 28 2012 */
(Magma) [(n-2)*Binomial(2*n-2, n-2)/2 : n in [0..30]]; // Wesley Ivan Hurt, Sep 24 2014

Crossrefs

Cf. A129175.

A diagonal of A253180.

Sequence in context: A301566 A109725 A057152 * A178750 A108475 A328007

Adjacent sequences: A002737 A002738 A002739 * A002741 A002742 A002743

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Name clarified by Noam Zeilberger, Aug 18 2017

Status

approved