2026-07-22T14:06:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8899 2024-03-12T11:57:43Z ddc:004 open_access

Patterns in Random Permutations Avoiding Some Other Patterns (Keynote Speakers) Janson, Svante Random permutations patterns forbidden patterns limit in distribution U-statistics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Svante Janson 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.6 urn:nbn:de:0030-drops-88996 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode