The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000139 a(n) = 2*(3*n)!/((2*n+1)!*((n+1)!)).
(Formerly M1660 N0651)

%I M1660 N0651

%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 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

%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, Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.

%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 S. Dulucq, S. Gire, 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.0571">Fighting fish and two-stack sortable permutations</a>, arXiv preprint arXiv:1711.0571 [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 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, 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, 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, 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 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*C(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 easy to get the asymptotic expression a(n) ~ (27/4)^n / (sqrt(Pi*n / 3) * (2n + 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

%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 (Sage)

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

%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

%Y Cf. A000142, A000309, A005802, A006335, A004677.

%K nonn,easy,nice,changed

%O 0,1

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 13:40 EST 2020. Contains 332077 sequences. (Running on oeis4.)