论文标题
Bubblesort操作员下的预先映射
Preimages under the bubblesort operator
论文作者
论文摘要
我们研究Bubblesort操作员$ \ Mathbf {B} $下的排列的预图。我们的描述比更复杂的排序操作员$ \ Mathbf {s} $（stackSort）和$ \ Mathbf {q} $（queueuesort）所知要完成的描述要完整得多。我们明确描述从$ \ Mathbf {b} $下方的$π$的任何排列$π$的$ \π$的$π$的$π$，这表明如果$ 2^{k-1} $此类preIbages如果$ k $是这些左右最高最大值的数量。我们进一步考虑，对于每个$ n $，$ t_n $记录其节点中的所有尺寸$ n $的排列，其中从子女到父母的边缘对应于$ \ mathbf {b} $的应用（根为身份排列），我们介绍了这些树的几个属性。特别是，对于每个排列$π$，我们展示了$ t_n $的子树源于$π$的子树是由$π$的左右最大值的数量确定的，以及$π$的左右最长最高后缀的长度。在此结果的基础上，我们确定了这种树木中每个高度的节点和叶子的数量，并恢复（分别获得）$ t_n $中的节点（分别叶子）的平均高度。
We study preimages of permutations under the bubblesort operator $\mathbf{B}$. We achieve a description of these preimages much more complete than what is known for the more complicated sorting operators $\mathbf{S}$ (stacksort) and $\mathbf{Q}$ (queuesort). We describe explicitly the set of preimages under $\mathbf{B}$ of any permutation $π$ from the left-to-right maxima of $π$, showing that there are $2^{k-1}$ such preimages if $k$ is the number of these left-to-right maxima. We further consider, for each $n$, the tree $T_n$ recording all permutations of size $n$ in its nodes, in which an edge from child to parent corresponds to an application of $\mathbf{B}$ (the root being the identity permutation), and we present several properties of these trees. In particular, for each permutation $π$, we show how the subtree of $T_n$ rooted at $π$ is determined by the number of left-to-right maxima of $π$ and the length of the longest suffix of left-to-right maxima of $π$. Building on this result, we determine the number of nodes and leaves at every height in such trees, and we recover (resp. obtain) the average height of nodes (resp. leaves) in $T_n$.
