|
|
A000168
|
|
a(n) = 2*3^n*(2*n)!/(n!*(n+2)!).
(Formerly M1940 N0768)
|
|
32
|
|
|
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
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
|
|
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.
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.
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.
|
|
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
|
|
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
|
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.
Sequence in context: A223943 A241125 A089436 * A307442 A222014 A321974
Adjacent sequences: A000165 A000166 A000167 * A000169 A000170 A000171
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
N. J. A. Sloane
|
|
EXTENSIONS
|
More terms from Joerg Arndt, Feb 26 2014
|
|
STATUS
|
approved
|
|
|
|