A000168 a(n) = 2*3^n*(2*n)!/(n!*(n+2)!).

1, 2, 9, 54, 378, 2916, 24057, 208494, 1876446, 17399772, 165297834, 1602117468, 15792300756, 157923007560, 1598970451545, 16365932856990, 169114639522230, 1762352559231660, 18504701871932430, 195621134074714260, 2080697516976506220, 22254416920705240440, 239234981897581334730, 2583737804493878415084

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

Number of rooted planar maps with n edges. - Don Knuth, Nov 24 2013

Number of rooted 4-regular planar maps with n vertices.

Also, number of doodles with n crossings, irrespective of the number of loops.

From Karol A. Penson, Sep 02 2010: (Start)

Integral representation as n-th moment of a positive function on the (0,12) segment of the x axis. This representation is unique as it is the solution of the Hausdorff moment problem.

a(n) = Integral_{x=0..12} ((x^n*(4/9)*(1 - x/12)^(3/2)) / (Pi*sqrt(x/3))). (End)

Also, the number of distinct underlying shapes of closed normal linear lambda terms of a given size, where the shape of a lambda term abstracts away from its variable binding. [N. Zeilberger, 2015] - N. J. A. Sloane, Sep 18 2016

The September 2018 talk by Noam Zeilberger (see link to video) connects three topics (planar maps, Tamari lattices, lambda calculus) and eight sequences: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. - N. J. A. Sloane, Sep 17 2018

Number of well-labeled trees (Bona, 2015). - N. J. A. Sloane, Dec 25 2018

Examples

			G.f. = 1 + 2*x + 9*x^2 + 54*x^3 + 378*x^4 + 2916*x^5 + 24057*x^6 + 208494*x^7 + ...
		

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 319, 353.
• E. R. Canfield, Calculating the number of rooted maps on a surface, Congr. Numerantium, 76 (1990), 21-34.
• J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.
• V. A. Liskovets, A census of nonisomorphic planar maps, in Algebraic Methods in Graph Theory, Vol. II, ed. L. Lovasz and V. T. Sos, North-Holland, 1981.
• V. A. Liskovets, Enumeration of nonisomorphic planar maps, Selecta Math. Sovietica, 4 (No. 4, 1985), 303-323.
• 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

• G. C. Greubel, Table of n, a(n) for n = 0..925 [Terms 0 to 100 computed by T. D. Noe; terms 101 to 925 by G. C. Greubel, Jan 15 2017]
• Marie Albenque and Dominique Poulalhon, A Generic Method for Bijections between Blossoming Trees and Planar Maps, Electron. J. Combin., 22 (2015), #P2.38.
• J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, Rooted planar maps modulo some patterns, Preprint 2016.
• Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
• Valentin Bonzom, Guillaume Chapuy, Maciej Dolega, Enumeration of non-oriented maps via integrability, Alg. Combin. 5 (6) (2022) p 1363-1390, A.1.
• M. Bousquet-Mélou, Limit laws for embedded trees, arXiv:math/0501266 [math.CO], 2005.
• M. Bousquet-Mélou and A. Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, arXiv:math/0504018 [math.CO], 2005.
• Sean R. Carrell and Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014.
• R. Cori and B. Vauquelin, Planar maps are well labeled trees, Canad. J. Math., 33 (1981), 1023-1042.
• S. R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 516
• A. Giorgetti, R. Genestier, and V. Senni, Software Engineering and Enumerative Combinatorics, slides from a talk at MAP 2014.
• Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
• C. Kassel, On combinatorial zeta functions, Slides from a talk, Potsdam, 2015.
• Sergey Kitaev, Anna de Mier, and Marc Noy, On the number of self-dual rooted maps, European J. Combin. 35 (2014), 377--387. MR3090510. See Eq. (1). - _N. J. A. Sloane_, May 19 2014
• Evgeniy Krasko and Alexander Omelchenko, Enumeration of r-regular maps on the torus. Part I: Rooted maps on the torus, the projective plane and the Klein bottle. Sensed maps on the torus, Discrete Mathematics (2019) Vol. 342, Issue 2, 584-599. Also arXiv:1709.03225 [math.CO].
• V. A. Liskovets, Enumeration of nonisomorphic planar maps, Journal of Graph Theory, Volume 5, Issue 1, pages 115-117, Spring 1981.
• Valery A. Liskovets, A reductive technique for enumerating non-isomorphic planar maps, Discrete Math. 156 (1996), no. 1-3, 197--217. MR1405018 (97f:05087) - From _N. J. A. Sloane_, Jun 03 2012
• R. C. Mullin, On the average activity of a spanning tree of a rooted map, J. Combin. Theory, 3 (1967), 103-121.
• R. C. Mullin, On the average activity of a spanning tree of a rooted map, J. Combin. Theory, 3 (1967), 103-121. [Annotated scanned copy]
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série, arXiv:0912.0072 [math.NT], 2009; FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.
• C. Reutenauer and M. Robado, On an algebraicity theorem of Kontsevich, FPSAC 2012, Nagoya, Japan DMTCS proc. AR, 2012, 241-248. - From _N. J. A. Sloane_, Dec 23 2012
• G. Schaeffer and P. Zinn-Justin, On the asymptotic number of plane curves and alternating knots, arXiv:math-ph/0304034, 2003-2004.
• W. T. Tutte, A Census of Planar Maps, Canad. J. Math. 15 (1963), 249-271.
• Noam Zeilberger, Counting isomorphism classes of beta-normal linear lambda terms, arXiv:1509.07596 [cs.LO], 2015.
• Noam Zeilberger, Towards a mathematical science of programming, Preprint 2015.
• Noam Zeilberger, Linear lambda terms as invariants of rooted trivalent maps, arXiv preprint arXiv:1512.06751 [cs.LO], 2015.
• Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018.
• Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv preprint 1803.10030, March 2018 (A revised version of a 2017 conference paper)
• Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Part 2, Rutgers Experimental Math Seminar, Sep 13 2018.
• Noam Zeilberger and Alain Giorgetti, A correspondence between rooted planar maps and normal planar lambda terms, arXiv:1408.5028 [cs.LO], 2014-2015; Logical Methods in Computer Science, vol. 11 (3:22), 2015, pp. 1-39.
• Jian Zhou, Fat and Thin Emergent Geometries of Hermitian One-Matrix Models, arXiv:1810.03883 [math-ph], 2018.

