Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T09:39:23.706Z Has data issue: false hasContentIssue false
  • English
  • Français

Patterns in Random Permutations Avoiding the Pattern 132

Published online by Cambridge University Press:  18 May 2016

SVANTE JANSON
SVANTE JANSON*
Affiliation:
Department of Mathematics, Uppsala University, PO box 480, SE-751 06 Uppsala, Sweden (e-mail: [email protected]), http://www2.math.uu.se/~svante/
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a random permutation drawn from the set of 132-avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by nλ(σ)/2, where λ(σ) is the length of σ plus the number of descents. The limit is not normal, and can be expressed as a functional of a Brownian excursion. Moments can be found by recursion.

Keywords

Primary 60C05Secondary 05A0560F05
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 1 , January 2017 , pp. 24 - 51
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Albert, M. H., Atkinson, M. D. and Brignall, R. (2011) The enumeration of permutations avoiding 2143 and 4231. Pure Math. Appl. 22 87–98.Google Scholar
[2] Albert, M. H., Atkinson, M. D. and Brignall, R. (2012) The enumeration of three pattern classes using monotone grid classes. Electron. J. Combin. 19 20.CrossRefGoogle Scholar
[3] Aldous, D. (1991) The continuum random tree II: An overview. In Stochastic Analysis: Durham 1990, Vol. 167 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 23–70.CrossRefGoogle Scholar
[4] Aldous, D. (1993) The continuum random tree III. Ann. Probab. 21 248–289.CrossRefGoogle Scholar
[5] Biane, P., Pitman, J. and Yor, M. (2001) Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions. Bull. Amer. Math. Soc. (N.S.) 38 435–465.CrossRefGoogle Scholar
[6] Billey, S. C., Jockusch, W. and Stanley, R. P. (1993) Some combinatorial properties of Schubert polynomials. J. Algebraic Combin. 2 345–374.CrossRefGoogle Scholar
[7] Billingsley, P. (1968) Convergence of Probability Measures, Wiley.Google Scholar
[8] Bóna, M. (2004) Combinatorics of Permutations, Chapman & Hall/CRC.CrossRefGoogle Scholar
[9] Bóna, M. (2007) The copies of any permutation pattern are asymptotically normal. arXiv:0712.2792 Google Scholar
[10] Bóna, M. (2010) The absence of a pattern and the occurrences of another. Discrete Math. Theor. Comput. Sci. 12 89–102.Google Scholar
[11] Bóna, M. (2010) On three different notions of monotone subsequences. In Permutation Patterns, Vol. 376 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 89–114.CrossRefGoogle Scholar
[12] Bóna, M. (2012) Surprising symmetries in objects counted by Catalan numbers. Electron. J. Combin. 19 62.CrossRefGoogle Scholar
[13] Bousquet-Mélou, M. and Janson, S. (2006) The density of the ISE and local limit laws for embedded trees. Ann. Appl. Probab. 16 1597–1632.CrossRefGoogle Scholar
[14] Cheng, S.-E., Eu, S.-P. and Fu, T.-S. (2007) Area of Catalan paths on a checkerboard. European J. Combin. 28 1331–1344.CrossRefGoogle Scholar
[15] Chow, T. and West, J. (1999) Forbidden subsequences and Chebyshev polynomials. Discrete Math. 204 119–128.CrossRefGoogle Scholar
[16] Cooper, J. Combinatorial problems I like. http://www.math.sc.edu/~cooper/combprob.html Google Scholar
[17] Drmota, M. (2009) Random Trees, Springer.CrossRefGoogle Scholar
[18] Durrett, R. T., Iglehart, D. L. and Miller, D. R. (1977) Weak convergence to Brownian meander and Brownian excursion. Ann. Probab. 5 117–129.Google Scholar
[19] Fill, J. A. and Janson, S. (2009) Precise logarithmic asymptotics for the right tails of some limit random variables for random trees. Ann. Combin. 12 403–416.CrossRefGoogle Scholar
[20] Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[21] Gut, A. (2013) Probability: A Graduate Course, second edition, Springer.CrossRefGoogle Scholar
[22] Homberger, C. (2012) Expected patterns in permutation classes. Electron. J. Combin. 19 43.CrossRefGoogle Scholar
[23] Janson, S. (2003) The Wiener index of simply generated random trees. Random Struct. Alg. 22 337–358.CrossRefGoogle Scholar
[24] Janson, S. (2007) Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas. Probab. Surv. 4 80–145.CrossRefGoogle Scholar
[25] Janson, S. Patterns in random permutations avoiding the pattern 132. (Earlier version of the present paper.) arXiv:1401.5679v1 Google Scholar
[26] Janson, S., Nakamura, B. and Zeilberger, D. (2015) On the asymptotic statistics of the number of occurrences of multiple permutation patterns. J. Combin. 6 117–143.Google Scholar
[27] Kallenberg, O. (2002) Foundations of Modern Probability, second edition, Springer.CrossRefGoogle Scholar
[28] Knuth, D. E. (1997) The Art of Computer Programming, Vol. 1: Fundamental Algorithms, third edition, Addison-Wesley.Google Scholar
[29] Krattenthaler, C. (2001) Permutations with restricted patterns and Dyck paths. Adv. Appl. Math. 27 510–530.CrossRefGoogle Scholar
[30] Louchard, G. (1984) The Brownian excursion area: A numerical analysis. Comput. Math. Appl. 10 413–417. Erratum: Comput. Math. Appl. A 12 (1986) 375.CrossRefGoogle Scholar
[31] Mansour, T. and Vainshtein, A. (2000) Restricted permutations, continued fractions, and Chebyshev polynomials. Electron. J. Combin. 7 R17.CrossRefGoogle Scholar
[32] Mansour, T. and Vainshtein, A. (2001) Restricted 132-avoiding permutations. Adv. Appl. Math. 26 258–269.CrossRefGoogle Scholar
[33] Mansour, T. and Vainshtein, A. (2001/02) Restricted permutations and Chebyshev polynomials. Sém. Lothar. Combin. 47 B47c.Google Scholar
[34] Marckert, J.-F. (2004) The rotation correspondence is asymptotically a dilatation. Random Struct. Alg. 24 118–132.CrossRefGoogle Scholar
[35] Marckert, J.-F. and Mokkadem, A. (2003) The depth first processes of Galton–Watson trees converge to the same Brownian excursion. Ann. Probab. 31 1655–1678.CrossRefGoogle Scholar
[36] Nguyen The, M. (2004) Area and inertial moment of Dyck paths. Combin. Probab. Comput. 13 697–716.Google Scholar
[37] Revuz, D. and Yor, M. (1999) Continuous Martingales and Brownian Motion, third edition, Springer.CrossRefGoogle Scholar
[38] Richard, C. (2009) On q-functional equations and excursion moments. Discrete Math. 309 207–230.CrossRefGoogle Scholar
[39] Robertson, A., Wilf, H. S. and Zeilberger, D. (1999) Permutation patterns and continued fractions. Electron. J. Combin. 6 R38.CrossRefGoogle Scholar
[40] Rudolph, K. (2013) Pattern popularity in 132-avoiding permutations. Electron. J. Combin. 20 8.CrossRefGoogle Scholar
[41] Simion, R. and Schmidt, F. W. (1985) Restricted permutations. European J. Combin. 6 383–406.CrossRefGoogle Scholar
[42] Stanley, R. P. (1999) Enumerative Combinatorics, Vol. 2, Cambridge University Press.CrossRefGoogle Scholar
[43] West, J. (1996) Generating trees and forbidden subsequences. Discrete Math. 157 363–374.CrossRefGoogle Scholar