Séminaire Lotharingien de Combinatoire, B67d (2012), 20 pp.
Henning Úlfarsson
Describing West-3-Stack-Sortable Permutations with Permutation Patterns
Abstract.
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
Brändén and Claesson (2011), as well as a new type of
generalized pattern we call a decorated pattern.
Received: December 17, 2011.
Revised: February 21, 2012.
Accepted: March 22, 2012.
Final Version: April 11, 2012.
The following versions are available: