A000264 -id:A000264 - cp's OEIS frontend

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

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

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

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

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.

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

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

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

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

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

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

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

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

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)

Definition clarified by Michael Albert, Oct 24 2008

A000356 Number of rooted cubic maps with 2n nodes and a distinguished Hamiltonian cycle: (2n)!(2n+1)! / (n!^2*(n+1)!(n+2)!).

Original entry on oeis.org

1, 5, 35, 294, 2772, 28314, 306735, 3476330, 40831076, 493684828, 6114096716, 77266057400, 993420738000, 12964140630900, 171393565105575, 2291968851019650, 30961684478686500, 422056646314726500

Offset: 1

N. J. A. Sloane, Simon Plouffe

a(2n-1) is also the sum of the numbers of standard Young tableaux of size 2n+1 and of shapes (k+3,k+2,2^{n-2-k}), 0 <= k <= n-2. - Amitai Regev (amitai.regev(AT)weizmann.ac.il), Mar 10 2010

Amitai Regev, Preprint. [From Amitai Regev (amitai.regev(AT)weizmann.ac.il), Mar 10 2010]
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).

Vincenzo Librandi, Table of n, a(n) for n = 1..800
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
Anatol N. Kirillov, Notes on Schubert, Grothendieck and key polynomials, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 034, 56 p. (2016).
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.

Cf. A000264, A000309.
Equals A005568/2.
Fourth row of array A102539.
Column of array A073165.
Image of A001700 under the "little Hankel" transform (see A056220 for definition). - John W. Layman, Aug 22 2000
Cf. A000891.

A000356 := proc(n)
    binomial(2*n,n)*binomial(2*n+1,n+1)/(n+1)/(n+2) ;
end proc:

CoefficientList[ Series[1 + (HypergeometricPFQ[{1, 3/2, 5/2}, {3, 4}, 16 x] - 1), {x, 0, 17}], x]
Table[(2*n)!*(2*n+2)!/(2*n!*(n+1)!^2*(n+2)!),{n,30}] (* Vincenzo Librandi, Mar 25 2012 *)

G.f.: (with offset 0) 3F2( [1, 3/2, 5/2], [3, 4], 16*x) = (1 - 2*x - 2F1( [-1/2, 1/2], [2], 16*x) ) / (4*x^2). - Olivier Gérard, Feb 16 2011
a(n)*(n+2) = A000891(n). - Gary W. Adamson, Apr 08 2011
D-finite with recurrence (n+2)*(n+1)*a(n)-4*(2*n-1)*(2*n+1)*a(n-1)=0. - R. J. Mathar, Mar 03 2013
From Ilya Gutkovskiy, Feb 01 2017: (Start)
E.g.f.: (1/2)*(2F2(1/2,3/2; 2,3; 16*x) - 1).
a(n) ~ 2^(4*n+1)/(Pi*n^3). (End)
From Peter Bala, Feb 22 2023: (Start)
a(n) = Product_{1 <= i <= j <= n-1} (i + j + 3)/(i + j - 1).
a(n) = (2^(n-1)) * Product_{1 <= i <= j <= n-1} (i + j + 3)/(i + j) for n >= 1.
 Cf. A003645. (End)

Better definition from Michael Albert, Oct 24 2008

A004304 Number of nonseparable planar tree-rooted maps with n edges.

Original entry on oeis.org

1, 2, 2, 6, 28, 160, 1036, 7294, 54548, 426960, 3463304, 28910816, 247104976, 2154192248, 19097610480, 171769942086, 1564484503044, 14407366963440, 133978878618904, 1256799271555872, 11881860129979440

Offset: 0

N. J. A. Sloane

nonn

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

Gheorghe Coserea, Table of n, a(n) for n = 0..200
Dov Tamari, Monoïdes préordonnés et chaînes de Malcev, Bulletin de la Société Mathématique de France, Volume 82 (1954), 53-96. See end of Appendix II.
T. R. S. Walsh, A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259. See Table IVc.

Cf. A000264.

Cf. A005568, A168450, A168451, A168452. - Paul D. Hanna, Nov 26 2009

A004304 := proc(n) local N,x,ode ; Order := n+1 ; ode := x^2*diff(N(x),x,x)*(N(x)^3-16*x*N(x)) ; ode := ode + (x*diff(N(x),x))^3*(16-6*N(x)) ; ode := ode + (x*diff(N(x),x))^2*(12*N(x)^2-16*x-24*N(x)) ; ode := ode + x*diff(N(x),x)*(-8*N(x)^3+24*x*N(x)+12*N(x)^2) ; ode := ode + 2*N(x)^2*(N(x)^2-N(x)-6*x) ; dsolve({ode=0,N(0)=1,D(N)(0)=2},N(x),type=series) ; convert(%,polynom) ; rhs(%) ; RETURN( coeftayl(%,x=0,n)) ; end; for n from 0 to 20 do printf("%d,",A004304(n)) ; od ; # R. J. Mathar, Aug 18 2006

