An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation
Let $\pi_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, the authors of a recent paper showed that the expected number of distinct consecutive patterns of all lengths $k\in\{1,2,\ldots,...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2024-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/12458/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850056409881772032 |
|---|---|
| author | Anant Godbole Hannah Swickheimer |
| author_facet | Anant Godbole Hannah Swickheimer |
| author_sort | Anant Godbole |
| collection | DOAJ |
| description | Let $\pi_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, the authors of a recent paper showed that the expected number of distinct consecutive patterns of all lengths $k\in\{1,2,\ldots,n\}$ in $\pi_n$ is $\frac{n^2}{2}(1-o(1))$ as $n\to\infty$. This exhibited the fact that random permutations pack consecutive patterns near-perfectly. We use entirely different methods, namely the Stein-Chen method of Poisson approximation, to reprove and slightly improve their result. |
| format | Article |
| id | doaj-art-bde90eef4b484221a118f9754a69f080 |
| institution | DOAJ |
| issn | 1365-8050 |
| language | English |
| publishDate | 2024-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-bde90eef4b484221a118f9754a69f0802025-08-20T02:51:42ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502024-05-01vol. 26:1, Permutation...Special issues10.46298/dmtcs.1245812458An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random PermutationAnant Godbole0https://orcid.org/0000-0001-6984-3194Hannah Swickheimer1East Tennessee State UniversityEast Tennessee State UniversityLet $\pi_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, the authors of a recent paper showed that the expected number of distinct consecutive patterns of all lengths $k\in\{1,2,\ldots,n\}$ in $\pi_n$ is $\frac{n^2}{2}(1-o(1))$ as $n\to\infty$. This exhibited the fact that random permutations pack consecutive patterns near-perfectly. We use entirely different methods, namely the Stein-Chen method of Poisson approximation, to reprove and slightly improve their result.http://dmtcs.episciences.org/12458/pdfmathematics - combinatoricsmathematics - probability05a99, 60c05 |
| spellingShingle | Anant Godbole Hannah Swickheimer An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics mathematics - probability 05a99, 60c05 |
| title | An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation |
| title_full | An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation |
| title_fullStr | An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation |
| title_full_unstemmed | An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation |
| title_short | An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random Permutation |
| title_sort | alternative proof for the expected number of distinct consecutive patterns in a random permutation |
| topic | mathematics - combinatorics mathematics - probability 05a99, 60c05 |
| url | http://dmtcs.episciences.org/12458/pdf |
| work_keys_str_mv | AT anantgodbole analternativeprooffortheexpectednumberofdistinctconsecutivepatternsinarandompermutation AT hannahswickheimer analternativeprooffortheexpectednumberofdistinctconsecutivepatternsinarandompermutation AT anantgodbole alternativeprooffortheexpectednumberofdistinctconsecutivepatternsinarandompermutation AT hannahswickheimer alternativeprooffortheexpectednumberofdistinctconsecutivepatternsinarandompermutation |