A002740 Number of tree-rooted bridgeless planar maps with two vertices and n faces.

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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.

Crossrefs

Cf. A129175.

A diagonal of A253180.

Programs

Magma

[(n-2)*Binomial(2*n-2,n-2)/2 : n in [0..30]]; // Wesley Ivan Hurt, Sep 24 2014

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 *)

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 */

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)

Extensions

Name clarified by Noam Zeilberger, Aug 18 2017