Fixed points of 321-avoiding permutations

Hoffman, Christopher; Rizzolo, Douglas; Slivken, Erik

doi:10.1090/proc/14299

Fixed points of 321-avoiding permutations
HTML articles powered by AMS MathViewer

by Christopher Hoffman, Douglas Rizzolo and Erik Slivken PDF

Proc. Amer. Math. Soc. 147 (2019), 861-872 Request permission

Abstract:

We describe the distribution of the number and location of the fixed points of permutations that avoid the pattern $321$ via a bijection with rooted ordered trees on $n+1$ vertices. Using the local limit theorem for Galton-Watson trees, we are able to give an explicit description of the limit of this distribution.

References

Romain Abraham and Jean-François Delmas, Local limits of conditioned Galton-Watson trees: the infinite spine case, Electron. J. Probab. 19 (2014), no. 2, 19. MR 3164755, DOI 10.1214/ejp.v19-2747
David Aldous and Jim Pitman, Tree-valued Markov chains derived from Galton-Watson processes, Ann. Inst. H. Poincaré Probab. Statist. 34 (1998), no. 5, 637–686 (English, with English and French summaries). MR 1641670, DOI 10.1016/S0246-0203(98)80003-4
Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, and Adeline Pierrot, The Brownian limit of separable permutations, Ann. Probab. 46 (2018), no. 4, 2134–2189. MR 3813988, DOI 10.1214/17-AOP1223
Miklós Bóna, Combinatorics of permutations, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2012. With a foreword by Richard Stanley. MR 2919720, DOI 10.1201/b12210
Sergi Elizalde, Consecutive patterns and statistics on restricted permutations. PhD thesis, Massachusetts Institute of Technology, 2004.
Sergi Elizalde, Fixed points and excedances in restricted permutations, Electron. J. Combin. 18 (2011), no. 2, Paper 29, 17. MR 2880679
Sergi Elizalde and Igor Pak, Bijections for refined restricted permutations, J. Combin. Theory Ser. A 105 (2004), no. 2, 207–219. MR 2046080, DOI 10.1016/j.jcta.2003.10.009
Christopher Hoffman, Douglas Rizzolo, and Erik Slivken, Pattern-avoiding permutations and Brownian excursion Part I: shapes and fluctuations, Random Structures Algorithms 50 (2017), no. 3, 394–419. MR 3632417, DOI 10.1002/rsa.20677
Christopher Hoffman, Douglas Rizzolo, and Erik Slivken, Pattern-avoiding permutations and Brownian excursion, part II: fixed points, Probab. Theory Related Fields 169 (2017), no. 1-2, 377–424. MR 3704772, DOI 10.1007/s00440-016-0732-2
Svante Janson, Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probab. Surv. 9 (2012), 103–252. MR 2908619, DOI 10.1214/11-PS188
Svante Janson, Patterns in random permutations avoiding the pattern 132, Combin. Probab. Comput. 26 (2017), no. 1, 24–51. MR 3579588, DOI 10.1017/S0963548316000171
Olav Kallenberg, Foundations of modern probability, 2nd ed., Probability and its Applications (New York), Springer-Verlag, New York, 2002. MR 1876169, DOI 10.1007/978-1-4757-4015-8
Douglas P. Kennedy, The Galton-Watson process conditioned on the total progeny, J. Appl. Probability 12 (1975), no. 4, 800–806. MR 386042, DOI 10.2307/3212730
Harry Kesten, Subdiffusive behavior of random walk on a random cluster, Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425–487 (English, with French summary). MR 871905
C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math. 27 (2001), no. 2-3, 510–530. Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000). MR 1868978, DOI 10.1006/aama.2001.0747
Russell Lyons, Robin Pemantle, and Yuval Peres, Conceptual proofs of $L\log L$ criteria for mean behavior of branching processes, Ann. Probab. 23 (1995), no. 3, 1125–1138. MR 1349164
Neal Madras and Lerna Pehlivan, Structure of random 312-avoiding permutations, Random Structures Algorithms 49 (2016), no. 3, 599–631. MR 3545829, DOI 10.1002/rsa.20601
Neal Madras and Lerna Pehlivan, Large deviations for permutations avoiding monotone patterns, Electron. J. Combin. 23 (2016), no. 4, Paper 4.36, 20. MR 3604794, DOI 10.37236/6225
Neal Madras and Gökhan Yıldırım, Longest monotone subsequences and rare regions of pattern-avoiding permutations, Electron. J. Combin. 24 (2017), no. 4, Paper No. 4.13, 29. MR 3711046, DOI 10.37236/6402
Sam Miner and Igor Pak, The shape of random pattern-avoiding permutations, Adv. in Appl. Math. 55 (2014), 86–130. MR 3176717, DOI 10.1016/j.aam.2013.12.004
J. Neveu, Arbres et processus de Galton-Watson, Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 2, 199–207 (French, with English summary). MR 850756
Aaron Robertson, Dan Saracino, and Doron Zeilberger, Refined restricted permutations, Ann. Comb. 6 (2002), no. 3-4, 427–444. MR 1980351, DOI 10.1007/s000260200015
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589