|
%I M2946 N1187 #232 Oct 25 2023 09:31:10
%S 1,1,3,13,68,399,2530,16965,118668,857956,6369883,48336171,373537388,
%T 2931682810,23317105140,187606350645,1524813969276,12504654858828,
%U 103367824774012,860593023907540,7211115497448720,60776550501588855
%N 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.
%C 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
%C 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
%C Number of rooted triangulations of type [n, 0] (see Brown paper eq (4.8)). - _Michel Marcus_, Jun 23 2013
%C Equivalently, number of rooted bridgeless planar maps with n edges. - _Noam Zeilberger_, Oct 06 2016
%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
%C 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
%C 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
%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 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.
%D Handbook of Combinatorics, North-Holland '95, p. 891.
%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).
%D 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.
%H T. D. Noe, <a href="/A000260/b000260.txt">Table of n, a(n) for n = 0..200</a>
%H E. A. Bender and N. C. Wormald, <a href="http://dx.doi.org/10.1016/0012-365X(85)90084-6">The number of loopless planar maps</a>, Discr. Math. 54:2 (1985), 235-237.
%H Andreas Bernig, <a href="https://arxiv.org/abs/2001.03372">Unitarily invariant valuations and Tutte's sequence</a>, arXiv:2001.03372 [math.DG], 2020.
%H Alin Bostan, Frédéric Chyzak, and Vincent Pilaud, <a href="https://arxiv.org/abs/2303.10986">Refined product formulas for Tamari intervals</a>, arXiv:2303.10986 [math.CO], 2023.
%H T. Daniel Brennan, Christian Ferko, and Savdeep Sethi, <a href="https://arxiv.org/abs/1912.12389">A Non-Abelian Analogue of DBI from $T \overline{T}$</a>, arXiv:1912.12389 [hep-th], 2019. See also <a href="https://doi.org/10.21468/SciPostPhys.8.4.052">SciPost Phys.</a> (2020) Vol. 8, 052.
%H Enrica Duchi and Corentin Henriet, <a href="https://arxiv.org/abs/2206.04375">A bijection between Tamari intervals and extended fighting fish</a>, arXiv:2206.04375 [math.CO], 2022.
%H William G. Brown, <a href="http://dx.doi.org/10.1112/plms/s3-14.4.746">Enumeration of Triangulations of the Disk</a>, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.
%H F. Chapoton, <a href="https://arxiv.org/abs/math/0602368">Sur le nombre d'intervalles dans les treillis de Tamari</a>, arXiv:math/0602368 [math.CO], 2006.
%H Grégory Chatel, Vincent Pilaud, and Viviane Pons, <a href="https://arxiv.org/abs/1701.07995">The weak order on integer posets</a>, arXiv:1701.07995 [math.CO], 2017.
%H G. Chatel and V. Pons, <a href="http://arxiv.org/abs/1311.3922">Counting smaller elements in the Tamari and m-Tamari lattices</a>, arXiv preprint arXiv:1311.3922 [math.CO], 2013.
%H F. David, <a href="http://dx.doi.org/10.1016/0550-3213(85)90363-3">A model of random surfaces with nontrivial critical behavior</a>, Nuclear Physics B, v. 257 (1985), 543-576.
%H Colin Defant, <a href="https://arxiv.org/abs/1904.02627">Catalan Intervals and Uniquely Sorted Permutations</a>, arXiv:1904.02627 [math.CO], 2019.
%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 Wenjie Fang, <a href="https://arxiv.org/abs/1611.07922">Planar triangulations, bridgeless planar maps and Tamari intervals</a>, arXiv:1611.07922 [math.CO], 2016.
%H Joël Gay and Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.
%H C. Germain and J. Pallo, <a href="http://dx.doi.org/10.1080/00207169608804497">The number of coverings in four Catalan lattices</a>, Intern. J. Computer Math., Vol. 61 (1996) pp. 19-28. (See p. 27.)
%H Hsien-Kuei Hwang, Mihyun Kang, and 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 Z. Li and Y. Liu, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.039">Chromatic sums of general maps on the sphere and the projective plane</a>, Discr. Math. 307 (2007), 78-87.
%H Michaël Moortgat, <a href="https://cla.tcs.uj.edu.pl/history/2020/pdfs/CLA_Moortgat.pdf">The Tamari order for D^3 and derivability in semi-associative Lambek-Grishin Calculus</a>, 15th Workshop: Computational Logic and Applications (CLA 2020).
%H K. A. Penson, K. Górska, A. Horzela, and G. H. E. Duchamp, <a href="https://arxiv.org/abs/2209.06574">Hausdorff moment problem for combinatorial numbers of Brown and Tutte: exact solution</a>, arXiv:2209.06574 [math.CO], 2022.
%H Viviane Pons, <a href="https://arxiv.org/abs/2310.12687">Combinatorics of the Permutahedra, Associahedra, and Friends</a>, arXiv:2310.12687 [math.CO], 2023. See p. 37.
%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 William T. Tutte, <a href="http://dx.doi.org/10.4153/CJM-1962-002-9">A census of planar triangulations</a>, Canad. J. Math. 14 (1962), 21-38. See Eq. 5.12.
%H William T. Tutte, <a href="http://dx.doi.org/10.1016/0095-8956(80)90059-3">On the enumeration of convex polyhedra</a>, J. Combin. Theory Ser. B 28 (1980), no. 2, 105--126. MR0572468 (81j:05073).
%H T. R. S. Walsh and A. B. Lehman, <a href="http://dx.doi.org/10.1016/0095-8956(75)90050-7">Counting rooted maps by genus. III: Nonseparable maps</a>, J. Combinatorial Theory Ser. B 18 (1975), 222-259, eq. (6).
%H Noam Zeilberger, <a href="https://arxiv.org/abs/1701.02917">A sequent calculus for the Tamari order</a>, arXiv:1701.02917 [cs.LO], 2017.
%H Noam Zeilberger, <a href="https://arxiv.org/abs/1803.10080">A Sequent Calculus for a Semi-Associative Law</a>, arXiv preprint 1803.10030 [math.LO], 2018-2019 (A revised version of a 2017 conference paper).
%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://vimeo.com/289907363">A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video)</a>, Rutgers Experimental Math Seminar, Sep 13 2018. See also <a href="https://vimeo.com/289910554">Part 2</a>.
%F a(n) = 2*(4*n+1)! / ((n+1)!*(3*n+2)!) = binomial(4*n+1, n+1) - 9*binomial(4*n+1, n-1).
%F G.f.: (2-g)*g^2 where g = 1 + x*g^4 is the g.f. of A002293. - _Mark van Hoeij_, Nov 10 2011
%F 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
%F a(n) = binomial(4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2)). - _Michael Somos_, Mar 28 2012
%F a(n) * (n+1) = A069271(n). - _Michael Somos_, Mar 28 2012
%F 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
%F 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
%F a(n) = Sum_{k=1..A000108(n)} k * A263191(n,k). - _Alois P. Heinz_, Nov 16 2015
%F a(n) ~ 2^(8*n+7/2) / (sqrt(Pi) * n^(5/2) * 3^(3*n+5/2)). - _Vaclav Kotesovec_, Feb 26 2016
%F E.g.f.: 3F3(1/2,3/4,5/4; 4/3,5/3,2; 256*x/27). - _Ilya Gutkovskiy_, Feb 01 2017
%F From _Gheorghe Coserea_, Aug 17 2017: (Start)
%F G.f. y(x) satisfies:
%F 0 = x^3*y^4 + 3*x^2*y^3 + x*(8*x+3)*y^2 - (20*x-1)*y + 16*x-1.
%F 0 = x*(256*x - 27)*deriv(y,x) - 8*x^2*y^3 - 25*x*y^2 + 4*(24*x-11)*y + 44.
%F (End)
%F From _Karol A. Penson_, Apr 06 2022: (Start)
%F a(n) = Integral_{x=0...256/27} x^n*W(x), where
%F W(x) = (sqrt(2)/Pi)*(h1(x) - h2(x) + h3(x)) and
%F h1(x) = 3F2([-6/12,-2/12, 2/12], [ 3/12, 9/12], (27*x)/256)/((x/2)^(1/2));
%F h2(x) = 3F2([-3/12, 1/12, 5/12], [ 6/12, 15/12], (27*x)/256)/(x^(1/4));
%F h3(x) = 3F2([ 3/12, 7/12, 11/12], [18/12, 21/12], (27*x)/256)/(x^(-1/4)*32).
%F 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)
%F 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
%e G.f. = 1 + x + 3*x^2 + 13*x^3 + 68*x^4 + 399*x^5 + 2530*x^6 + 16965*x^7 + ...
%p A000260 := proc(n)
%p 2*(4*n+1)!/((n+1)!*(3*n+2)!) ;
%p end proc:
%t Table[Binomial[4n+1,n+1]-9*Binomial[4n+1,n-1],{n,0,25}] (* _Harvey P. Dale_, Aug 23 2011 *)
%t 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 *)
%t terms = 22; G[_] = 0; Do[G[x_] = 1+x*G[x]^4 + O[x]^terms, terms];
%t CoefficientList[(2-G[x])*G[x]^2, x] (* _Jean-François Alcover_, Jan 13 2018, after _Mark van Hoeij_ *)
%o (PARI) {a(n) = if( n<0, 0, 2 * (4*n + 1)! / ((n + 1)! * (3*n + 2)!))}; /* _Michael Somos_, Sep 07 2005 */
%o (PARI) {a(n) = binomial( 4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2))}; /* _Michael Somos_, Mar 28 2012 */
%o (Sage)
%o def a(n):
%o n = ZZ(n)
%o return (4*n + 2).binomial(n + 1) // ((2*n + 1) * (3*n + 2))
%o # _F. Chapoton_, Aug 06 2015
%o (Magma) [Binomial(4*n+1, n+1)-9*Binomial(4*n+1, n-1): n in [0..25]]; // _Vincenzo Librandi_, Nov 24 2016
%Y Row sums of A342981.
%Y Column 0 of A146305 and A341856; Column 2 of A255918.
%Y Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
%Y Cf. A000256, A006013, A027836, A069271, A263191, A290326.
%K nonn,nice,easy
%O 0,3
%A _N. J. A. Sloane_
%E Edited by _F. Chapoton_, Feb 03 2011
|
