Computational Approach to the $S{C}_{231}$ Consecutive-Pattern-Avoiding Stack Sort

Abstract

Defant and Zheng introduced a consecutive-pattern-avoiding stack sort map $S{C}_{\ddot{I}}ƒ$, where the stack must avoid a consecutive pattern $\ddot{I}ƒ$. Seidel and Sun disproved a conjecture in Defant and Zheng's paper about the maximum sort-number of a length $n$ permutation under $S{C}_{231}$. In this paper, we compute sort-numbers for each permutation of length up to $14$, and we estimate the average sort-numbers up to length $1000$. Our results suggest the maximum and average sort-numbers grow faster than linear with respect to $n$ for the tested ranges, though the long-term behavior remains unclear. We also prove properties of $S{C}_{231}$ mathematically, such as a $n-1$ lower bound and a $\frac{(n+1)(n-2)}{2}$ upper bound for the maximum sort-number of length $n$ permutations.

10 pages, 6 figures