Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays
A permutation $\tau$ in the symmetric group $S_j$ is minimally overlapping if any two consecutive occurrences of $\tau$ in a permutation $\sigma$ can share at most one element. B\'ona \cite{B} showed that the proportion of minimal overlapping patterns in $S_j$ is at least $3 -e$. Given a permut...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2016-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1315/pdf |
| _version_ | 1797270061995524096 |
|---|---|
| author | Ran Pan Jeffrey B. Remmel |
| author_facet | Ran Pan Jeffrey B. Remmel |
| author_sort | Ran Pan |
| collection | DOAJ |
| description | A permutation $\tau$ in the symmetric group $S_j$ is minimally overlapping if
any two consecutive occurrences of $\tau$ in a permutation $\sigma$ can share
at most one element. B\'ona \cite{B} showed that the proportion of minimal
overlapping patterns in $S_j$ is at least $3 -e$. Given a permutation $\sigma$,
we let $\text{Des}(\sigma)$ denote the set of descents of $\sigma$. We study
the class of permutations $\sigma \in S_{kn}$ whose descent set is contained in
the set $\{k,2k, \ldots (n-1)k\}$. For example, up-down permutations in
$S_{2n}$ are the set of permutations whose descent equal $\sigma$ such that
$\text{Des}(\sigma) = \{2,4, \ldots, 2n-2\}$. There are natural analogues of
the minimal overlapping permutations for such classes of permutations and we
study the proportion of minimal overlapping patterns for each such class. We
show that the proportion of minimal overlapping permutations in such classes
approaches $1$ as $k$ goes to infinity. We also study the proportion of minimal
overlapping patterns in standard Young tableaux of shape $(n^k)$. |
| first_indexed | 2024-04-25T01:58:17Z |
| format | Article |
| id | doaj.art-2b6a81db637744b1b6991aeee0a80222 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:17Z |
| publishDate | 2016-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-2b6a81db637744b1b6991aeee0a802222024-03-07T15:30:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502016-05-01Vol. 18 no. 2, Permutation...Permutation Patterns10.46298/dmtcs.13151315Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arraysRan PanJeffrey B. RemmelA permutation $\tau$ in the symmetric group $S_j$ is minimally overlapping if any two consecutive occurrences of $\tau$ in a permutation $\sigma$ can share at most one element. B\'ona \cite{B} showed that the proportion of minimal overlapping patterns in $S_j$ is at least $3 -e$. Given a permutation $\sigma$, we let $\text{Des}(\sigma)$ denote the set of descents of $\sigma$. We study the class of permutations $\sigma \in S_{kn}$ whose descent set is contained in the set $\{k,2k, \ldots (n-1)k\}$. For example, up-down permutations in $S_{2n}$ are the set of permutations whose descent equal $\sigma$ such that $\text{Des}(\sigma) = \{2,4, \ldots, 2n-2\}$. There are natural analogues of the minimal overlapping permutations for such classes of permutations and we study the proportion of minimal overlapping patterns for each such class. We show that the proportion of minimal overlapping permutations in such classes approaches $1$ as $k$ goes to infinity. We also study the proportion of minimal overlapping patterns in standard Young tableaux of shape $(n^k)$.https://dmtcs.episciences.org/1315/pdfmathematics - combinatorics |
| spellingShingle | Ran Pan Jeffrey B. Remmel Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays |
| title_full | Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays |
| title_fullStr | Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays |
| title_full_unstemmed | Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays |
| title_short | Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays |
| title_sort | asymptotics for minimal overlapping patterns for generalized euler permutations standard tableaux of rectangular shape and column strict arrays |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/1315/pdf |
| work_keys_str_mv | AT ranpan asymptoticsforminimaloverlappingpatternsforgeneralizedeulerpermutationsstandardtableauxofrectangularshapeandcolumnstrictarrays AT jeffreybremmel asymptoticsforminimaloverlappingpatternsforgeneralizedeulerpermutationsstandardtableauxofrectangularshapeandcolumnstrictarrays |