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

• 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
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• 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₈-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

(23)

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

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)