Enumeration of Stack-Sorting Preimages via a Decomposition Lemma

MaRDI QIDQ5074765zbMATH OpenFDO

Authors Colin Defant

Publication date 10 May 2022

Full work available at URL https://arxiv.org/abs/1904.02829, https://dmtcs.episciences.org/7324

zbMATH Keywords

bubble sortpermutation patternpop-stack-sortingstack-sortingunbalanced Wilf equivalence

Mathematics Subject Classification ID

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

Abstract: We give three applications of a recently-proven "Decomposition Lemma," which allows one to count preimages of certain sets of permutations under West's stack-sorting map $s$. We first enumerate the permutation class $s^{-1}(extAv(231,321))=extAv(2341,3241,45231)$, finding a new example of an unbalanced Wilf equivalence. This result is equivalent to the enumeration of permutations sortable by $$, where $$ is the bubble sort map. We then prove that the sets $s^{-1}(extAv(231,312))$, $s^{-1}(extAv(132,231))=extAv(2341,1342,underline3241,underline3142)$, and $s^{-1}(extAv(132,312))=extAv(1342,3142,3412,34underline21)$ are counted by the so-called "Boolean-Catalan numbers," settling a conjecture of the current author and another conjecture of Hossain. This completes the enumerations of all sets of the form $s^{-1}(extAv(a{u}^{(1)},ldots,a{u}^{(r)}))$ for $a{u}^{(1)},ldots,a{u}^{(r)}subseteq{S}_3$ with the exception of the set $321$. We also find an explicit formula for $|s^{-1}(ext{Av}_{n,k}(231,312,321))|$, where $ext{Av}_{n,k}(231,312,321)$ is the set of permutations in $ext{Av}_n(231,312,321)$ with $k$ descents. This allows us to prove a conjectured identity involving Catalan numbers and order ideals in Young's lattice.

Recommendations

• Stack-sorting preimages of permutation classes
• Stack-sorting, set partitions, and Lassalle's sequence
• Multi-static enumeration of two-stack sortable permutations
• Preimages under the stack-sorting algorithm
• The enumeration of permutations sortable by pop stacks in parallel
• Stack-sortable permutations and beyond
• Stack-sortable permutations and polynomials
• A survey of stack sortable permutations
• Enumeration of decomposable combinatorial structures with restricted patterns
• Enumerating permutations sortable by \(k\) passes through a pop-stack

Cites work

• A combinatorial proof of J. West's conjecture
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• A simplicial complex of 2-stack sortable permutations
• A stack and pop stack in series
• A survey of stack-sorting disciplines
• Actions on permutations and unimodality of descent polynomials
• Catalan intervals and uniquely sorted permutations
• Combinatorics of permutations
• Counting 3-stack-sortable permutations
• Describing West-3-stack-sortable permutations with permutation patterns
• Egge triples and unbalanced Wilf equivalence
• Fertility monotonicity and average complexity of the stack-sorting map
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Fighting fish and two-stack sortable 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?)
• Linear recurrences with constant coefficients: The multivariate case
• Multi-static enumeration of two-stack sortable permutations
• On linear transformations preserving the Pólya frequency property
• On the inverse image of pattern classes under bubble sort
• Passing through a stack \(k\) times with reversals
• Permutations with forbidden subsequences and nonseparable planar maps
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• 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 words and a bound for 3-stack sortable permutations
• Stack-sorting preimages of permutation classes
• Stack-sorting, set partitions, and Lassalle's sequence
• Symmetry and unimodality in \(t\)-stack sortable permutations
• The kernel method for lattice paths below a line of rational slope
• The kernel method: a collection of examples
• Two examples of unbalanced Wilf-equivalence
• Two vignettes on full rook placements

Cited in

(10)

• Preimages under the bubblesort operator
• Stack-sorting preimages of permutation classes
• Counting 3-stack-sortable permutations
• Stack-sortable permutations and beyond
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• A lift of West's stack-sorting map to partition diagrams
• Burstein’s permutation conjecture, Hong and Li’s inversion sequence conjecture and restricted Eulerian distributions
• A new lower bound for deterministic pop-stack-sorting
• Stack-sorting preimages and 0-1-trees
• Boolean-Narayana numbers

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Enumeration of Stack-Sorting Preimages via a Decomposition Lemma

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