论文标题
DI-SK树上的组合培养
A combinatorial bijection on di-sk trees
论文作者
论文摘要
Di-Sk树是一棵根生的二进制树，其节点由$ \ oplus $或$ \ aminus $标记，并且没有任何节点具有与合适的孩子相同的标签。 DI-SK树是自然的，可分开的排列。我们在Di-Sk树上构建了组合培养，证明了两个五五元$（\ lmax，\ lmin，\ desb，\ iar，\ comp）$和$（\ lmax，\ lmin，\ lmin，\ desb，\ desb，\ comp，\ comp，\ iar）$具有相同的分配分配。在这里，对于置换$π$，$ \ lmax（π）/\ lmin（π）$是$π$ $π$和$ \ desb（π）$的一组值的值，是$π$的下降底部，而$ \ comp（comp（comp（fime）$）的数字（π）$ undecon（π）$（π）$（π）$（π）$ outs（π）$ outs（π）$ ous outs（π）和π$π; $π$的初始上升运行。 有趣的是，我们的两者培训专门针对$ 312 $的避免排列的培训，该排列提供了（最多可（延长经典）{\ em knuth--richards bioviond}）Rubey（2016）的替代方法，该方法宣称两种三倍的$（\ lmax，\ lmax，\ iar，\ comp）$（\ comp）$（\ comp）$（\ comp） $ 321 $ - 避免排列。 Rubey的结果是由于Adin-bagno-Roichman引起的等分分配的对称扩展，这意味着$ 321 $的$ 321 $ - 避免零件数量的零件的排列是Schur的。 最终提出了有关树遍历的各种统计数据的一些等分分配结果。
A di-sk tree is a rooted binary tree whose nodes are labeled by $\oplus$ or $\ominus$, and no node has the same label as its right child. The di-sk trees are in natural bijection with separable permutations. We construct a combinatorial bijection on di-sk trees proving the two quintuples $(\LMAX,\LMIN,\DESB,\iar,\comp)$ and $(\LMAX,\LMIN,\DESB,\comp,\iar)$ have the same distribution over separable permutations. Here for a permutation $π$, $\LMAX(π)/\LMIN(π)$ is the set of values of the left-to-right maxima/minima of $π$ and $\DESB(π)$ is the set of descent bottoms of $π$, while $\comp(π)$ and $\iar(π)$ are respectively the number of components of $π$ and the length of initial ascending run of $π$. Interestingly, our bijection specializes to a bijection on $312$-avoiding permutations, which provides (up to the classical {\em Knuth--Richards bijection}) an alternative approach to a result of Rubey (2016) that asserts the two triples $(\LMAX,\iar,\comp)$ and $(\LMAX,\comp,\iar)$ are equidistributed on $321$-avoiding permutations. Rubey's result is a symmetric extension of an equidistribution due to Adin--Bagno--Roichman, which implies the class of $321$-avoiding permutations with a prescribed number of components is Schur positive. Some equidistribution results for various statistics concerning tree traversal are presented in the end.