Crossrefs

Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.

First row of array A101486.

Cf. A005470.

Rooted maps with n edges of genus g for 0 <= g <= 10: this sequence, A006300, A006301, A104742, A215402, A238355, A238356, A238357, A238358, A238359, A238360.

Programs

Magma

[(2*Catalan(n)*3^n)/(n+2): n in [1..30]]; // Vincenzo Librandi, Sep 04 2014

Maple

A000168:=n->2*3^n*(2*n)!/(n!*(n+2)!);

Mathematica

Table[(2*3^n*(2n)!)/(n!(n+2)!),{n,0,20}] (* Harvey P. Dale, Jul 25 2011 *)
a[ n_] := If[ n < 0, 0, 2 3^n (2 n)!/(n! (n + 2)!)] (* Michael Somos, Nov 25 2013 *)
a[ n_] := SeriesCoefficient[ Hypergeometric2F1[ 1/2, 1, 3, 12 x], {x, 0, n}] (* Michael Somos, Nov 25 2013 *)

PARI

{a(n) = if( n<0, 0, 2 * 3^n * (2*n)! / (n! * (n+2)!))}; /* Michael Somos, Nov 25 2013 */

Formula

G.f. A(z) satisfies A(z) = 1 - 16*z + 18*z*A(z) - 27*z^2*A(z)^2.

G.f.: F(1/2,1;3;12x). - Paul Barry, Feb 04 2009

a(n) = 2*3^n*A000108(n)/(n+2). - Paul Barry, Feb 04 2009

D-finite with recurrence: (n + 1) a(n) = (12 n - 18) a(n - 1). - Simon Plouffe, Feb 09 2012

G.f.: 1/54*(-1+18*x+(-(12*x-1)^3)^(1/2))/x^2. - Simon Plouffe, Feb 09 2012

0 = a(n)*(+144*a(n+1) - 42*a(n+2)) + a(n+1)*(+18*a(n+1) + a(n+2)) if n>=0. - Michael Somos, Jan 31 2014

a(n) ~ 2*(12^n)/((n^2+3*n)*sqrt(Pi*n)). - Peter Luschny, Nov 25 2015

E.g.f.: exp(6*x)*(12*x*BesselI(0,6*x) - (1 + 12*x)*BesselI(1,6*x))/(9*x). - Ilya Gutkovskiy, Feb 01 2017

From Amiram Eldar, Jan 08 2023: (Start)

Sum_{n>=0} 1/a(n) = 1887/1331 + 3240*arccosec(2*sqrt(3))/(1331*sqrt(11)).

Sum_{n>=0} (-1)^n/a(n) = 1563/2197 - 3240*arccosech(2*sqrt(3))/(2197*sqrt(13)). (End)

Extensions

More terms from Joerg Arndt, Feb 26 2014