Stack-sorting preimages of permutation classes

MaRDI QIDQ2199801zbMATH OpenFDO

Authors Colin Defant

Publication date 14 September 2020

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

Full work available at URL https://arxiv.org/abs/1809.03123, http://www.mat.univie.ac.at/~slc/wpapers/s82defant.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

West's stack-sorting maps

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: We extend and generalize many of the enumerative results concerning West's stack-sorting map $s$. First, we prove a useful theorem that allows one to efficiently compute $|s^{-1}(pi)|$ for any permutation $pi$, answering a question of Bousquet-M'elou. We then enumerate permutations in various sets of the form $s^{-1}(extAv(a{u}^{(1)},ldots,a{u}^{(r)}))$, where $extAv(a{u}^{(1)},ldots,a{u}^{(r)})$ is the set of permutations avoiding the patterns $a{u}^{(1)},ldots,a{u}^{(r)}$. These preimage sets often turn out to be permutation classes themselves, so the current paper represents a new approach, based on the theory of valid hook configurations, for solving classical enumerative problems. In one case, we solve a problem previously posed by Bruner. We are often able to refine our counts by enumerating these permutations according to their number of descents or peaks. Our investigation not only provides several new combinatorial interpretations and identities involving known sequences, but also paves the way for several new enumerative problems.

Recommendations

• Stack-sortable permutations and beyond
• A survey of stack sortable permutations
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Preimages under the stack-sorting algorithm
• Stack-sortable permutations and polynomials
• Sorting and preimages of pattern classes
• Multi-static enumeration of two-stack sortable permutations
• Generalized Stack Permutations
• Permutations sortable by deques and by two stacks in parallel
• Permutations generated by stacks and deques

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• A combinatorial proof of J. West's conjecture
• A simplicial complex of 2-stack sortable permutations
• A survey of stack-sorting disciplines
• A survey of the Fine numbers
• Algebraic Combinatorics
• Combinatorics of permutations
• Counting Walks in the Quarter Plane
• Fighting fish
• Fighting fish and two-stack sortable permutations
• Forest-like permutations
• Generalized permutation patterns -- a short survey
• Generalized permutation patterns and a classification of the Mahonian statistics
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• Multi-static enumeration of two-stack sortable permutations
• On linear transformations preserving the Pólya frequency property
• Pattern avoidance in \(k\)-ary heaps
• Pattern avoidance in extensions of comb-like posets
• Patterns in permutations and words.
• Permutations with forbidden subsequences and a generalized Schröder number
• Permutations with forbidden subsequences and nonseparable planar maps
• Permuting machines and permutation patterns
• Poset pattern-avoidance problems posed by Yakoubov
• Postorder Preimages
• Preimages under the stack-sorting algorithm
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry
• Sorted and/or sortable permutations
• Sorting and preimages of pattern classes
• Stack-sorting, set partitions, and Lassalle's sequence
• Staircases, dominoes, and the growth rate of 1324-avoiders
• Symmetry and unimodality in \(t\)-stack sortable permutations
• The descent statistic on 123-avoiding permutations
• Two integer sequences related to Catalan numbers
• Unimodality, log-concavity, real-rootedness and beyond

Cited in

(19)

• A lift of West's stack-sorting map to partition diagrams
• Stack-sorting, set partitions, and Lassalle's sequence
• Sorting and preimages of pattern classes
• On partially ordered patterns of length 4 and 5 in permutations
• Stack-sortable permutations and beyond
• Preimages under the stack-sorting algorithm
• Further bijections to pattern-avoiding valid hook configurations
• Preimages under the Queuesort algorithm
• Restricted stacks as functions
• Preimages under the bubblesort operator
• Troupes, cumulants, and stack-sorting
• Fertilitopes
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Counting 3-stack-sortable permutations
• Uniquely sorted permutations
• Two permutation classes related to the bubble sort operator
• Highly sorted permutations and Bell numbers
• Stack-sorting with consecutive-pattern-avoiding stacks
• Lattice paths and pattern-avoiding uniquely sorted permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Stack-sorting preimages of permutation classes

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