Enumerating pattern-avoiding permutations by leading terms
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_ | 1866910029385302016 |
|---|---|
| author | Eğecioğlu, Ömer Gaiser, Collier Yin, Mei |
| author_facet | Eğecioğlu, Ömer Gaiser, Collier Yin, Mei |
| contents | The number of 123-avoiding permutation on $\{1,2,\ldots,n\}$ with a fixed leading terms is counted by the ballot numbers. The same holds for $132$-avoiding permutations. These results were proved by Miner and Pak using the Robinson-Schensted-Knuth (RSK) correspondence to connect permutations with Dyck paths. In this paper, we first provide an alternate proof of these enumeration results via a direct counting argument. We then study the number of pattern-avoiding permutations with a fixed prefix of length $t\geq1$, generalizing the $t=1$ case. We find exact expressions for single and pairs of patterns of length three as well as the pair $3412$ and $3421$. These expressions depend on $t$, the extrema, and the order statistics. We also define $r$-Wilf equivalence for permutations with a single fixed leading term $r$, and classify the $r$-Wilf-equivalence classes for both classical and vincular patterns of length three. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_15964 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Enumerating pattern-avoiding permutations by leading terms Eğecioğlu, Ömer Gaiser, Collier Yin, Mei Combinatorics 05A05, 05A15 The number of 123-avoiding permutation on $\{1,2,\ldots,n\}$ with a fixed leading terms is counted by the ballot numbers. The same holds for $132$-avoiding permutations. These results were proved by Miner and Pak using the Robinson-Schensted-Knuth (RSK) correspondence to connect permutations with Dyck paths. In this paper, we first provide an alternate proof of these enumeration results via a direct counting argument. We then study the number of pattern-avoiding permutations with a fixed prefix of length $t\geq1$, generalizing the $t=1$ case. We find exact expressions for single and pairs of patterns of length three as well as the pair $3412$ and $3421$. These expressions depend on $t$, the extrema, and the order statistics. We also define $r$-Wilf equivalence for permutations with a single fixed leading term $r$, and classify the $r$-Wilf-equivalence classes for both classical and vincular patterns of length three. |
| title | Enumerating pattern-avoiding permutations by leading terms |
| topic | Combinatorics 05A05, 05A15 |
| url | https://arxiv.org/abs/2309.15964 |