Permutations sortable by n-4 passes through a stack

2008/11/30 by Anders Claesson, Claesson, Anders, Mark Dukes +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Biochemical and Structural Characterization #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.0812.0143

openalex publication_date 2008/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We characterise and enumerate permutations that are sortable by n-4 passes through a stack. We conjecture the number of permutations sortable by n-5 passes, and also the form of a formula for the general case n-k, which involves a polynomial expression.

Related

• Passing through a stack k times
• 2-Stack Sorting is polynomial
• Generalizations of two-stack-sortable permutations
• 2-stack sortable permutations with a given number of runs
• Stack words and a bound for 3-stack sortable permutations