Stack words and a bound for 3-stack sortable permutations

2019/03/11 by Bona, Miklos
#05A05 #05A15 #05A16 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1903.04113

Abstract

We use stack words to find a new, simple proof for the best known upper bound for the number of 3-stack sortable permutations of a given length. This is the first time that stack words are used to obtain such a result.

Related

• Permutations sortable by n-4 passes through a stack
• Counting 3-Stack-Sortable Permutations
• 2-stack pushall sortable permutations
• 2-Stack Sorting is polynomial
• Generalizations of two-stack-sortable permutations