论文标题
堆栈分类地图的生育单调性和平均复杂性
Fertility Monotonicity and Average Complexity of the Stack-Sorting Map
论文作者
论文摘要
令$ \ MATHCAL D_N $表示West的堆栈分类地图$ s $的平均迭代次数，这些迭代$ s $是将$ s_n $中排列的$ s_n $中的排列$ 123 \ cdots n $。我们证明\ [0.62433 \oftλ\ leq \ liminf_ {n \ to \ infty} \ frac {\ mathcal d_n} {n} \ leq \ limsup_ {n \ n \ n \ \ frac {3} {5}（7-8 \ log 2）\大约0.87289，\]，其中$λ$是Golomb-Dickman常数。我们的下边界在West的下限$ 0.23 $上的改善，我们的上限是$ 1 $的微不足道上限的第一个改进。然后，我们表明，截止日期的迭代次数增加了$ s $的单调增加。更准确地说，我们证明了$ | s^{ - 1}（σ）| \ leq | s^{ - 1}（s（σ））| $ for S_N $中的所有$σ\ for s_n $中的所有$σ\，在$σ= 123 \ cdots n $中，当equality保持equality时。这是第一个表现出对Bóna提出的堆栈分类地图的返回哲学的定理。在此过程中，我们注意到堆栈分类地图与$ s_n $上的左右弱订单之间的一些连接。
Let $\mathcal D_n$ denote the average number of iterations of West's stack-sorting map $s$ that are needed to sort a permutation in $S_n$ into the identity permutation $123\cdots n$. We prove that \[0.62433\approxλ\leq\liminf_{n\to\infty}\frac{\mathcal D_n}{n}\leq\limsup_{n\to\infty}\frac{\mathcal D_n}{n}\leq \frac{3}{5}(7-8\log 2)\approx 0.87289,\] where $λ$ is the Golomb-Dickman constant. Our lower bound improves upon West's lower bound of $0.23$, and our upper bound is the first improvement upon the trivial upper bound of $1$. We then show that fertilities of permutations increase monotonically upon iterations of $s$. More precisely, we prove that $|s^{-1}(σ)|\leq|s^{-1}(s(σ))|$ for all $σ\in S_n$, where equality holds if and only if $σ=123\cdots n$. This is the first theorem that manifests a law-of-diminishing-returns philosophy for the stack-sorting map that Bóna has proposed. Along the way, we note some connections between the stack-sorting map and the right and left weak orders on $S_n$.
