Emerging consecutive pattern avoidance
By: Nathanaël Hassler, Sergey Kirgizov
Potential Business Impact:
Finds patterns in number lists more easily.
In this note we study the {\em asymptotic popularity}, that is, the limit probability to find a given consecutive pattern at a random position in a random permutation in the eighteen classes of permutations avoiding at least two length 3 consecutive patterns. We show that for ten classes, this popularity can be readily deduced from the structure of permutations. By combining analytical and bijective approaches, we study in details two more involved cases. The problem remains open for five classes.
Similar Papers
Inapproximability of Counting Permutation Patterns
Data Structures and Algorithms
Makes counting patterns in data much faster.
Compact representations of pattern-avoiding permutations
Data Structures and Algorithms
Stores special number lists super fast.
Permutation patterns in streams
Data Structures and Algorithms
Finds hidden number patterns in fast-moving lists.