Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.12719 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915503716433920 |
|---|---|
| author | Omar, Mohamed Troyka, Justin M. |
| author_facet | Omar, Mohamed Troyka, Justin M. |
| contents | Given a set $I \subseteq \mathbb{N}$, consider the sequences $\{d_n(I)\},\{p_n(I)\}$ where for any $n$, $d_n(I)$ and $p_n(I)$ respectively count the number of permutations in the symmetric group $\mathfrak{S}_n$ whose descent set (respectively peak set) is $I \cap [n-1]$. We investigate the growth rates $\text{gr} \ d_n(I) = \lim_{n \to \infty} \left(d_n(I)/n!\right)^{1/n}$ and $\text{gr} \ p_n(I) = \lim_{n \to \infty} \left(p_n(I)/n!\right)^{1/n}$ over all $I \subseteq \mathbb{N}$. Our main contributions are two-fold. Firstly, we prove that the numbers $\text{gr} \ d_n(I)$ over all $I \subseteq \mathbb{N}$ are exactly the interval $\left[0,2/π\right]$. To do so, we construct an algorithm that explicitly builds $I$ for any desired limit $L$ in the interval. Secondly, we prove that the numbers $\text{gr} \ p_n(I)$ for periodic sets $I \subseteq \mathbb{N}$ form a dense set in $\left[0,1/\sqrt[3]{3}\right]$. We do this by explicitly finding, for any prescribed $L$ in the interval, a set $I$ whose corresponding growth rate is arbitrarily close to $L$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_12719 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Growth Rates Of Permutations With Given Descent Or Peak Set Omar, Mohamed Troyka, Justin M. Combinatorics Given a set $I \subseteq \mathbb{N}$, consider the sequences $\{d_n(I)\},\{p_n(I)\}$ where for any $n$, $d_n(I)$ and $p_n(I)$ respectively count the number of permutations in the symmetric group $\mathfrak{S}_n$ whose descent set (respectively peak set) is $I \cap [n-1]$. We investigate the growth rates $\text{gr} \ d_n(I) = \lim_{n \to \infty} \left(d_n(I)/n!\right)^{1/n}$ and $\text{gr} \ p_n(I) = \lim_{n \to \infty} \left(p_n(I)/n!\right)^{1/n}$ over all $I \subseteq \mathbb{N}$. Our main contributions are two-fold. Firstly, we prove that the numbers $\text{gr} \ d_n(I)$ over all $I \subseteq \mathbb{N}$ are exactly the interval $\left[0,2/π\right]$. To do so, we construct an algorithm that explicitly builds $I$ for any desired limit $L$ in the interval. Secondly, we prove that the numbers $\text{gr} \ p_n(I)$ for periodic sets $I \subseteq \mathbb{N}$ form a dense set in $\left[0,1/\sqrt[3]{3}\right]$. We do this by explicitly finding, for any prescribed $L$ in the interval, a set $I$ whose corresponding growth rate is arbitrarily close to $L$. |
| title | Growth Rates Of Permutations With Given Descent Or Peak Set |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.12719 |