Asymptotics of self-overlapping permutations
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913743844147200 |
|---|---|
| author | Kirgizov, Sergey Nurligareev, Khaydar |
| author_facet | Kirgizov, Sergey Nurligareev, Khaydar |
| contents | In this work, we study the concept of self-overlapping permutations, which is related to the larger study of consecutive patterns in permutations. We show that this concept admits a simple and clear geometrical meaning, and prove that a permutation can be represented as a sequence of non-self-overlapping ones. The above structural decomposition allows us to obtain equations for the corresponding generating functions, as well as the complete asymptotic expansions for the probability that a large random permutation is (non-)self-overlapping. In particular, we show that almost all permutations are non-self-overlapping, and that the corresponding asymptotic expansion has the self-reference property: the involved coefficients count non-self-overlapping permutations once again. We also establish complete asymptotic expansions of the distributions of very tight non-self-overlapping patterns, and discuss the similarities of the non-self-overlapping permutations to other permutation building blocks, such as indecomposable and simple permutations, as well as their associated asymptotics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_11677 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Asymptotics of self-overlapping permutations Kirgizov, Sergey Nurligareev, Khaydar Combinatorics 05A05, 05A15, 05A16, 60C05 G.2.2; G.3 In this work, we study the concept of self-overlapping permutations, which is related to the larger study of consecutive patterns in permutations. We show that this concept admits a simple and clear geometrical meaning, and prove that a permutation can be represented as a sequence of non-self-overlapping ones. The above structural decomposition allows us to obtain equations for the corresponding generating functions, as well as the complete asymptotic expansions for the probability that a large random permutation is (non-)self-overlapping. In particular, we show that almost all permutations are non-self-overlapping, and that the corresponding asymptotic expansion has the self-reference property: the involved coefficients count non-self-overlapping permutations once again. We also establish complete asymptotic expansions of the distributions of very tight non-self-overlapping patterns, and discuss the similarities of the non-self-overlapping permutations to other permutation building blocks, such as indecomposable and simple permutations, as well as their associated asymptotics. |
| title | Asymptotics of self-overlapping permutations |
| topic | Combinatorics 05A05, 05A15, 05A16, 60C05 G.2.2; G.3 |
| url | https://arxiv.org/abs/2311.11677 |