English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $\mathcal D_n$ denote the average number of iterations of West'sstack-sorting map $s$ that are needed to sort a permutation in $S_n$ into theidentity permutation $123\cdots n$. We prove that\[0.62433\approx\lambda\leq\liminf_{n\to\infty}\frac{\mathcalD_n}{n}\leq\limsup_{n\to\infty}\frac{\mathcal D_n}{n}\leq \frac{3}{5}(7-8\log2)\approx 0.87289,\] where $\lambda$ is the Golomb-Dickman constant. Our lowerbound improves upon West's lower bound of $0.23$, and our upper bound is thefirst improvement upon the trivial upper bound of $1$. We then show thatfertilities of permutations increase monotonically upon iterations of $s$. Moreprecisely, we prove that $|s^{-1}(\sigma)|\leq|s^{-1}(s(\sigma))|$ for all$\sigma\in S_n$, where equality holds if and only if $\sigma=123\cdots n$. Thisis the first theorem that manifests a law-of-diminishing-returns philosophy forthe stack-sorting map that B\'ona has proposed. Along the way, we note someconnections between the stack-sorting map and the right and left weak orders on$S_n$.

Fertility Monotonicity and Average Complexity of the Stack-Sorting Map