论文标题
用固定的峰设置排列排列
Sorting Permutations with Fixed Pinnacle Set
论文作者
论文摘要
我们对戴维斯等人提出的问题给出了积极的答案。 （{\ em离散数学} 341，2018），关于具有相同峰值集的排列。给定的$π\在s_n $中，$π$的{\ em Pinnacle}是一个元素$π_i$（$ i \ neq 1，n $），因此$π_{i-1}<π_i>π__i>π_{i+1} $。问题是：给定$π，π'\在s_n $中，带有相同的顶峰集$ s $，是否有一系列操作将$π$转换为$π'$，以便所有中间排列都有峰值$ s $？我们介绍{\ em平衡逆转}，定义为不修改其应用置换的悬崖集的逆转。然后，我们表明$π$可以通过平衡的逆转（即转换为标准排列$ \ id_s $）进行分类，这意味着最多可以将$π$转换为$ 4N-2 \ min \ {p，3 \} $ balanced反向，其中$ 4n-2 \ min \ {p，3 \}，其中$ p = | s | s | s | geq 1 $。如果$ p = 0 $，最多需要$ 2N-1 $ $平衡的逆转。
We give a positive answer to a question raised by Davis et al. ({\em Discrete Mathematics} 341, 2018), concerning permutations with the same pinnacle set. Given $π\in S_n$, a {\em pinnacle} of $π$ is an element $π_i$ ($i\neq 1,n$) such that $π_{i-1}<π_i>π_{i+1}$. The question is: given $π,π'\in S_n$ with the same pinnacle set $S$, is there a sequence of operations that transforms $π$ into $π'$ such that all the intermediate permutations have pinnacle set $S$? We introduce {\em balanced reversals}, defined as reversals that do not modify the pinnacle set of the permutation to which they are applied. Then we show that $π$ may be sorted by balanced reversals (i.e. transformed into a standard permutation $\Id_S$), implying that $π$ may be transformed into $π'$ using at most $4n-2\min\{p,3\}$ balanced reversals, where $p=|S|\geq 1$. In case $p=0$, at most $2n-1$ balanced reversals are needed.
