Enumerating 1324-avoiders with few inversions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912003071672320 |
|---|---|
| author | Linusson, Svante Verkama, Emil |
| author_facet | Linusson, Svante Verkama, Emil |
| contents | We enumerate the numbers $Av_n^k(1324)$ of 1324-avoiding $n$-permutations with exactly $k$ inversions for all $k$ and $n \geq (k+7)/2$. The result depends on a structural characterization of such permutations in terms of a new notion of almost-decomposability. In particular, our enumeration verifies half of a conjecture of Claesson, Jelínek and Steingrímsson, according to which $Av_n^k(1324) \leq Av_{n+1}^k(1324)$ for all $n$ and $k$. Proving also the other half would improve the best known upper bound for the exponential growth rate of the number of $1324$-avoiders from $13.5$ to approximately $13.002$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15075 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Enumerating 1324-avoiders with few inversions Linusson, Svante Verkama, Emil Combinatorics 05A05, 05A15 We enumerate the numbers $Av_n^k(1324)$ of 1324-avoiding $n$-permutations with exactly $k$ inversions for all $k$ and $n \geq (k+7)/2$. The result depends on a structural characterization of such permutations in terms of a new notion of almost-decomposability. In particular, our enumeration verifies half of a conjecture of Claesson, Jelínek and Steingrímsson, according to which $Av_n^k(1324) \leq Av_{n+1}^k(1324)$ for all $n$ and $k$. Proving also the other half would improve the best known upper bound for the exponential growth rate of the number of $1324$-avoiders from $13.5$ to approximately $13.002$. |
| title | Enumerating 1324-avoiders with few inversions |
| topic | Combinatorics 05A05, 05A15 |
| url | https://arxiv.org/abs/2408.15075 |