login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000139 a(n) = 2*(3*n)!/((2*n+1)!*((n+1)!)).
(Formerly M1660 N0651)
17
2, 1, 2, 6, 22, 91, 408, 1938, 9614, 49335, 260130, 1402440, 7702632, 42975796, 243035536, 1390594458, 8038677054, 46892282815, 275750636070, 1633292229030, 9737153323590, 58392041019795, 352044769046880, 2132866978427640 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

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

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

The number of rooted non-separable planar maps with n edges. - Valery A. Liskovets, Mar 17 2005

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.

Number of left ternary trees having n nodes (n>=1). - Emeric Deutsch, Jul 23 2006

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

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

The number of fighting fish (branching polyominoes). - David Bevan, Jan 10 2018

The number of 1324-avoiding dominoes (gridded permutations). - David Bevan, Jan 10 2018

REFERENCES

E. Duchi, V. Guerrini, S. Rinaldi and G. Schaeffer, Fighting fish: enumerative properties. Sém. Lothar. Combin. 78B (2017), Art. 43, 12 pp.

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; http://www.maa.org/sites/default/files/pdf/pubs/books/members/cent_volume.pdf

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

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

S. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, Restricted non-separable planar maps and some pattern avoiding permutations, Discrete Applied Mathematics, Volume 161, Issues 16-17, November 2013, Pages 2514-2526.

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.

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

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.41.

LINKS

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

A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011. See p. 15.

E. Ben-Naim and P. L. Krapivsky, Popularity-Driven Networking, arXiv preprint arXiv:1112.0049 [cond-mat.stat-mech], 2011.

David Bevan, Robert Brignall, Andrew Elvey Price and Jay Pantone, A structural characterisation of Av(1324) and new bounds on its growth rate, arXiv preprint arXiv:1711.10325 [math.CO], 2017.

M. Bousquet-Mélou and A. Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, J Comb. Thy. B 96 (2006), 623-672.

W. G. Brown, Enumeration of non-separable planar maps, Canad. J. Math., 15 (1963), 526-545.

A. Del Lungo, F. Del Ristoro and J.-G. Penaud, Left ternary trees and non-separable rooted planar maps, Theor. Comp. Sci., 233, 2000, 201-215.

S. Dulucq, S. Gire, O. Guibert, A combinatorial proof of J. West's conjecture Discrete Math. 187 (1998), no. 1-3, 71--96. MR1630680(99f:05053).

S. Dulucq, S. Gire, and J. West, Permutations with forbidden subsequences and nonseparable planar maps, 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)

Eric S. Egge, Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics, MAA Focus, August/September 2015, pp. 33-34. [Annotated scanned copy]

W. Fang, Fighting fish and two-stack sortable permutations, arXiv preprint arXiv:1711.0571 [math.CO], 2017.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 713

I. Gessel and G. Xin, The generating function of ternary trees and continued fractions, Electron. J Combin. 13 (2006), paper 53.

O. Guibert, Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps, Discr. Math., 210 (2000), 71-85.

S. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, Restricted non-separable planar maps and some pattern avoiding permutations, 2012.

Sergey Kitaev, Anna de Mier, Marc Noy, On the number of self-dual rooted maps, European J. Combin. 35 (2014), 377-387. MR3090510. See Theorem 1.

Sergey Kitaev, Pavel Salimov, Christopher Severs, and Henning Ulfarsson, Restricted rooted non-separable planar maps, arXiv preprint arXiv:1202.1790 [math.CO], 2012.

L.-F. Préville-Ratelle and X. Viennot, An extension of Tamari lattices, arXiv preprint arXiv:1406.3787 [math.CO], 2014.

G. Schaeffer, A combinatorial interpretation of super-Catalan numbers of order two, (2001).

W. T. Tutte, A Census of Planar Maps, Canad. J. Math. 15 (1963), 249-271.

J. West, Sorting twice through a stack, Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991), Theoret. Comput. Sci. 117 (1993), no. 1-2, 303-313.

D. Zeilberger, A proof of Julian West's conjecture that the number of two-stacksortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!), Discrete Math., 102 (1992), 85-93.

P. Zinn-Justin and J.-B. Zuber, Matrix integrals and the counting of tangles and links, Discrete Math 246 (2002), 343-360.

P. Zinn-Justin and J.-B. Zuber, Matrix integrals and the generation and counting of virtual tangles and links, arXiv:math-ph/0303049, 2003; J.Knot Theor. Ramifications 13 (2004) 325-356.

FORMULA

a(n) = 2*C(3*n, 2*n+1)/(n*(n+1)), or 2*(3*n)!/((2*n+1)!*((n+1)!)).

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

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.

G.f.: (2/(3*x)) * (hypergeom([ -2/3, -1/3],[1/2],(27/4)*x)-1) - Mark van Hoeij, Nov 02 2009

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

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

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

a(n) = A007318(3*n, 2*n+1)/A000217(n) for n > 0. - Reinhard Zumkeller, Feb 17 2013

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

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

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

From Ilya Gutkovskiy, Jan 17 2017: (Start)

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

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

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

Table[(2(3n)!)/((2n+1)!(n+1)!), {n, 0, 30}] (* Harvey P. Dale, Mar 31 2013 *)

PROG

(Haskell)

a000139 0 = 2

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

-- Reinhard Zumkeller, Feb 17 2013

(Sage)

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

[A000139(n) for n in (0..23)]  # Peter Luschny, Jun 17 2013

(PARI) a(n)=binomial(3*n, n)*2/((n+1)*(2*n+1)); \\ Joerg Arndt, Jul 21 2014

(MAGMA) [2*Factorial(3*n)/(Factorial(2*n+1)*Factorial(n+1)): n in [0..25]]; // Vincenzo Librandi, Apr 20 2015

CROSSREFS

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

Sequence in context: A032085 A032163 A038078 * A114572 A052621 A212671

Adjacent sequences:  A000136 A000137 A000138 * A000140 A000141 A000142

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, entry revised Apr 24 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 18 17:08 EST 2018. Contains 299325 sequences. (Running on oeis4.)