Describing West-3-stack-sortable permutations with permutation patterns
Séminaire Lotharingien de Combinatoire, Volume 67 (2012), Article B67d
We describe a new method for finding patterns in permutations that produce a
given pattern after the permutation has been passed once through a stack. We
use this method to describe West-3-stack-sortable permutations, that is,
permutations that are sorted by three passes through a stack. We also show how
the method can be applied to the bubble-sort operator. The method requires the
use of mesh patterns, introduced by Branden and Claesson (2011), as well as a
new type of generalized pattern we call a decorated pattern.
Download the paper
Presentations
- A talk given at the Computer and Information Sciences Departmental Seminar at Strathclyde University, October 2011
- A talk given at the ICE-TCS Seminar at Reykjavik University, October 2011
Additional material
Later work (last updated 2 October 2026)
- A. Claesson and H. Úlfarsson, Sorting and preimages of pattern classes, FPSAC 2012. An algorithm that decides when a sorting operator, such as stack-sort, outputs a given pattern; it reproves the description of the West-2-stack-sortable permutations.
- H. Magnusson and H. Úlfarsson, Algorithms for discovering and proving theorems about permutation patterns, preprint (2012). Extends the preimage algorithm to mesh pattern classes, giving a fully automatic proof of the description of the West-3-stack-sortable permutations.
- M. Bouvel and O. Guibert, Refined enumeration of permutations sorted with two stacks and a $D_8$-symmetry, Ann. Comb. 18 (2014). Permutations sorted by two passes through a stack with a symmetry of the square in between; notes that the method of this paper and of Claesson and Úlfarsson’s paper above also applies to these operators, and could give another proof of one of its theorems.
- C. Defant, Counting 3-stack-sortable permutations, J. Combin. Theory Ser. A 172 (2020). A recurrence for the number of West-3-stack-sortable permutations (called 3-stack-sortable there), computing them up to length 174 (13 terms were known before), and the first nontrivial lower bound on their growth rate.
- M. Bóna, Stack words and a bound for 3-stack sortable permutations, Discrete Appl. Math. 284 (2020). A new, simple proof of the best known upper bound for the number of West-3-stack-sortable permutations.
- C. Defant, A. Price and A. J. Guttmann, Asymptotics of 3-stack-sortable permutations, Electron. J. Combin. 28 (2021). A functional equation for the generating function of the West-3-stack-sortable permutations, 1000 terms of the series, and an estimate of their growth rate, about 9.6996.
- B. E. Tenner, Prism permutations in the Bruhat order, Adv. Appl. Math. 159 (2024). Introduces calibrated patterns, which fit the suggestion made here of attaching rules, such as “must avoid 321”, to the cells of a mesh pattern.
- All citing papers on Google Scholar (45)