cp's OEIS Frontend

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

%I A000139 M1660 N0651 #272 Aug 20 2025 16:19:39
%S A000139 2,1,2,6,22,91,408,1938,9614,49335,260130,1402440,7702632,42975796,
%T A000139 243035536,1390594458,8038677054,46892282815,275750636070,
%U A000139 1633292229030,9737153323590,58392041019795,352044769046880,2132866978427640,12980019040145352,79319075627675556
%N A000139 a(n) = 2*(3*n)! / ((2*n+1)!*(n+1)!).
%C A000139 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 A000139 The number of 2-stack sortable permutations on n letters (n >= 1).
%C A000139 The number of rooted non-separable planar maps with n+1 edges. - _Valery A. Liskovets_, Mar 17 2005
%C A000139 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 A000139 Number of left ternary trees having n nodes (n>=1). - _Emeric Deutsch_, Jul 23 2006
%C A000139 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 A000139 Number of canopy intervals in the Tamari lattices, see [Préville-Ratelle and Viennot, section 6]. - _F. Chapoton_, Apr 19 2015
%C A000139 The number of fighting fish (branching polyominoes). - _David Bevan_, Jan 10 2018
%C A000139 The number of 1324-avoiding dominoes (gridded permutations). - _David Bevan_, Jan 10 2018
%C A000139 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
%C A000139 Conjecture: a(n) is odd iff n is a term of A022341. - _Peter Bala_, Jul 24 2025
%D A000139 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 365.
%D A000139 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 A000139 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.
%D A000139 S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. See p. 399 Table A.7
%D A000139 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 A000139 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000139 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000139 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.41.
%H A000139 T. D. Noe, <a href="/A000139/b000139.txt">Table of n, a(n) for n = 0..200</a>
%H A000139 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 A000139 E. Ben-Naim and P. L. Krapivsky, <a href="https://arxiv.org/abs/1112.0049">Popularity-Driven Networking</a>, arXiv preprint arXiv:1112.0049 [cond-mat.stat-mech], 2011.
%H A000139 Alin Bostan, Frédéric Chyzak, Bérénice Delcroix-Oger, Guillaume Laplante-Anfossi, Vincent Pilaud, and Kurt Stoeckl, <a href="https://mathexp.eu/bostan/diagonalsFPSAC25.pdf">Diagonals of permutahedra and associahedra</a>, Sém. Lotharingien Comb., 37th Formal Power Series Alg. Comb. (FPSAC 2025). See pp. 10-11.
%H A000139 David Bevan, Robert Brignall, Andrew Elvey Price and Jay Pantone, <a href="https://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 A000139 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 A000139 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 A000139 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 A000139 W. G. Brown, <a href="https://dx.doi.org/10.4153/CJM-1963-056-7">Enumeration of non-separable planar maps</a>, Canad. J. Math., 15 (1963), 526-545.
%H A000139 Colin Defant, <a href="https://arxiv.org/abs/1903.09138">Counting 3-Stack-Sortable Permutations</a>, arXiv:1903.09138 [math.CO], 2019.
%H A000139 A. Del Lungo, F. Del Ristoro and J.-G. Penaud, <a href="https://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 A000139 E. Duchi, V. Guerrini, S. Rinaldi and G. Schaeffer, <a href="https://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 A000139 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 A000139 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 A000139 S. Dulucq, S. Gire, and O. Guibert, <a href="https://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 A000139 S. Dulucq, S. Gire, and J. West, <a href="https://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 A000139 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 A000139 W. Fang, <a href="https://arxiv.org/abs/1711.05713">Fighting fish and two-stack sortable permutations</a>, arXiv preprint arXiv:1711.05713 [math.CO], 2017.
%H A000139 P. Flajolet and R. Sedgewick, <a href="https://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 713
%H A000139 I. Gessel and G. Xin, <a href="https://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 A000139 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 A000139 O. Guibert, <a href="https://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 A000139 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 A000139 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 A000139 S. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, <a href="https://staff.ru.is/henningu/papers/maps/maps.pdf">Restricted non-separable planar maps and some pattern avoiding permutations</a>, 2012.
%H A000139 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 A000139 Sergey Kitaev, Anna de Mier, and Marc Noy, <a href="https://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 A000139 Sergey Kitaev, Pavel Salimov, Christopher Severs, and Henning Ulfarsson, <a href="https://arxiv.org/abs/1202.1790">Restricted non-separable planar maps and some pattern avoiding permutations</a>, arXiv preprint arXiv:1202.1790 [math.CO], 2012. [Original title: Restricted rooted non-separable planar maps]
%H A000139 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 A000139 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 A000139 Permutation Pattern Avoidance Library (PermPAL), <a href="https://permpal.com/perms/name/1324_domino/">1324 Domino</a>
%H A000139 L.-F. Préville-Ratelle and X. Viennot, <a href="https://arxiv.org/abs/1406.3787">An extension of Tamari lattices</a>, arXiv preprint arXiv:1406.3787 [math.CO], 2014.
%H A000139 G. Schaeffer, <a href="https://www.lix.polytechnique.fr/~schaeffe/Biblio/Sc03.ps">A combinatorial interpretation of super-Catalan numbers of order two</a>, (2001).
%H A000139 W. T. Tutte, <a href="https://dx.doi.org/10.4153/CJM-1963-029-x">A Census of Planar Maps</a>, Canad. J. Math. 15 (1963), 249-271.
%H A000139 J. West, <a href="https://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 A000139 D. Zeilberger, <a href="https://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 A000139 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 A000139 P. Zinn-Justin and J.-B. Zuber, <a href="https://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 A000139 a(n) = 2*binomial(3*n, 2*n+1)/(n*(n+1)), or 2*(3*n)!/((2*n+1)!*((n+1)!)).
%F A000139 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 A000139 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 A000139 G.f.: (2/(3*x)) * (hypergeom([-2/3, -1/3],[1/2],(27/4)*x)-1). - _Mark van Hoeij_, Nov 02 2009
%F A000139 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 A000139 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 A000139 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 A000139 a(n) = A007318(3*n, 2*n+1)/A000217(n) for n > 0. - _Reinhard Zumkeller_, Feb 17 2013
%F A000139 a(n) is the n-th Hausdorff moment of the positive function w(x) defined on (0,27) which is equal 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 Integral_{x=0..27/4} x^n*w(x) dx, n >= 0. The function w(x) is unique. - _Karol A. Penson_, Jun 17 2013
%F A000139 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 A000139 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 A000139 From _Ilya Gutkovskiy_, Jan 17 2017: (Start)
%F A000139 E.g.f.: 2*2F2(1/3,2/3; 3/2,2; 27*x/4).
%F A000139 Sum_{n>=0} 1/a(n) = (1/2)*3F2(1,3/2,2; 1/3,2/3; 4/27) = 2.226206199291261... (End)
%F A000139 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 A000139 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 A000139 a(n) = 4*(3*n)!/(n!*(2*n+2)!). - _Chai Wah Wu_, Dec 15 2021
%F A000139 From _Peter Bala_, Feb 05 2022: (Start)
%F A000139 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 A000139 (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 A000139 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 A000139 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 A000139 G.f. = 2 + x + 2*x^2 + 6*x^3 + 22*x^4 + 91*x^5 + 408*x^6 + 1938*x^7 + ...
%p A000139 A000139 := n->2*(3*n)!/((2*n+1)!*((n+1)!)): seq(A000139(n), n=0..23);
%t A000139 Table[(2(3n)!)/((2n+1)!(n+1)!),{n,0,30}] (* _Harvey P. Dale_, Mar 31 2013 *)
%o A000139 (Haskell)
%o A000139 a000139 0 = 2
%o A000139 a000139 n = ((3 * n) `a007318` (2 * n + 1)) `div` a000217 n
%o A000139 -- _Reinhard Zumkeller_, Feb 17 2013
%o A000139 (Python)
%o A000139 from sympy import binomial
%o A000139 def A000139(n): return (binomial(3*n, n)*2)//((n+1)*(2*n+1))
%o A000139 (Python)
%o A000139 A000139_list = [2]
%o A000139 for n in range(1,30):
%o A000139     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
%o A000139 (Sage)
%o A000139 def A000139(n): return (binomial(3*n, n)*2)//((n+1)*(2*n+1))
%o A000139 [A000139(n) for n in (0..23)]  # _Peter Luschny_, Jun 17 2013
%o A000139 (PARI) a(n)=binomial(3*n,n)*2/((n+1)*(2*n+1)); \\ _Joerg Arndt_, Jul 21 2014
%o A000139 (Magma) [2*Factorial(3*n)/(Factorial(2*n+1)*Factorial(n+1)): n in [0..25]]; // _Vincenzo Librandi_, Apr 20 2015
%Y A000139 Cf. A000142, A000309, A001764, A005802, A006335, A004677, A121545, A218473, A233389.
%Y A000139 Row m=1 of A210664(n>0).
%K A000139 nonn,easy,nice
%O A000139 0,1
%A A000139 _N. J. A. Sloane_, entry revised Apr 24 2012