cp's OEIS Frontend

A000309 Number of rooted planar bridgeless cubic maps with 2n nodes.

%I A000309 M3601 N1460 #114 Feb 25 2025 05:46:36
%S A000309 1,1,4,24,176,1456,13056,124032,1230592,12629760,133186560,1436098560,
%T A000309 15774990336,176028860416,1990947110912,22783499599872,
%U A000309 263411369705472,3073132646563840,36143187370967040,428157758086840320,5105072641718353920,61228492804372561920
%N A000309 Number of rooted planar bridgeless cubic maps with 2n nodes.
%C A000309 Also counts rooted planar non-separable triangulations with 3n edges. - _Valery A. Liskovets_, Dec 01 2003
%C A000309 Equivalently, rooted planar loopless triangulations with 2n triangles. - _Noam Zeilberger_, Oct 06 2016
%C A000309 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 A000309 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 A000309 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 A000309 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000309 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000309 T. D. Noe, <a href="/A000309/b000309.txt">Table of n, a(n) for n = 0..100</a>
%H A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 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 A000309 a(n) = 2^(n-1) * A000139(n) for n > 0.
%F A000309 a(n) = 4*a(n-1)*binomial(3*n, 3) / binomial(2*n+2, 3).
%F A000309 a(n) = 2^n*(3*n)!/ ( (n+1)!*(2*n+1)! ).
%F A000309 G.f.: (1/(6*x)) * (hypergeom([ -2/3, -1/3],[1/2],(27/2)*x)-1). - _Mark van Hoeij_, Nov 02 2009
%F A000309 a(n) ~ 3^(3*n+1/2)/(sqrt(Pi)*2^(n+2)*n^(5/2)). - _Ilya Gutkovskiy_, Oct 06 2016
%F A000309 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 A000309 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
%F A000309 From _Karol A. Penson_, Feb 24 2025: (Start)
%F A000309 G.f.: hypergeom([1/3, 2/3, 1], [3/2, 2], (27*z)/2).
%F A000309 G.f. A(z) satisfies: - 1 + 27*z + (-36*z + 1)*A(z) + 8*z*A(z)^2 + 16*z^2*A(z)^3 = 0.
%F A000309 G.f.: ((4*sqrt(4 - 54*z) + 12*i*sqrt(6)*sqrt(z))^(1/3)*(sqrt(z*(4 - 54*z)) - 9*i*sqrt(6)*z) + (4*sqrt(4 - 54*z) - 12*i*sqrt(6)*sqrt(z))^(1/3)*(9*i*sqrt(6)*z + sqrt(z*(4 - 54*z))) - 8*sqrt(z))/(48*z^(3/2)), where i = sqrt(-1) is the imaginary unit.
%F A000309 a(n) = Integral_{x=0..27/2} x^n*W(x), where W(x) = (6^(1/3)*(9 + sqrt(81 - 6*x))^(2/3)*(9*sqrt(3) - sqrt(27 - 2*x)) - 2^(2/3)*3^(1/6)*(27 + sqrt(81 - 6*x))*x^(1/3))/(48*Pi*(9 + sqrt(81 - 6*x))^(1/3)*x^(2/3)).
%F A000309 This integral representation is unique as W(x) is the solution of the Hausdorff power moment problem for x on (0, 27/2). Using only the definition of a(n), W(x) can be proven to be positive. W(x) is singular at x = 0, with singularity x^(-2/3), and for x > 0 is monotonically decreasing to zero at x = 27/2. (End)
%p A000309 a := n -> 2^(n+1)*(3*n)!/(n!*(2*n+2)!);
%p A000309 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 A000309 f[n_] := 2^n(3n)!/((n + 1)!(2n + 1)!); Table[f[n], {n, 0, 19}] (* _Robert G. Wilson v_, Sep 21 2004 *)
%t A000309 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 A000309 (PARI) a(n) = 2^(n+1)*(3*n)!/(n!*(2*n+2)!); \\ _Michel Marcus_, Aug 09 2014
%o A000309 (Magma) [2^(n+1)*Factorial(3*n)/(Factorial(n)*Factorial(2*n+2)): n in [0..20]]; // _Vincenzo Librandi_, Aug 10 2014
%o A000309 (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 A000309 (GAP) List([0..20], n -> 2^(n+1)*Factorial(3*n)/(Factorial(n)* Factorial(2*n+2))); # _G. C. Greubel_, Nov 29 2018
%Y A000309 Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
%Y A000309 Cf. A000139, A000264, A000356, A002005, A006335, A358091.
%K A000309 nonn,nice
%O A000309 0,3
%A A000309 _N. J. A. Sloane_ and _Robert G. Wilson v_
%E A000309 Definition clarified by _Michael Albert_, Oct 24 2008