Growth Rates Of Permutations With Given Descent Or Peak Set

Abstract

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/\pi \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$.

arXiv comment26 pages