|
| |
|
|
A000139
|
|
Number of 2-stack sortable permutations on n letters.
(Formerly M1660 N0651)
|
|
9
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,1
|
|
|
COMMENTS
| The number of rooted non-separable planar maps with n edges. - Valery A. Liskovets (liskov(AT)im.bas-net.by), 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 (deutsch(AT)duke.poly.edu), 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
|
|
|
REFERENCES
| E. Ben-Naim and P. L. Krapivsky, Popularity-Driven Networking, Arxiv preprint arXiv:1112.0049, 2011
W. G. Brown, Enumeration of non-separable planar maps, Canad. J. Math., 15:3 (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.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.
O. Guibert, Stack words, ..., Discr. Math., 210 (2000), 71-85.
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.
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 ..., Discrete Math., 102 (1992), 85-93.
|
|
|
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.
M. Bousqet-Melou and A. Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, J Comb. Thy. B 96 (2006), 623-672.
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.
G. Schaeļ¬er, A combinatorial interpretation of super-Catalan numbers of order two, (2001).
P. Zinn-Justin and J.-B. Zuber, Matrix integrals and the generation and counting of virtual tangles and links, Discrete Math 246 (2002), 343-360, p. 11.
|
|
|
FORMULA
| 2*C(3n, 2n+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 + zB(z), where B(z) = 1 - 8z + 2z(5-6z)B - 2z^2(1+3z)B^2 - z^4B^3.
G.f.: (2/(3*x)) * (hypergeom([ -2/3, -1/3],[1/2],(27/4)*x)-1) [From Mark van Hoeij (hoeij(AT)math.fsu.edu), 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
|
|
|
MAPLE
| A000139 := n->2*(3*n)!/((2*n+1)!*((n+1)!)); [seq(f(i), i=0..30)];
|
|
|
CROSSREFS
| Cf. A000142, A000309, A006335, A004677.
Sequence in context: A032085 A032163 A038078 * A114572 A052621 A131057
Adjacent sequences: A000136 A000137 A000138 * A000140 A000141 A000142
|
|
|
KEYWORD
| nonn,easy,nice,changed
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
