login
The OEIS is supported by the many generous donors 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)
35

%I M1940 N0768 #204 Mar 02 2023 08:42:12

%S 1,2,9,54,378,2916,24057,208494,1876446,17399772,165297834,1602117468,

%T 15792300756,157923007560,1598970451545,16365932856990,

%U 169114639522230,1762352559231660,18504701871932430,195621134074714260,2080697516976506220,22254416920705240440,239234981897581334730,2583737804493878415084

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

%C Number of rooted planar maps with n edges. - _Don Knuth_, Nov 24 2013

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

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

%C From _Karol A. Penson_, Sep 02 2010: (Start)

%C 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.

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

%C 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

%C 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

%C Number of well-labeled trees (Bona, 2015). - _N. J. A. Sloane_, Dec 25 2018

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 319, 353.

%D E. R. Canfield, Calculating the number of rooted maps on a surface, Congr. Numerantium, 76 (1990), 21-34.

%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.

%D 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.

%D V. A. Liskovets, Enumeration of nonisomorphic planar maps, Selecta Math. Sovietica, 4 (No. 4, 1985), 303-323.

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

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

%H G. C. Greubel, <a href="/A000168/b000168.txt">Table of n, a(n) for n = 0..925</a> [Terms 0 to 100 computed by T. D. Noe; terms 101 to 925 by G. C. Greubel, Jan 15 2017]

%H Marie Albenque and Dominique Poulalhon, <a href="https://doi.org/10.37236/3386">A Generic Method for Bijections between Blossoming Trees and Planar Maps</a>, Electron. J. Combin., 22 (2015), #P2.38.

%H J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/cartes.pdf">Rooted planar maps modulo some patterns</a>, Preprint 2016.

%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.

%H Valentin Bonzom, Guillaume Chapuy, Maciej Dolega, <a href="https://doi.org/10.5802/alco.268">Enumeration of non-oriented maps via integrability</a>, Alg. Combin. 5 (6) (2022) p 1363-1390, A.1.

%H M. Bousquet-Mélou, <a href="https://arxiv.org/abs/math/0501266">Limit laws for embedded trees</a>, arXiv:math/0501266 [math.CO], 2005.

%H M. Bousquet-Mélou and A. Jehanne, <a href="https://arxiv.org/abs/math/0504018">Polynomial equations with one catalytic variable, algebraic series and map enumeration</a>, arXiv:math/0504018 [math.CO], 2005.

%H Sean R. Carrell and Guillaume Chapuy, <a href="http://arxiv.org/abs/1402.6300">Simple recurrence formulas to count maps on orientable surfaces</a>, arXiv:1402.6300 [math.CO], 2014.

%H R. Cori and B. Vauquelin, <a href="http://dx.doi.org/10.4153/CJM-1981-078-2">Planar maps are well labeled trees</a>, Canad. J. Math., 33 (1981), 1023-1042.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 516

%H A. Giorgetti, R. Genestier, and V. Senni, <a href="http://perso.crans.org/cohen/map2014/raw/Giorgetti.pdf">Software Engineering and Enumerative Combinatorics</a>, slides from a talk at MAP 2014.

%H Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, <a href="https://doi.org/10.4230/LIPIcs.AofA.2018.29">Asymptotic Expansions for Sub-Critical Lagrangean Forms</a>, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.

%H C. Kassel, <a href="http://www-irma.u-strasbg.fr/~kassel/Potsdam130515.pdf">On combinatorial zeta functions</a>, Slides from a talk, Potsdam, 2015.

%H Sergey Kitaev, Anna de Mier, and Marc Noy, <a href="http://dx.doi.org/10.1016/j.ejc.2013.06.013">On the number of self-dual rooted maps</a>, European J. Combin. 35 (2014), 377--387. MR3090510. See Eq. (1). - _N. J. A. Sloane_, May 19 2014

%H Evgeniy Krasko and Alexander Omelchenko, <a href="https://doi.org/10.1016/j.disc.2018.07.013">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</a>, Discrete Mathematics (2019) Vol. 342, Issue 2, 584-599. Also <a href="https://arxiv.org/abs/1709.03225">arXiv:1709.03225 [math.CO]</a>.

%H V. A. Liskovets, <a href="http://dx.doi.org/10.1002/jgt.3190050110">Enumeration of nonisomorphic planar maps</a>, Journal of Graph Theory, Volume 5, Issue 1, pages 115-117, Spring 1981.

%H Valery A. Liskovets, <a href="http://dx.doi.org/10.1016/0012-365X(94)00347-L">A reductive technique for enumerating non-isomorphic planar maps</a>, Discrete Math. 156 (1996), no. 1-3, 197--217. MR1405018 (97f:05087) - From _N. J. A. Sloane_, Jun 03 2012

%H R. C. Mullin, <a href="http://dx.doi.org/10.1016/S0021-9800(67)80001-2">On the average activity of a spanning tree of a rooted map</a>, J. Combin. Theory, 3 (1967), 103-121.

%H R. C. Mullin, <a href="/A260039/a260039.pdf">On the average activity of a spanning tree of a rooted map</a>, J. Combin. Theory, 3 (1967), 103-121. [Annotated scanned copy]

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="http://arxiv.org/abs/0912.0072">Une méthode pour obtenir la fonction génératrice d'une série</a>, arXiv:0912.0072 [math.NT], 2009; FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.

%H C. Reutenauer and M. Robado, <a href="http://www.math.nagoya-u.ac.jp/fpsac12/download/contributed/dmAR0122.pdf">On an algebraicity theorem of Kontsevich</a>, FPSAC 2012, Nagoya, Japan DMTCS proc. AR, 2012, 241-248. - From _N. J. A. Sloane_, Dec 23 2012

%H G. Schaeffer and P. Zinn-Justin, <a href="https://arxiv.org/abs/math-ph/0304034">On the asymptotic number of plane curves and alternating knots</a>, arXiv:math-ph/0304034, 2003-2004.

%H W. T. Tutte, <a href="http://dx.doi.org/10.4153/CJM-1963-029-x">A Census of Planar Maps</a>, Canad. J. Math. 15 (1963), 249-271.

%H Noam Zeilberger, <a href="http://arxiv.org/abs/1509.07596">Counting isomorphism classes of beta-normal linear lambda terms</a>, arXiv:1509.07596 [cs.LO], 2015.

%H Noam Zeilberger, <a href="http://noamz.org/research-statement-short.pdf">Towards a mathematical science of programming</a>, Preprint 2015.

%H Noam Zeilberger, <a href="https://arxiv.org/abs/1512.06751">Linear lambda terms as invariants of rooted trivalent maps</a>, arXiv preprint arXiv:1512.06751 [cs.LO], 2015.

%H Noam Zeilberger, <a href="https://arxiv.org/abs/1804.10540">A theory of linear typings as flows on 3-valent graphs</a>, arXiv:1804.10540 [cs.LO], 2018.

%H Noam Zeilberger, <a href="https://arxiv.org/abs/1803.10080">A Sequent Calculus for a Semi-Associative Law</a>, arXiv preprint 1803.10030, March 2018 (A revised version of a 2017 conference paper)

%H Noam Zeilberger, <a href="https://vimeo.com/289907363">A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video)</a>, <a href="https://vimeo.com/289910554">Part 2</a>, Rutgers Experimental Math Seminar, Sep 13 2018.

%H Noam Zeilberger and Alain Giorgetti, <a href="https://arxiv.org/abs/1408.5028">A correspondence between rooted planar maps and normal planar lambda terms</a>, arXiv:1408.5028 [cs.LO], 2014-2015; Logical Methods in Computer Science, vol. 11 (3:22), 2015, pp. 1-39.

%H Jian Zhou, <a href="https://arxiv.org/abs/1810.03883">Fat and Thin Emergent Geometries of Hermitian One-Matrix Models</a>, arXiv:1810.03883 [math-ph], 2018.

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

%F G.f.: F(1/2,1;3;12x). - _Paul Barry_, Feb 04 2009

%F a(n) = 2*3^n*A000108(n)/(n+2). - _Paul Barry_, Feb 04 2009

%F D-finite with recurrence: (n + 1) a(n) = (12 n - 18) a(n - 1). - _Simon Plouffe_, Feb 09 2012

%F G.f.: 1/54*(-1+18*x+(-(12*x-1)^3)^(1/2))/x^2. - _Simon Plouffe_, Feb 09 2012

%F 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

%F a(n) ~ 2*(12^n)/((n^2+3*n)*sqrt(Pi*n)). - _Peter Luschny_, Nov 25 2015

%F 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

%F From _Amiram Eldar_, Jan 08 2023: (Start)

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

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

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

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

%t Table[(2*3^n*(2n)!)/(n!(n+2)!),{n,0,20}] (* _Harvey P. Dale_, Jul 25 2011 *)

%t a[ n_] := If[ n < 0, 0, 2 3^n (2 n)!/(n! (n + 2)!)] (* _Michael Somos_, Nov 25 2013 *)

%t a[ n_] := SeriesCoefficient[ Hypergeometric2F1[ 1/2, 1, 3, 12 x], {x, 0, n}] (* _Michael Somos_, Nov 25 2013 *)

%o (PARI) {a(n) = if( n<0, 0, 2 * 3^n * (2*n)! / (n! * (n+2)!))}; /* _Michael Somos_, Nov 25 2013 */

%o (Magma) [(2*Catalan(n)*3^n)/(n+2): n in [1..30]]; // _Vincenzo Librandi_, Sep 04 2014

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

%Y First row of array A101486.

%Y Cf. A005470.

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

%K nonn,nice,easy

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Joerg Arndt_, Feb 26 2014

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:15 EDT 2024. Contains 371265 sequences. (Running on oeis4.)