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: