A000139 - OEIS

%I M1660 N0651 #249 Apr 18 2024 10:46:21

%S 2,1,2,6,22,91,408,1938,9614,49335,260130,1402440,7702632,42975796,

%T 243035536,1390594458,8038677054,46892282815,275750636070,

%U 1633292229030,9737153323590,58392041019795,352044769046880,2132866978427640

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

%C This sequence arises in many different contexts, and over the years it has had several different definitions. I have now changed the definition back to one of the earlier ones, a self-contained formula. - _N. J. A. Sloane_, Apr 24 2012

%C The number of 2-stack sortable permutations on n letters (n >= 1).

%C The number of rooted non-separable planar maps with n+1 edges. - _Valery A. Liskovets_, Mar 17 2005

%C The shifted sequence starting with a(1): Number of quadrangular dissections of a square, counted by the number of vertices. Rooted, non-separable planar maps with no multiple edges, in which each non-root face has degree 4.

%C Number of left ternary trees having n nodes (n>=1). - _Emeric Deutsch_, Jul 23 2006

%C A combinatorial interpretation for this sequence in terms of a family of plane trees is given in [Schaeffer, Corollary 2 with k = 3]. - _Peter Bala_, Oct 12 2011

%C Number of canopy intervals in the Tamari lattices, see [Préville-Ratelle and Viennot, section 6]. - _F. Chapoton_, Apr 19 2015

%C The number of fighting fish (branching polyominoes). - _David Bevan_, Jan 10 2018

%C The number of 1324-avoiding dominoes (gridded permutations). - _David Bevan_, Jan 10 2018

%C For n > 0, a(n) is the number of simple strong triangulations of a fixed quadrilateral with n interior nodes. See A210664. - _Andrew Howroyd_, Feb 24 2021

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 365.

%D Eric S. Egge, Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics, pp. 65-82 of "A Century of Advancing Mathematics", ed. S. F. Kennedy et al., MAA Press 2015.

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

%D S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. See p. 399 Table A.7

%D W. F. Lunnon, Counting polyominoes, pp. 347-372 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.

%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 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.41.

%H T. D. Noe, <a href="/A000139/b000139.txt">Table of n, a(n) for n = 0..200</a>

%H A. M. Baxter, <a href="https://pdfs.semanticscholar.org/2c5d/79e361d3aecb25c380402144177ad7cd9dc8.pdf">Algorithms for Permutation Statistics</a>, Ph. D. Dissertation, Rutgers University, May 2011. See p. 15.

%H E. Ben-Naim and P. L. Krapivsky, <a href="http://arxiv.org/abs/1112.0049">Popularity-Driven Networking</a>, arXiv preprint arXiv:1112.0049 [cond-mat.stat-mech], 2011.

%H David Bevan, Robert Brignall, Andrew Elvey Price and Jay Pantone, <a href="http://arxiv.org/abs/1711.10325">A structural characterisation of Av(1324) and new bounds on its growth rate</a>, arXiv preprint arXiv:1711.10325 [math.CO], 2017.

%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.

%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 M. Bousquet-Mélou and A. Jehanne, <a href="https://arxiv.org/abs/math/0504018">Polynomial equations with one catalytic variable, algebraic series and map enumeration</a>, arXiv:math/0504018 [math.CO], 2005; J Comb. Thy. B 96 (2006), 623-672.

%H W. G. Brown, <a href="http://dx.doi.org/10.4153/CJM-1963-056-7">Enumeration of non-separable planar maps</a>, Canad. J. Math., 15 (1963), 526-545.

%H Colin Defant, <a href="https://arxiv.org/abs/1903.09138">Counting 3-Stack-Sortable Permutations</a>, arXiv:1903.09138 [math.CO], 2019.

%H A. Del Lungo, F. Del Ristoro and J.-G. Penaud, <a href="http://dx.doi.org/10.1016/S0304-3975(98)00025-5">Left ternary trees and non-separable rooted planar maps</a>, Theor. Comp. Sci., 233, 2000, 201-215.

%H E. Duchi, V. Guerrini, S. Rinaldi and G. Schaeffer, <a href="http://www.mat.univie.ac.at/~slc/s/43%20Duchi%20Guerrini%20Rinaldi%20Schaeffer.html">Fighting fish: enumerative properties</a>, Sém. Lothar. Combin. 78B (2017), Art. 43, 12 pp.

%H E. Duchi, V. Guerrini, S. Rinaldi, and G. Schaeffer, <a href="https://doi.org/10.1088/1751-8121/50/2/024002">Fighting fish</a>.  J. Phys. A, Math. Theor. 50, No. 2, Article ID 024002, 16 p. (2017).

%H Enrica Duchi and Corentin Henriet, <a href="https://arxiv.org/abs/2210.16635">A bijection between rooted planar maps and generalized fighting fish</a>, arXiv:2210.16635 [math.CO], 2022.

%H S. Dulucq, S. Gire, and O. Guibert, <a href="http://dx.doi.org/10.1016/S0012-365X(98)80005-8">A combinatorial proof of J. West's conjecture</a> Discrete Math. 187 (1998), no. 1-3, 71--96. MR1630680(99f:05053).

%H S. Dulucq, S. Gire, and J. West, <a href="http://dx.doi.org/10.1016/0012-365X(95)00130-O">Permutations with forbidden subsequences and nonseparable planar maps</a>, Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993). Discrete Math. 153 (1996), no. 1-3, 85-103. MR1394948 (98a:05081)

%H Eric S. Egge, <a href="/A000139/a000139.pdf">Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics</a>, MAA Focus, August/September 2015, pp. 33-34. [Annotated scanned copy]

%H W. Fang, <a href="http://arxiv.org/abs/1711.05713">Fighting fish and two-stack sortable permutations</a>, arXiv preprint arXiv:1711.05713 [math.CO], 2017.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 713

%H I. Gessel and G. Xin, <a href="http://www.combinatorics.org/Volume_13/Abstracts/v13i1r53.html">The generating function of ternary trees and continued fractions</a>, Electron. J Combin. 13 (2006), paper 53.

%H Juan B. Gil, Oscar A. Lopez, and Michael D. Weiner, <a href="https://arxiv.org/abs/2311.18227">A positional statistic for 1324-avoiding permutations</a>, arXiv:2311.18227 [math.CO], 2023.

%H O. Guibert, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00121-1">Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps</a>, Discr. Math., 210 (2000), 71-85.

%H Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.

%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 S. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, <a href="http://staff.ru.is/henningu/papers/maps/maps.pdf">Restricted non-separable planar maps and some pattern avoiding permutations</a>, 2012.

%H S. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, <a href="https://doi.org/10.1016/j.dam.2013.01.004">Restricted non-separable planar maps and some pattern avoiding permutations</a>, Discrete Applied Mathematics, Volume 161, Issues 16-17, November 2013, Pages 2514-2526.

%H Sergey Kitaev, Anna de Mier, and Marc Noy, <a href="http://dx.doi.org/10.1016/j.ejc.2013.06.013">On the number of self-dual rooted maps</a>, European J. Combin. 35 (2014), 377-387. MR3090510. See Theorem 1.

%H Sergey Kitaev, Pavel Salimov, Christopher Severs, and Henning Ulfarsson, <a href="http://arxiv.org/abs/1202.1790">Restricted rooted non-separable planar maps</a>, arXiv preprint arXiv:1202.1790 [math.CO], 2012.

%H Arturo Merino and Torsten Mütze, <a href="https://arxiv.org/abs/2103.09333">Combinatorial generation via permutation languages. III. Rectangulations</a>, arXiv:2103.09333 [math.CO], 2021.

%H Alois Panholzer, <a href="https://arxiv.org/abs/2007.14676">Parking function varieties for combinatorial tree models</a>, arXiv:2007.14676 [math.CO], 2020.

%H L.-F. Préville-Ratelle and X. Viennot, <a href="http://arxiv.org/abs/1406.3787">An extension of Tamari lattices</a>, arXiv preprint arXiv:1406.3787 [math.CO], 2014.

%H G. Schaeffer, <a href="http://www.lix.polytechnique.fr/~schaeffe/Biblio/Sc03.ps">A combinatorial interpretation of super-Catalan numbers of order two, (2001).

%H W. T. Tutte, <a href="http://dx.doi.org/10.4153/CJM-1963-029-x">A Census of Planar Maps</a>, Canad. J. Math. 15 (1963), 249-271.

%H J. West, <a href="http://dx.doi.org/10.1016/0304-3975(93)90321-J">Sorting twice through a stack</a>, Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991), Theoret. Comput. Sci. 117 (1993), no. 1-2, 303-313.

%H D. Zeilberger, <a href="http://dx.doi.org/10.1016/0012-365X(92)90351-F">A proof of Julian West's conjecture that the number of two-stacksortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!)</a>, Discrete Math., 102 (1992), 85-93.

%H P. Zinn-Justin and J.-B. Zuber, <a href="https://doi.org/10.1016/S0012-365X(01)00267-9">Matrix integrals and the counting of tangles and links</a>, Discrete Math 246 (2002), 343-360.

%H P. Zinn-Justin and J.-B. Zuber, <a href="http://arxiv.org/abs/math-ph/0303049">Matrix integrals and the generation and counting of virtual tangles and links</a>, arXiv:math-ph/0303049, 2003; J. Knot Theor. Ramifications 13 (2004) 325-356.

%F a(n) = 2*binomial(3*n, 2*n+1)/(n*(n+1)), or 2*(3*n)!/((2*n+1)!*((n+1)!)).

%F Using Stirling's formula in A000142 it is easy to get the asymptotic expression a(n) ~ (27/4)^n / (sqrt(Pi*n / 3) * (2*n + 1) * (n + 1)). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 13 2001

%F G.f.: A(z) = 2 + z*B(z), where B(z) = 1 - 8*z + 2*z*(5-6*z)*B - 2*z^2*(1+3*z)*B^2 - z^4*B^3.

%F G.f.: (2/(3*x)) * (hypergeom([-2/3, -1/3],[1/2],(27/4)*x)-1). - _Mark van Hoeij_, Nov 02 2009

%F G.f.: (2-3*R)/(R-1)^2 where R := RootOf(x-t*(t-1)^2,t) is an algebraic function in Maple notation. - _Mark van Hoeij_, Nov 08 2011