m = 22;
F[x_] = Sum[2 (2n+1) Binomial[2n, n]^2 x^n/((n+2)(n+1)^2), {n, 0, m}];
A[x_] = (x/InverseSeries[x F[x]^2 + O[x]^m, x])^(1/2);
CoefficientList[A[x], x] (* Jean-François Alcover, Mar 28 2020 *)

{a(n)=local(C_2=vector(n+1,m,(binomial(2*m-2,m-1)/m)*(binomial(2*m,m)/(m+1))));polcoeff((x/serreverse(x*Ser(C_2)^2))^(1/2),n)} \\ Paul D. Hanna, Nov 26 2009

seq(N) = {
  my(c(n)=binomial(2*n,n)/(n+1), s=Ser(apply(n->c(n)*c(n+1), [0..N])));
  Vec(subst(s, 'x, serreverse('x*s^2)));
};
seq(20)
\\ test: y=Ser(seq(200)); 0 == x^2*y''*(y^3 - 16*x*y) + (x*y')^3*(16-6*y) + (x*y')^2*(12*y^2-16*x-24*y) + x*y'*(-8*y^3 + 24*x*y + 12*y^2) + 2*y^2*(y^2-y-6*x)
\\ Gheorghe Coserea, Jun 13 2018

From Paul D. Hanna, Nov 26 2009: (Start)
G.f.: A(x) = [x/Series_Reversion(x*F(x)^2)]^(1/2) where F(x) = g.f. of A005568, where A005568(n) is the product of two successive Catalan numbers C(n)*C(n+1).
G.f.: A(x) = F(x/A(x)^2) where A(x*F(x)^2) = F(x) where F(x) = g.f. of A005568.
G.f.: A(x) = G(x/A(x)) where A(x*G(x)) = G(x) where F(x) = g.f. of A168450.
G.f.: A(x) = x/Series_Reversion(x*G(x)) where G(x) = g.f. of A168450.
Self-convolution yields A168451.
(End)

More terms from R. J. Mathar, Aug 18 2006

A256330 Number of H&S Family matchings on n edges.

Original entry on oeis.org

1, 3, 14, 84, 592, 4659, 39699, 359004, 3399164, 33378417, 337584612, 3498553682, 37006524557, 398312230440, 4351822041763, 48169486233388, 539303075161814, 6099303431601708, 69604032964928589, 800737747350839332, 9279033826462097649, 108236883894562489628

Offset: 1

Aziza Jefferson, Mar 25 2015

nonn

The H&S Family of matchings is the family of matchings that can be drawn in the plane without crossings.
Jay Pantone has computed the first 1500 terms and has a conjectured g.f. - N. J. A. Sloane, Oct 06 2016
Consider the graph whose vertices are the arcs of a matching, where two vertices are connected if the corresponding arcs cannot be drawn on the same side without crossing. Matchings, where the graph obtained this way is connected, are in bijection with 3-edge-connected rooted cubic maps with 2n nodes and a distinguished Hamiltonian cycle (cf. A000264). - Ludovic Schwob, Jun 17 2025

			a(5)= 592; in canonical sequence form the two 3-noncrossing matchings it does not include are 1231435425 and 1234254153.

Ludovic Schwob, Table of n, a(n) for n = 1..200
Michael Albert and Mireille Bousquet-Mélou, Permutations sortable by two stacks in parallel and quarter plane walks, European Journal of Combinatorics 43 (2015): 131-164. Also arXiv:1312.4487 [math.CO], 2013-2014.
C. Haslinger and P. F. Stadler, RNA structures with pseudo-notes: Graph-theoretical, combinatorial, and statistical properties, Bulletin of Mathematical Biology 61 (1999), 437-467.
Aziza Jefferson, The Substitution Decomposition of Matchings and RNA Secondary Structures, PhD Thesis, University of Florida, 2015.
Jay Pantone, Approximate Asymptotic Analysis of Combinatorial Sequences, Experimental Math Seminar, Rutgers University, Oct 06 2016.

Cf. A000264.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A000356 Number of rooted cubic maps with 2n nodes and a distinguished Hamiltonian cycle: (2n)!(2n+1)! / (n!^2*(n+1)!(n+2)!).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A004304 Number of nonseparable planar tree-rooted maps with n edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A256330 Number of H&S Family matchings on n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs