论文标题
群，累积和堆栈
Troupes, Cumulants, and Stack-Sorting
论文作者
论文摘要
计算二进制平面树的几个自由累积剂序列对应于经典累积物的序列，这些序列计算了同一树的减少版本。使用我们称为插入和分解的彩色二进制式平面树上的两个新操作，我们证明了这种令人惊讶的现象对我们称为群体的树木家属。我们提供了一个简单的团体表征，该剧集提供了一个广泛的框架，可以概括有关West的堆栈分类地图$ S $已知的几个结果。的确，我们提供了有关理解$ S $的一些主要技术的新证明；这些新的证据比原始证据更为概念，解释了称为有效挂钩配置的对象如何自然出现并概括为群体。对于$ t \ in \ {2,3 \} $，我们列举了$ t $ stack-stack-stack-sortable-stack-stack-stack-sortable-s-stack-and-s-stack-stack-stack-stack-stack-stack-stack-stack-stack-stack-stack-stack-stack-portufutations的下降都是峰值。 团队和累积物之间的意外连接提供了一个强大的新工具，用于分析取决于自由概率理论的堆栈分类图。我们提供了这种方法的许多应用。例如，我们表明，如果在s_ {n-1} $中均均匀地选择$σ\，则$ \ text {des}}（s（σ））+1 $的预期值是\ [\ left（3- \ sum_ {j = 0}^n}^n \ frac {1} {1} {1} {1} {j！} {j！ $ \ text {des}（s（σ））+1 $是渐近$（2+2e-e^2）n $。我们获得了相似的结果，即有关减少有色二进制平面树的后订单读数下降数量的相似结果。我们还获得了$ | s（s_n）| $的改进估算值，并针对$ s $的不可逆性程度进行了改进的下限。我们提供了两个新颖的公式，这些公式从自由转变为古典累积物。第一个由非交叉分区的总和给出，第二个由超过$ 231 $的有效挂钩配置给出。我们提出了几个开放问题。
Several sequences of free cumulants that count binary plane trees correspond to sequences of classical cumulants that count the decreasing versions of the same trees. Using two new operations on colored binary plane trees that we call insertion and decomposition, we prove that this surprising phenomenon holds for families of trees that we call troupes. We give a simple characterization of troupes, which provide a broad framework for generalizing several of the results known about West's stack-sorting map $s$. Indeed, we give new proofs of some of the main techniques that have been developed for understanding $s$; these new proofs are far more conceptual than the original ones, explain how the objects called valid hook configurations arise naturally, and generalize to troupes. For $t\in\{2,3\}$, we enumerate $t$-stack-sortable alternating permutations of odd length and $t$-stack-sortable permutations whose descents are all peaks. The unexpected connection between troupes and cumulants provides a powerful new tool for analyzing the stack-sorting map that hinges on free probability theory. We give numerous applications of this method. For example, we show that if $σ\in S_{n-1}$ is chosen uniformly at random, then the expected value of $\text{des}(s(σ))+1$ is \[\left(3-\sum_{j=0}^n\frac{1}{j!}\right)n.\] Furthermore, the variance of $\text{des}(s(σ))+1$ is asymptotically $(2+2e-e^2)n$. We obtain similar results concerning the expected number of descents of postorder readings of decreasing colored binary plane trees. We also obtain improved estimates for $|s(S_n)|$ and an improved lower bound for the degree of noninvertibility of $s$. We give two novel formulas that convert from free to classical cumulants. The first is given by a sum over noncrossing partitions, and the second is given by a sum over $231$-avoiding valid hook configurations. We pose several open problems.
