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

1, 1, 4, 24, 176, 1456, 13056, 124032, 1230592, 12629760, 133186560, 1436098560, 15774990336, 176028860416, 1990947110912, 22783499599872, 263411369705472, 3073132646563840, 36143187370967040, 428157758086840320, 5105072641718353920, 61228492804372561920

Offset: 0

Author

N. J. A. Sloane and Robert G. Wilson v

Keywords

• nonn
• nice

Comments

Also counts rooted planar non-separable triangulations with 3n edges. - Valery A. Liskovets, Dec 01 2003

Equivalently, rooted planar loopless triangulations with 2n triangles. - Noam Zeilberger, Oct 06 2016

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

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

References

• 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.
• 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

• T. D. Noe, Table of n, a(n) for n = 0..100
• Marie Albenque, Dominique Poulalhon, A Generic Method for Bijections between Blossoming Trees and Planar Maps, Electron. J. Combin., 22 (2015), #P2.38.
• Dario Benedetti, Sylvain Carrozza, Reiko Toriumi, Guillaume Valette, Multiple scaling limits of U(N)^2 X O(D) multi-matrix models, arXiv:2003.02100 [math-ph], 2020.
• Olivier Bernardi, Bijective counting of Kreweras walks and loopless triangulations, Journal of Combinatorial Theory, Series A 114:5 (2007), 931-956.
• Junliang Cai, Yanpei Liu, The enumeration of rooted nonseparable nearly cubic maps, Discrete Math. 207 (1999), no. 1-3, 9--24. MR1710479 (2000g:05074). See (31).
• Robert Cori and Gilles Schaeffer, Description trees and Tutte formulas, Theoretical Computer Science 292:1 (2003), 165-183.
• S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter permutations, Disc. Math. 157 (1996), 91-106.
• 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. (Annotated scanned copy)
• Hsien-Kuei Hwang, Mihyun Kang, 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.
• R. C. Mullin, On counting rooted triangular maps, Canad. J. Math., v.17 (1965), 373-382.
• Elena Patyukova, Taylor Rottreau, Robert Evans, Paul D. Topham, Martin J. Greenall, Hydrogen Bonding Aggregation in Acrylamide: Theory and Experiment, Macromolecules (2018) Vol. 51, No. 18, 7032-7043. Also arXiv:1805.09878 [math.CA], 2018.
• W. T. Tutte, A census of Hamiltonian polygons, Canad. J. Math., 14 (1962), 402-417.
• W. T. Tutte, On the enumeration of four-colored maps, SIAM J. Appl. Math., 17 (1969), 454-460.
• 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:1803.10080 [math.LO], 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.
• Jian Zhou, Fat and Thin Emergent Geometries of Hermitian One-Matrix Models, arXiv:1810.03883 [math-ph], 2018.

Crossrefs

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

Cf. A000139, A000264, A000356, A002005, A006335, A358091.

Programs

GAP

List([0..20], n -> 2^(n+1)*Factorial(3*n)/(Factorial(n)* Factorial(2*n+2))); # G. C. Greubel, Nov 29 2018

Magma

[2^(n+1)*Factorial(3*n)/(Factorial(n)*Factorial(2*n+2)): n in [0..20]]; // Vincenzo Librandi, Aug 10 2014

Maple

a := n -> 2^(n+1)*(3*n)!/(n!*(2*n+2)!);
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

Mathematica

f[n_] := 2^n(3n)!/((n + 1)!(2n + 1)!); Table[f[n], {n, 0, 19}] (* Robert G. Wilson v, Sep 21 2004 *)
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 *)

PARI

a(n) = 2^(n+1)*(3*n)!/(n!*(2*n+2)!); \\ Michel Marcus, Aug 09 2014

Sage

[2^n*factorial(3*n)/(factorial(n+1)*factorial(2*n+1))for n in range(20)] # G. C. Greubel Nov 29 2018

Formula

a(n) = 2^(n-1) * A000139(n) for n > 0.

a(n) = 4*a(n-1)*binomial(3*n, 3) / binomial(2*n+2, 3).

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

G.f.: (1/(6*x)) * (hypergeom([ -2/3, -1/3],[1/2],(27/2)*x)-1). - Mark van Hoeij, Nov 02 2009

a(n) ~ 3^(3*n+1/2)/(sqrt(Pi)*2^(n+2)*n^(5/2)). - Ilya Gutkovskiy, Oct 06 2016

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

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

From Karol A. Penson, Feb 24 2025: (Start)

G.f.: hypergeom([1/3, 2/3, 1], [3/2, 2], (27*z)/2).

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.

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.

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)).

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)

Extensions

Definition clarified by Michael Albert, Oct 24 2008