Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.6
URN: urn:nbn:de:0030-drops-88996
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8899/
Janson, Svante
Patterns in Random Permutations Avoiding Some Other Patterns (Keynote Speakers)
| pdf-format: |
|
Abstract
Consider a random permutation drawn from the set of permutations of length n that avoid a given set of one or several patterns of length 3. We show that the number of occurrences of another pattern has a limit distribution, after suitable scaling. In several cases, the limit is normal, as it is in the case of unrestricted random permutations; in other cases the limit is a non-normal distribution, depending on the studied pattern. In the case when a single pattern of length 3 is forbidden, the limit distributions can be expressed in terms of a Brownian excursion.The analysis is made case by case; unfortunately, no general method is known, and no general pattern emerges from the results.
BibTeX - Entry
@InProceedings{janson:LIPIcs:2018:8899,
author = {Svante Janson},
title = {{Patterns in Random Permutations Avoiding Some Other Patterns (Keynote Speakers)}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {6:1--6:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-078-1},
ISSN = {1868-8969},
year = {2018},
volume = {110},
editor = {James Allen Fill and Mark Daniel Ward},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8899},
URN = {urn:nbn:de:0030-drops-88996},
doi = {10.4230/LIPIcs.AofA.2018.6},
annote = {Keywords: Random permutations, patterns, forbidden patterns, limit in distribution, U-statistics}
}
| Keywords: | Random permutations, patterns, forbidden patterns, limit in distribution, U-statistics | |
| Seminar: | 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 18.06.2018 |