%F G.f.: 2*Q(0), where Q(k) = 1 + 3*x*(3*k+1)*(6*k+1)/(2*(k+1)*(4*k+3) - 6*x*(k+1)*(3*k+2)*(4*k+3)*(6*k+5)/(3*x*(3*k+2)*(6*k+5) + (2*k+3)*(4*k+5)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Apr 30 2013

%F E.g.f.: 2*Q(0), where Q(k) = 1 + 3*x*(3*k+1)*(6*k+1)/(2*(k+1)*(2*k+1)*(4*k+3) - 6*x*(k+1)*(2*k+1)*(3*k+2)*(4*k+3)*(6*k+5)/(3*x*(3*k+2)*(6*k+5) + (2*k+2)*(2*k+3)*(4*k+5)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Apr 30 2013

%F a(n) = A007318(3*n, 2*n+1)/A000217(n) for n > 0. - _Reinhard Zumkeller_, Feb 17 2013

%F a(n) is the n-th Hausdorff moment of the positive function w(x) defined on (0,27) which is equal (in Maple notation) to w(x) = 3*sqrt(3)*2^(2/3)*(3-sqrt(81-12*x)/9)*(1+sqrt(81-12*x)/9)^(1/3)/(8*Pi*x^(2/3))-sqrt(3)*2^(1/3)*(3+sqrt(81-12*x)/9)*(1+sqrt(81-12*x)/9)^(-1/3)/(4*Pi*x^(1/3)), that is, a(n) is the integral int(x^n * w(x), x=0..27/4), n=0,1,2,.... The function w(x) is unique. - _Karol A. Penson_, Jun 17 2013

%F D-finite with recurrence 2*(n+1)*(2*n+1)*a(n) -3*(3*n-1)*(3*n-2)*a(n-1)=0. - _R. J. Mathar_, Aug 21 2014

%F G.f. A(z) is related to the g.f. M(z) of A000168 by M(z) = 1 + A(z*M(z)^2) (see Tutte 1963, equation 6.3). - _Noam Zeilberger_, Nov 02 2016

%F From _Ilya Gutkovskiy_, Jan 17 2017: (Start)

%F E.g.f.: 2*2F2(1/3,2/3; 3/2,2; 27*x/4).

%F Sum_{n>=0} 1/a(n) = (1/2)*3F2(1,3/2,2; 1/3,2/3; 4/27) = 2.226206199291261... (End)

%F G.f. A(z) is the solution to the initial value problem 4*A + 2*z*A' = 8 + 3*z*A + 9*z^2*A' + 2*z^2*A*A', A(0) = 2. - _Bjarki Ágúst Guðmundsson_, Jul 03 2017

%F a(n+1) = a(n)*3*(3*n+1)*(3*n+2)/(2*(n+2)*(2*n+3)). - _Chai Wah Wu_, Apr 02 2021

%F a(n) = 4*(3*n)!/(n!*(2*n+2)!). - _Chai Wah Wu_, Dec 15 2021

%F From _Peter Bala, Feb 05 2022: (Start)

%F O.g.f.: A(x) = T(x)*(3 - T(x)), where T(x) = 1 + x*T(x)^3 is the o.g.f. of A001764.

%F (1/x)*(A(x) - 2)/(A(x) - 1) = 1 + x + 3*x^2 + 11*x^3 + 46*x^4 + 209*x^5 + ... is the o.g.f. of A233389.

%F 1 + 2*x*A'(2*x)/A(2*x) = 1 + x + 7*x^2 + 61*x^3 + 591*x^4 + 6101*x^6 + ... is the o.g.f. of A218473.

%F Let B(x) = 1 + x*(A(x) - 1). Then x*B'(x)/B(x) = x + x^2 + 4*x^3 + 17*x^4 + 81*x^5 + ... is the o.g.f. of A121545. (End)

%e G.f. = 2 + x + 2*x^2 + 6*x^3 + 22*x^4 + 91*x^5 + 408*x^6 + 1938*x^7 + ...

%p A000139 := n->2*(3*n)!/((2*n+1)!*((n+1)!)): seq(A000139(n), n=0..23);

%t Table[(2(3n)!)/((2n+1)!(n+1)!),{n,0,30}] (* _Harvey P. Dale_, Mar 31 2013 *)

%o (Haskell)

%o a000139 0 = 2

%o a000139 n = ((3 * n) `a007318` (2 * n + 1)) `div` a000217 n

%o -- _Reinhard Zumkeller_, Feb 17 2013

%o (Python)

%o from sympy import binomial

%o def A000139(n): return (binomial(3*n, n)*2)//((n+1)*(2*n+1))

%o (Sage)

%o def A000139(n): return (binomial(3*n, n)*2)//((n+1)*(2*n+1))

%o [A000139(n) for n in (0..23)]  # _Peter Luschny_, Jun 17 2013

%o (PARI) a(n)=binomial(3*n,n)*2/((n+1)*(2*n+1)); \\ _Joerg Arndt_, Jul 21 2014

%o (Magma) [2*Factorial(3*n)/(Factorial(2*n+1)*Factorial(n+1)): n in [0..25]]; // _Vincenzo Librandi_, Apr 20 2015

%o (Python)

%o A000139_list = [2]

%o for n in range(1,30):

%o     A000139_list.append(3*(3*n-2)*(3*n-1)*A000139_list[-1]//(2*n+2)//(2*n+1)) # _Chai Wah Wu_, Apr 02 2021

%Y Cf. A000142, A000309, A001764, A005802, A006335, A004677, A121545, A218473, A233389.

%Y Row m=1 of A210664(n>0).

%K nonn,easy,nice

%O 0,1

%A _N. J. A. Sloane_, entry revised Apr 24 2012