A000260 Number of rooted simplicial 3-polytopes with n+3 nodes; or rooted 3-connected triangulations with 2n+2 faces; or rooted 3-connected trivalent maps with 2n+2 vertices. (Formerly M2946 N1187)

1, 1, 3, 13, 68, 399, 2530, 16965, 118668, 857956, 6369883, 48336171, 373537388, 2931682810, 23317105140, 187606350645, 1524813969276, 12504654858828, 103367824774012, 860593023907540, 7211115497448720, 60776550501588855

Offset

0,3

Comments

Number of rooted loopless planar maps with n edges. E.g., there are a(2)=3 loopless planar maps with 2 edges: two rooted paths (.-.-.) and one digon (.=.). - Valery A. Liskovets, Sep 25 2003

Number of intervals (i.e., ordered pairs (x,y) such that x<=y) in the Tamari lattice (rotation lattice of binary trees) of size n (see Pallo and Chapoton references). - Ralf Stephan, May 08 2007, Jean Pallo (Jean.Pallo(AT)u-bourgogne.fr), Sep 11 2007

Number of rooted triangulations of type [n, 0] (see Brown paper eq (4.8)). - Michel Marcus, Jun 23 2013

Equivalently, number of rooted bridgeless planar maps with n edges. - Noam Zeilberger, Oct 06 2016

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

Number of uniquely sorted permutations of [2n+1] that avoid the pattern 231. Also the number of uniquely sorted permutations of [2n+1] that avoid 132. - Colin Defant, Jun 13 2019

The sequence 1,3,13,68,... appears naturally in integral geometry, namely in the algebra of unitarily invariant valuations on complex space forms. - Andreas Bernig, Feb 02 2020

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.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.

Handbook of Combinatorics, North-Holland '95, p. 891.

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

W. T. Tutte, The enumerative theory of planar maps, in A Survey of Combinatorial Theory (J. N. Srivastava et al. eds.), pp. 437-448, North-Holland, Amsterdam, 1973.

Links

T. D. Noe, Table of n, a(n) for n = 0..200

E. A. Bender and N. C. Wormald, The number of loopless planar maps, Discr. Math. 54:2 (1985), 235-237.

Andreas Bernig, Unitarily invariant valuations and Tutte's sequence, arXiv:2001.03372 [math.DG], 2020.

Alin Bostan, Frédéric Chyzak, and Vincent Pilaud, Refined product formulas for Tamari intervals, arXiv:2303.10986 [math.CO], 2023.

T. Daniel Brennan, Christian Ferko, and Savdeep Sethi, A Non-Abelian Analogue of DBI from $T \overline{T}$, arXiv:1912.12389 [hep-th], 2019. See also SciPost Phys. (2020) Vol. 8, 052.

Enrica Duchi and Corentin Henriet, A bijection between Tamari intervals and extended fighting fish, arXiv:2206.04375 [math.CO], 2022.

William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.

F. Chapoton, Sur le nombre d'intervalles dans les treillis de Tamari, arXiv:math/0602368 [math.CO], 2006.

Grégory Chatel, Vincent Pilaud, and Viviane Pons, The weak order on integer posets, arXiv:1701.07995 [math.CO], 2017.

G. Chatel and V. Pons, Counting smaller elements in the Tamari and m-Tamari lattices, arXiv preprint arXiv:1311.3922 [math.CO], 2013.

F. David, A model of random surfaces with nontrivial critical behavior, Nuclear Physics B, v. 257 (1985), 543-576.

Colin Defant, Catalan Intervals and Uniquely Sorted Permutations, arXiv:1904.02627 [math.CO], 2019.

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)

Wenjie Fang, Planar triangulations, bridgeless planar maps and Tamari intervals, arXiv:1611.07922 [math.CO], 2016.

Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.

C. Germain and J. Pallo, The number of coverings in four Catalan lattices, Intern. J. Computer Math., Vol. 61 (1996) pp. 19-28. (See p. 27.)

Hsien-Kuei Hwang, Mihyun Kang, and 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.

Z. Li and Y. Liu, Chromatic sums of general maps on the sphere and the projective plane, Discr. Math. 307 (2007), 78-87.

Michaël Moortgat, The Tamari order for D^3 and derivability in semi-associative Lambek-Grishin Calculus, 15th Workshop: Computational Logic and Applications (CLA 2020).

K. A. Penson, K. Górska, A. Horzela, and G. H. E. Duchamp, Hausdorff moment problem for combinatorial numbers of Brown and Tutte: exact solution, arXiv:2209.06574 [math.CO], 2022.

Viviane Pons, Combinatorics of the Permutahedra, Associahedra, and Friends, arXiv:2310.12687 [math.CO], 2023. See p. 37.

W. T. Tutte, A census of Hamiltonian polygons, Canad. J. Math., 14 (1962), 402-417.

William T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38. See Eq. 5.12.

William T. Tutte, On the enumeration of convex polyhedra, J. Combin. Theory Ser. B 28 (1980), no. 2, 105--126. MR0572468 (81j:05073).

T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259, eq. (6).

Noam Zeilberger, A sequent calculus for the Tamari order, arXiv:1701.02917 [cs.LO], 2017.

Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv preprint 1803.10030 [math.LO], 2018-2019 (A revised version of a 2017 conference paper).

Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018.

Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Rutgers Experimental Math Seminar, Sep 13 2018. See also Part 2.

