Describing West-3-stack-sortable permutations with permutation patterns

MaRDI QIDQ715231zbMATH OpenFDO

Authors Henning Úlfarsson

Publication date 2 November 2012

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.1219, http://www.emis.de/journals/SLC/wpapers/s67ulfarss.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bubble-sort operatordecorated pattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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"and'en and Claesson (2011), as well as a new type of generalized pattern we call a decorated pattern.

Recommendations

• Sorting and preimages of pattern classes
• A survey of stack sortable permutations
• Stack-sortable permutations and beyond
• Counting 3-stack-sortable permutations
• Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture

Cited in

(22)

• Counting 3-stack-sortable permutations
• Two first-order logics of permutations
• Preimages under the stack-sorting algorithm
• Highly sorted permutations and Bell numbers
• Sorting and preimages of pattern classes
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Algorithmic coincidence classification of mesh patterns
• Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture
• Stack-sorting for Coxeter groups
• Prism permutations in the Bruhat order
• Polyurethane toggles
• Asymptotics of 3-stack-sortable permutations
• Operators of equivalent sorting power and related Wilf-equivalences
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
• Stack-sortable permutations and beyond
• Stack words and a bound for 3-stack sortable permutations
• Lattice paths and \((n - 2)\)-stack sortable permutations
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Harmonic numbers, Catalan's triangle and mesh patterns

This page was built for publication: Describing West-3-stack-sortable permutations with permutation patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715231)