login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000168 a(n) = 2*3^n*(2*n)!/(n!*(n+2)!).
(Formerly M1940 N0768)
22
1, 2, 9, 54, 378, 2916, 24057, 208494, 1876446, 17399772, 165297834, 1602117468, 15792300756, 157923007560, 1598970451545, 16365932856990, 169114639522230, 1762352559231660, 18504701871932430, 195621134074714260, 2080697516976506220, 22254416920705240440, 239234981897581334730, 2583737804493878415084 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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.

In Maple notation: a(n)=int(x^n*(4/9)*sqrt(3)*(1-(1/12)*x)^(3/2)/(Pi*sqrt(x)), x=0..12), n=0,1,...

This representation is unique as it is the solution of the Hausdorff moment problem. (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

REFERENCES

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.

C. Kassel, On combinatorial zeta functions, Slides from a talk, Potsdam, 2015: http://www-irma.u-strasbg.fr/~kassel/Potsdam130515.pdf.

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

N Zeilberger, Towards a mathematical science of programming, Preprint 2015; http://noamz.org/research-statement-short.pdf

LINKS

T. D. Noe, Table of n, a(n) for n=0..100

Marie Albenque, Dominique Poulalhon, A Generic Method for Bijections between Blossoming Trees and Planar Maps, Electron. J. Combin., 22 (2015), #P2.38.

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, Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], (19-March-2014)

R. Cori and B. Vauquelin, Planar maps are well labeled trees, Canad. J. Math., 33 (1981), 1023-1042.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 516

A. Giorgetti, R. Genestier, V. Senni, Software Engineering and Enumerative Combinatorics, slides from a talk at MAP 2014.

Sergey Kitaev, Anna de Mier, 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

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.

Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série. 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 and Alain Giorgetti, A correspondence between rooted planar maps and normal planar lambda terms, Logical Methods in Computer Science, vol. 11 (3:22), 2015, pp. 1-39.

FORMULA

G.f. 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

(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

EXAMPLE

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

MAPLE

f:=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 *)

PROG

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

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

CROSSREFS

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.

Sequence in context: A223943 A241125 A089436 * A222014 A127128 A254795

Adjacent sequences:  A000165 A000166 A000167 * A000169 A000170 A000171

KEYWORD

nonn,nice,easy,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Joerg Arndt, Feb 26 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 18:10 EDT 2016. Contains 276546 sequences.