A Lower Bound on the Expected Number of Distinct Patterns in a Random Permutation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912985418563584 |
|---|---|
| author | Borrás-Serrano, Verónica Byrne, Isabel Godbole, Anant Veimau, Nathaniel |
| author_facet | Borrás-Serrano, Verónica Byrne, Isabel Godbole, Anant Veimau, Nathaniel |
| contents | Let $π_n$ be a uniformly chosen random permutation on $[n]$. The authors of [2] showed that the expected number of distinct consecutive patterns of all lengths $k\in\{1,2,\ldots,n\}$ in $π_n$ was $\frac{n^2}{2}(1-o(1))$ as $n\to\infty$, exhibiting the fact that random permutations pack consecutive patterns near-perfectly. A conjecture was made in [11] that the same is true for non-consecutive patterns, i.e., that there are $2^n(1-o(1))$ distinct non-consecutive patterns expected in a random permutation. This conjecture is false, but, in this paper, we prove that a random permutation contains an expected number of at least $2^{n-1}(1+o(1))$ distinct permutations; this number is half of the range of the number of distinct permutations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_13194 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Lower Bound on the Expected Number of Distinct Patterns in a Random Permutation Borrás-Serrano, Verónica Byrne, Isabel Godbole, Anant Veimau, Nathaniel Combinatorics Probability 05A05 Let $π_n$ be a uniformly chosen random permutation on $[n]$. The authors of [2] showed that the expected number of distinct consecutive patterns of all lengths $k\in\{1,2,\ldots,n\}$ in $π_n$ was $\frac{n^2}{2}(1-o(1))$ as $n\to\infty$, exhibiting the fact that random permutations pack consecutive patterns near-perfectly. A conjecture was made in [11] that the same is true for non-consecutive patterns, i.e., that there are $2^n(1-o(1))$ distinct non-consecutive patterns expected in a random permutation. This conjecture is false, but, in this paper, we prove that a random permutation contains an expected number of at least $2^{n-1}(1+o(1))$ distinct permutations; this number is half of the range of the number of distinct permutations. |
| title | A Lower Bound on the Expected Number of Distinct Patterns in a Random Permutation |
| topic | Combinatorics Probability 05A05 |
| url | https://arxiv.org/abs/2601.13194 |