login
Number of rooted planar cubic maps with 2n vertices.
(Formerly M3646 N1483)
12

%I M3646 N1483 #99 Mar 02 2023 08:46:44

%S 1,4,32,336,4096,54912,786432,11824384,184549376,2966845440,

%T 48855252992,820675092480,14018773254144,242919827374080,

%U 4261707069259776,75576645116559360,1353050213048123392,24428493151359467520,444370175232646840320,8138178004138611179520

%N Number of rooted planar cubic maps with 2n vertices.

%C Equivalently, number of rooted planar triangulations with 2n faces.

%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

%D R. C. Mullin, E. Nemeth and P. J. Schellenberg, The enumeration of almost cubic maps, pp. 281-295 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 1, edited R. C. Mullin et al., 1970.

%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 Gheorghe Coserea, <a href="/A002005/b002005.txt">Table of n, a(n) for n = 0..1000</a>

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

%H Mireille Bousquet-Mélou, <a href="https://hal.archives-ouvertes.fr/hal-00653963/">Counting planar maps, coloured or uncoloured</a>, 23rd British Combinatorial Conference, Jul 2011, Exeter, United Kingdom. 392, pp.1-50, 2011, London Math. Soc. Lecture Note Ser., hal-00653963. See p.13.

%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 Maxim Krikun, <a href="http://arxiv.org/abs/0706.0681">Explicit enumeration of triangulations with multiple boundaries</a>, arXiv:0706.0681 [math.CO], 2007. [Comment from _Gheorghe Coserea_, Dec 26 2015: the formula in the paper for almost trivalent maps is 2 * 4^(k-1) * (3k)!!/ ((k+1)!*(k+2)!!); however, the exponent of 4 should be k not (k-1) i.e. 2 * 4^k * (3k)!! / ((k+1)!*(k+2)!!)]

%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 [math.LO], 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 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 a(n) = 2^(2*n+1)*(3*n)!!/((n+2)!*n!!). - _Sean A. Irvine_, May 19 2013

%F a(n) ~ sqrt(6/Pi) * n^(-5/2) * (12*sqrt(3))^n. - _Gheorghe Coserea_, Feb 25 2016

%F G.f.: (96*x - 1 + 2F1(-2/3, -1/3; 1/2; 432*x^2) - 96*x*2F1(-1/6, 1/6; 3/2; 432*x^2))/(192*x^2). - _Benedict W. J. Irwin_, Aug 07 2016

%F From _Gheorghe Coserea_, Jun 13 2017: (Start)

%F G.f. y(x) satisfies:

%F x*(1-432*x^2)*deriv(y,x) = 64*x^2*y^2 + (288*x^2 - 64*x - 1)*y + 72*x + 1.

%F 0 = 64*x^3*y^3 + x*(1-96*x)*y^2 + (30*x-1)*y - 27*x + 1.

%F (End).

%F D-finite with recurrence (n+2)*(n+1)*a(n) -48*(3*n-2)*(3*n-4)*a(n-2)=0. - _R. J. Mathar_, Feb 08 2021

%F From _Karol A. Penson_ and Katarzyna Gorska (katarzyna.gorska@ifj.edu.pl), Nov 02 2022: (Start)

%F a(n) = Integral_{x=0..12*sqrt(3)} x^n*W(x), where

%F W(x) = (T1(x) + T2(x)) / T3(x), and

%F T1(x) = -x^(2/3) * (108 + sqrt(3) * sqrt(432 - x^2));

%F T2(x) = 3^(1/6)*(36+sqrt(3)*sqrt(432-x^2))^(2/3) * (-432+x^2+36*sqrt(3)* sqrt(432-x^2)) / sqrt(432-x^2);

%F T3(x) = (128*3^(5/6)*Pi*x^(1/3)*(36+sqrt(3)*sqrt(432-x^2))^(1/3)).

%F This integral representation is unique as W(x) is the solution of the Hausdorff power moment problem. Using only the definition of a(n), W(x) can be proven to be positive. W(x) is singular at x = 0, with the singularity x^(-1/3), and for x > 0 is monotonically decreasing to zero at x = 12*sqrt(3). (End)

%F a(n) = 2^(3*n + 1)*binomial(n*3/2, n)/((n + 1)*(n + 2)) = A358367(n) / A000217(n + 1). - _Peter Luschny_, Nov 14 2022

%p seq(2*8^n*binomial(n*3/2, n)/((n + 2)*(n + 1)), n = 0..19); # _Peter Luschny_, Nov 14 2022

%t Table[2^(2 n + 1) (3 n)!!/((n + 2)! n!!), {n, 0, 20}] (* _Vincenzo Librandi_, Dec 28 2015 *)

%t CoefficientList[Series[(-1 + 96 z + Hypergeometric2F1[-2/3,-1/3,1/2,432z^2]- 96 z Hypergeometric2F1[-1/6,1/6,3/2,432z^2])/(192 z^2), {z, 0, 10}], z] (* _Benedict W. J. Irwin_, Aug 07 2016 *)

%o (PARI) factorial2(n) = my(x = (2^(n\2)*(n\2)!)); if (n%2, n!/x, x);

%o a(n) = 2^(2*n+1)*factorial2(3*n)/((n+2)!*factorial2(n));

%o vector(20, i, a(i-1))

%o \\ test: y = Ser(vector(201, n, a(n-1))); x*(1-432*x^2)*y' == 64*x^2*y^2 + (288*x^2 - 64*x - 1)*y + 72*x + 1

%o \\ _Gheorghe Coserea_, Jun 13 2017

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

%Y Column k=0 of A266240.

%Y Cf. A000217, A358367.

%K nonn

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Sean A. Irvine_, May 19 2013