Formula

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

G.f.: (2-g)*g^2 where g = 1 + x*g^4 is the g.f. of A002293. - Mark van Hoeij, Nov 10 2011

G.f.: hypergeom([1,1/2,3/4,5/4],[2,4/3,5/3],256*x/27) = 1 + 120*x/(Q(0)-120*x); Q(k) = 8*x*(2*k+1)*(4*k+3)*(4*k+5) + 3*(k+2)*(3*k+4)*(3*k+5) - 24*x*(k+2)*(2*k+3)*(3*k+4)*(3*k+5)*(4*k+7)*(4*k+9)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2011

a(n) = binomial(4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2)). - Michael Somos, Mar 28 2012

a(n) * (n+1) = A069271(n). - Michael Somos, Mar 28 2012

0 = F(a(n), a(n+1), ..., a(n+8)) for all n in Z where a(-1) = 3/4 and F() is a polynomial of degree 2 with integer coefficients and 29 monomials. - Michael Somos, Dec 23 2014

D-finite with recurrence: 3*(3*n+2)*(3*n+1)*(n+1)*a(n) - 8*(4*n+1)*(2*n-1)*(4*n-1)*a(n-1) = 0. - R. J. Mathar, Oct 21 2015

a(n) = Sum_{k=1..A000108(n)} k * A263191(n,k). - Alois P. Heinz, Nov 16 2015

a(n) ~ 2^(8*n+7/2) / (sqrt(Pi) * n^(5/2) * 3^(3*n+5/2)). - Vaclav Kotesovec, Feb 26 2016

E.g.f.: 3F3(1/2,3/4,5/4; 4/3,5/3,2; 256*x/27). - Ilya Gutkovskiy, Feb 01 2017

From Gheorghe Coserea, Aug 17 2017: (Start)

G.f. y(x) satisfies:

0 = x^3*y^4 + 3*x^2*y^3 + x*(8*x+3)*y^2 - (20*x-1)*y + 16*x-1.

0 = x*(256*x - 27)*deriv(y,x) - 8*x^2*y^3 - 25*x*y^2 + 4*(24*x-11)*y + 44.

(End)

From Karol A. Penson, Apr 06 2022: (Start)

a(n) = Integral_{x=0...256/27} x^n*W(x), where

W(x) = (sqrt(2)/Pi)*(h1(x) - h2(x) + h3(x)) and

h1(x) = 3F2([-6/12,-2/12, 2/12], [ 3/12, 9/12], (27*x)/256)/((x/2)^(1/2));

h2(x) = 3F2([-3/12, 1/12, 5/12], [ 6/12, 15/12], (27*x)/256)/(x^(1/4));

h3(x) = 3F2([ 3/12, 7/12, 11/12], [18/12, 21/12], (27*x)/256)/(x^(-1/4)*32).

This integral representation is unique as the solution of n-th Hausdorff power moment of the function W. Using only the definition of a(n), W(x) can be proven to be positive. W(x) is singular at x = 0 and for x > 0 is monotonically decreasing to zero at x = 256/27. (End)

a(n) = (1/27^n) * Product_{1 <= i <= j <= 3*n} (3*i + j + 3)/(3*i + j - 1). Cf. A006013. - Peter Bala, Feb 21 2023

Example

G.f. = 1 + x + 3*x^2 + 13*x^3 + 68*x^4 + 399*x^5 + 2530*x^6 + 16965*x^7 + ...

Maple

A000260 := proc(n)
    2*(4*n+1)!/((n+1)!*(3*n+2)!) ;
end proc:

Mathematica

Table[Binomial[4n+1, n+1]-9*Binomial[4n+1, n-1], {n, 0, 25}] (* Harvey P. Dale, Aug 23 2011 *)
a[ n_] := SeriesCoefficient[ HypergeometricPFQ[ {1/2, 3/4, 1, 5/4}, {4/3, 5/3, 2}, 256/27 x], {x, 0, n}]; (* Michael Somos, Dec 23 2014 *)
terms = 22; G[_] = 0; Do[G[x_] = 1+x*G[x]^4 + O[x]^terms, terms];
CoefficientList[(2-G[x])*G[x]^2, x] (* Jean-François Alcover, Jan 13 2018, after Mark van Hoeij *)

Prog

(PARI) {a(n) = if( n<0, 0, 2 * (4*n + 1)! / ((n + 1)! * (3*n + 2)!))}; /* Michael Somos, Sep 07 2005 */
(PARI) {a(n) = binomial( 4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2))}; /* Michael Somos, Mar 28 2012 */
(Sage)
def a(n):
    n = ZZ(n)
    return (4*n + 2).binomial(n + 1) // ((2*n + 1) * (3*n + 2))
# F. Chapoton, Aug 06 2015
(Magma) [Binomial(4*n+1, n+1)-9*Binomial(4*n+1, n-1): n in [0..25]]; // Vincenzo Librandi, Nov 24 2016

Crossrefs

Row sums of A342981.

Column 0 of A146305 and A341856; Column 2 of A255918.

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

Cf. A000256, A006013, A027836, A069271, A263191, A290326.

Sequence in context: A054132 A047149 A200757 * A192737 A125279 A186371

Adjacent sequences: A000257 A000258 A000259 * A000261 A000262 A000263

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

Edited by F. Chapoton, Feb 03 2011

Status

approved