Computational Approach to the S ​ C 231 SC_{231} Consecutive-Pattern-Avoiding Stack Sort

Kai Yi · 2026

Read Computational Approach to the S ​ C 231 SC_{231} Consecutive-Pattern-Avoiding Stack Sort by Kai Yi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18626.txt.

Introduction

Yi works out sort counts for every shuffle up to length 14 and gauges mean counts up to length 1000 for Defant and Zheng's stack sort map, which bars a pattern. Seidel and Sun had refuted a Defant and Zheng guess about peak counts for pattern 231. His counts hint peak and mean counts rise faster than a straight line over the tested spans, though the far-term trend stays open. He also proves facts about the map for pattern 231: an n-minus-1 floor and a quadratic cap on peak counts.

Catalog record

CREATORKai Yi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29005
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18626

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computational Approach to the S ​ C 231 SC_{231} Consecutive-Pattern-Avoiding Stack Sort Kai Yi Abstract Defant and Zheng introduced a consecutive-pattern-avoiding stack sort map S ​ C σ SC_{\sigma} , where the stack must avoid a consecutive pattern σ \sigma . Seidel and Sun disproved a conjecture in Defant and Zheng’s paper about the maximum sort-number of a length n n permutation under S ​ C 231 SC_{231} . In this paper, we compute sort-numbers for each permutation of length up to 14 14 , and we estimate the average sort-numbers up to length 1000 1000 . Our results suggest the maximum and average sort-numbers grow faster than linear with respect to n n for the tested ranges, though the long-term behavior remains unclear. We also prove properties of S ​ C 231 SC_{231} mathematically, such as a n − 1 n-1 lower bound and a ( n + 1 ) ​ ( n − 2 ) 2 \frac{(n+1)(n-2)}{2} upper bound for the maximum sort-number of length n n permutations. {asydef} size(10cm); // set a reasonable default usepackage(”amsmath”); usepackage(”amssymb”); settings.tex=”pdflatex”; settings.outformat=”pdf”; import geometry; void filldraw(picture pic = currentpicture, conic g, pen fillpen=defaultpen, pen drawpen=defaultpen) filldraw(pic, (path) g, fillpen, drawpen); void fill(picture pic = currentpicture, conic g, pen p=defaultpen) filldraw(pic, (path) g, p); pair foot(pair P, pair A, pair B) return foot(triangle(A,B,P).VC); pair centroid(pair A, pair B, pair C) return (A+B+C)/3; 1 Introduction and Preliminaries Stack sorting was first introduced in 1968 by Knuth in [ 1 ] , who proved a permutation can be sorted into the identity permutation using the stack sort machine (push and pop operations) if and only if it avoids the pattern 231 . The formal definition of pattern avoidance is: Let p and q be permutations. Let the entries of q be q_{1}q_{2}\dots q_{k} . If there exists a subsequence of entries p_{1}p_{2}\dots p_{k} in p such that p_{i}<p_{j} if and only if q_{i}<q_{j} for all indices i,j , we say p contains the pattern q . Otherwise, we say p avoids the pattern q . For example, 13425 avoids the pattern 321 but contains the pattern 123 because of the entries 1,3,5 . In 1990, West [ 2 ] introduced the stack sort function s:S_{n}\rightarrow S_{n} , which ”pushes” an entry into a stack if the entries in the stack would remain in increasing order from top to bottom and ”pops” an entry from the top of the stack if this would not happen. This is similar to the Tower of Hanoi, where you can not place a large disk on top of a small one. For example, here is how the permutation 15243 is sorted using West’s function: {asy} draw((0,0)–(2,0)–(2,-2)–(3,-2)–(3,0)–(5,0)); draw((5,-1)–(6,-1), arrow=Arrow()); draw((6,0)–(8,0)–(8,-2)–(9,-2)–(9,0)–(11,0)); draw((11,-1)–(12,-1), arrow=Arrow()); draw((12,0)–(14,0)–(14,-2)–(15,-2)–(15,0)–(17,0)); draw((17,-1)–(18,-1), arrow=Arrow()); draw((18,0)–(20,0)–(20,-2)–(21,-2)–(21,0)–(23,0)); draw((-1,-4)–(0,-4), arrow=Arrow()); draw((0,-3)–(2,-3)–(2,-5)–(3,-5)–(3,-3)–(5,-3)); draw((5,-4)–(6,-4), arrow=Arrow()); draw((6,-3)–(8,-3)–(8,-5)–(9,-5)–(9,-3)–(11,-3)); draw((11,-4)–(12,-4), arrow=Arrow()); draw((12,-3)–(14,-3)–(14,-5)–(15,-5)–(15,-3)–(17,-3)); draw((17,-4)–(18,-4), arrow=Arrow()); draw((18,-3)–(20,-3)–(20,-5)–(21,-5)–(21,-3)–(23,-3)); draw((-1,-7)–(0,-7), arrow=Arrow()); draw((0,-6)–(2,-6)–(2,-8)–(3,-8)–(3,-6)–(5,-6)); draw((5,-7)–(6,-7), arrow=Arrow()); draw((6,-6)–(8,-6)–(8,-8)–(9,-8)–(9,-6)–(11,-6)); draw((11,-7)–(12,-7), arrow=Arrow()); draw((12,-6)–(14,-6)–(14,-8)–(15,-8)–(15,-6)–(17,-6)); label(” 15243”, (4, 0.5)); label(”5243”, (10, 0.5)); label(”5243”, (16, 0.5)); label(”243”, (22, 0.5)); label(”43”, (4, -2.5)); label(”43”, (10, -2.5)); label(”3”, (16, -2.5)); label(”1”, (13, 0.5)); label(”1”, (19, 0.5)); label(”1”, (1, -2.5)); label(”12”, (7, -2.5)); label(”12”, (13, -2.5)); label(”12”, (19, -2.5)); label(”123”, (1, -5.5)); label(”1234”, (7, -5.5)); label(”12345”, (13, -5.5)); label(”1”, (8.5, -1.5)); label(”5”, (20.5, -1.5)); label(”5”, (2.5, -4.5)); label(”2”, (2.5, -3.8)); label(”5”, (8.5, -4.5)); label(”5”, (14.5, -4.5)); label(”4”, (14.5, -3.8)); label(”5”, (20.5, -4.5)); label(”4”, (20.5, -3.8)); label(”3”, (20.5, -3.1)); label(”5”, (2.5, -7.5)); label(”4”, (2.5, -6.8)); label(”5”, (8.5, -7.5)); Figure 1: Stack Sorting 15243 using West’s function In the second step, we pop 1 rather than push 5 because pushing 5 would result in 5 (a large entry) being in the stack on top of 1 (a small entry). Since West’s 1990 dissertation, many have explored variants of the original stack sort function. For example, in 2020, Cerbai, Claesson, and Ferrari [ 3 ] introduced the pattern-avoiding stack sorting function, s_{\sigma} . This stack differs from West’s stack because the numbers in the stack, arranged top to bottom, must avoid the pattern \sigma . In this new definition, West’s stack sorting function is s_{21} . A few months later, Defant and Zheng [ 4 ] introduce a related variant, the stack sorting function SC_{\sigma} . Unlike s_{\sigma} , the stack must avoid a consecutive pattern instead of a regular pattern. For example, 15243 contains the pattern 123 because of entries 1,2,3 , but it avoids the consecutive pattern \underline{123} because there does not exist three consecutive entries in increasing order. In our paper, we will underline a consecutive pattern to denote that it is consecutive. We will look at SC_{231} specifically. Let \Av_{n}(\sigma_{1},\sigma_{2},\dots,\sigma_{k}) denote the set of permutations in S_{n} that avoid the patterns \sigma_{1},\sigma_{2},\dots,\sigma_{k} . In Defant and Zheng’s paper [ 4 ] , the authors proposed the conjecture: Conjecture 1.1: Let n\geq 3 . We have SC_{231}^{2n-4}(\pi)\in\Av_{n}(132,231) for every \pi\in S_{n} . Furthermore, there exists a permutation \tau\in S_{n} such that SC_{231}^{2n-5}(\tau)\not\in\Av_{n}(132,231) . The motivation behind this conjecture is the fact that the periodic points of SC_{\sigma} are the permutations in \Av_{n}(\underline{\sigma},\underline{\rev(\sigma)}) . This was proved in Defant and Zheng’s paper [ 4 ] for patterns \sigma\in S_{3} , then proved in Siedel and Sun’s paper [ 5 ] for \sigma\in S_{k} , k\geq 3 . Note that \Av_{n}(\underline{231},\underline{\rev(231)}) is the same as \Av_{n}(231,\rev(231)) because both sets represent length n permutations that have no peaks. This conjecture was first verified in [ 4 ] up to n=9 , then disproved in [ 5 ] using the counterexample (4,6,8,5,11,7,2,9,10,3,1)\in S_{11} . This leads to the question: how many times do we really need to apply SC_{231} to force a length 11 permutation into a periodic point? We will explore this in more depth using a computational approach. Another paper that uses SC_{231} is [ 6 ] , in which they denote SC_{231} as SC_{2\underline{31}} . The paper [ 7 ] also explores SC_{231} , finding the fertility numbers of specific examples to prove that for any positive number f , there exists a permutation p such that |SC_{231}^{-1}(p)|=f . Define the sort-number of a permutation as the minimum number of times SC_{231} must be applied to it in order for it to enter \Av_{n}(132,231) . Other than a computational analysis of SC_{231} sort-numbers, our paper also improves the bounds for the maximum sort number in [ 5 ] to n-1\leq m(n)\leq\frac{(n+1)(n-2)}{2} and proves additional properties of SC_{231} mathematically. A key idea for exploring this question is what we will call the index of a permutation. Define the index of a permutation as: • 1 if 1 and 2 are not adjacent. • 2 if 1 and 2 are adjacent but 3 is not adjacent to either one. • 3 if 1 and 2 are adjacent, 3 is adjacent to either one, but 4 is not adjacent to 1,2, or 3 . … • n if 1 and 2 are adjacent, 3 is adjacent to either one, 4 is adjacent to some entry in 1 through 3 , and 5 is adjacent to some entry in 1 through 4 , …, and n is adjacent to some entry in 1 through n-1 . • Note that index n-1 does not exist, because if 1 through n-1 are all in a block, then n ,

Read the complete text