|
%I M3601 N1460 #103 Oct 28 2022 14:23:28
%S 1,1,4,24,176,1456,13056,124032,1230592,12629760,133186560,1436098560,
%T 15774990336,176028860416,1990947110912,22783499599872,
%U 263411369705472,3073132646563840,36143187370967040,428157758086840320,5105072641718353920,61228492804372561920
%N Number of rooted planar bridgeless cubic maps with 2n nodes.
%C Also counts rooted planar non-separable triangulations with 3n edges. - _Valery A. Liskovets_, Dec 01 2003
%C Equivalently, rooted planar loopless triangulations with 2n triangles. - _Noam Zeilberger_, Oct 06 2016
%C Description trees of type (2,2) with n edges. (A description tree of type (a,b) is a rooted plane tree where every internal node is labeled by an integer between a and [b + sum of labels of its children], every leaf is labeled a, and the root is labeled [b + sum of labels of its children]. See Definition 1 and Section 5.2 of Cori and Schaeffer 2003.) - _Noam Zeilberger_, Oct 08 2017
%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 C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979.
%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 T. D. Noe, <a href="/A000309/b000309.txt">Table of n, a(n) for n = 0..100</a>
%H Marie Albenque, Dominique Poulalhon, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p38">A Generic Method for Bijections between Blossoming Trees and Planar Maps</a>, Electron. J. Combin., 22 (2015), #P2.38.
%H Dario Benedetti, Sylvain Carrozza, Reiko Toriumi, Guillaume Valette, <a href="https://arxiv.org/abs/2003.02100">Multiple scaling limits of U(N)^2 X O(D) multi-matrix models</a>, arXiv:2003.02100 [math-ph], 2020.
%H Olivier Bernardi, <a href="https://hal.archives-ouvertes.fr/hal-00068433/document">Bijective counting of Kreweras walks and loopless triangulations</a>, Journal of Combinatorial Theory, Series A 114:5 (2007), 931-956.
%H Junliang Cai, Yanpei Liu, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00129-6">The enumeration of rooted nonseparable nearly cubic maps</a>, Discrete Math. 207 (1999), no. 1-3, 9--24. MR1710479 (2000g:05074). See (31).
%H Robert Cori and Gilles Schaeffer, <a href="https://doi.org/10.1016/S0304-3975(01)00221-3">Description trees and Tutte formulas</a>, Theoretical Computer Science 292:1 (2003), 165-183.
%H S. Dulucq and O. Guibert, <a href="http://dx.doi.org/10.1016/S0012-365X(96)83009-3">Stack words, standard tableaux and Baxter permutations</a>, Disc. Math. 157 (1996), 91-106.
%H C. F. Earl and L. J. March, <a href="/A005500/a005500_1.pdf">Architectural applications of graph theory</a>, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979. (Annotated scanned copy)
%H Hsien-Kuei Hwang, Mihyun Kang, 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 R. C. Mullin, <a href="http://dx.doi.org/10.4153/CJM-1965-038-x">On counting rooted triangular maps</a>, Canad. J. Math., v.17 (1965), 373-382.
%H Elena Patyukova, Taylor Rottreau, Robert Evans, Paul D. Topham, Martin J. Greenall, <a href="https://www.doi.org/10.1021/acs.macromol.8b01118">Hydrogen Bonding Aggregation in Acrylamide: Theory and Experiment</a>, Macromolecules (2018) Vol. 51, No. 18, 7032-7043. Also <a href="https://arxiv.org/abs/1805.09878">arXiv:1805.09878</a> [math.CA], 2018.
%H W. T. Tutte, <a href="http://dx.doi.org/10.4153/CJM-1962-032-x">A census of Hamiltonian polygons</a>, Canad. J. Math., 14 (1962), 402-417.
%H W. T. Tutte, <a href="http://dx.doi.org/10.1137/0117044">On the enumeration of four-colored maps</a>, SIAM J. Appl. Math., 17 (1969), 454-460.
%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:1803.10080 [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^(n-1) * A000139(n) for n > 0.
%F a(n) = 4*a(n-1)*binomial(3*n, 3) / binomial(2*n+2, 3).
%F a(n) = 2^n*(3*n)!/ ( (n+1)!*(2*n+1)! ).
%F G.f.: (1/(6*x)) * (hypergeom([ -2/3, -1/3],[1/2],(27/2)*x)-1). - _Mark van Hoeij_, Nov 02 2009
%F a(n) ~ 3^(3*n+1/2)/(sqrt(Pi)*2^(n+2)*n^(5/2)). - _Ilya Gutkovskiy_, Oct 06 2016
%F D-finite with recurrence (n+1)*(2*n+1)*a(n) -3*(3*n-1)*(3*n-2)*a(n-1)=0. - _R. J. Mathar_, Nov 02 2018
%F a(n) = -(-2)^(n-1)*(3*n+2)*hypergeom([-3*(n+1),-n,-n+1/3], [-n-1,-n-2/3], 1). The a(n) are values of the polynomials A358091. - _Peter Luschny_, Oct 28 2022
%p a := n -> 2^(n+1)*(3*n)!/(n!*(2*n+2)!);
%p A000309 := n -> -(-2)^(n-1)*(3*n+2)*hypergeom([-3*(n+1),-n,-n+1/3], [-n-1,-n-2/3], 1): seq(simplify(A000309(n)), n = 0..21); # _Peter Luschny_, Oct 28 2022
%t f[n_] := 2^n(3n)!/((n + 1)!(2n + 1)!); Table[f[n], {n, 0, 19}] (* _Robert G. Wilson v_, Sep 21 2004 *)
%t Join[{1},RecurrenceTable[{a[1]==1,a[n]==4a[n-1] Binomial[3n,3]/ Binomial[2n+2,3]}, a[n],{n,20}]] (* _Harvey P. Dale_, May 11 2011 *)
%o (PARI) a(n) = 2^(n+1)*(3*n)!/(n!*(2*n+2)!); \\ _Michel Marcus_, Aug 09 2014
%o (Magma) [2^(n+1)*Factorial(3*n)/(Factorial(n)*Factorial(2*n+2)): n in [0..20]]; // _Vincenzo Librandi_, Aug 10 2014
%o (Sage) [2^n*factorial(3*n)/(factorial(n+1)*factorial(2*n+1))for n in range(20)] # _G. C. Greubel_ Nov 29 2018
%o (GAP) List([0..20], n -> 2^(n+1)*Factorial(3*n)/(Factorial(n)* Factorial(2*n+2))); # _G. C. Greubel_, Nov 29 2018
%Y Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
%Y Cf. A000139, A000264, A000356, A002005, A006335, A358091.
%K nonn,nice
%O 0,3
%A _N. J. A. Sloane_ and _Robert G. Wilson v_
%E Definition clarified by _Michael Albert_, Oct 24 2008
|
