Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-11T19:51:18.409Z 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: svante.janson@math.uu.se), http://www2.math.uu.se/~svante/
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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