Stack-sorting preimages of permutation classes

zbMATH Open1447.05004arXiv1809.03123MaRDI QIDQ2199801FDOQ2199801

Colin Defant

Publication date: 14 September 2020

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

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.

Full work available at URL: https://arxiv.org/abs/1809.03123

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

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

zbMATH Keywords

West's stack-sorting maps

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• Counting 3-stack-sortable permutations
• A lift of West's stack-sorting map to partition diagrams
• Two permutation classes related to the bubble sort operator
• Stack-sortable permutations and beyond
• On partially ordered patterns of length 4 and 5 in permutations
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Stack-sorting with consecutive-pattern-avoiding stacks
• Fertilitopes
• Further bijections to pattern-avoiding valid hook configurations
• Preimages under the Queuesort algorithm
• Preimages under the bubblesort operator
• Troupes, cumulants, and stack-sorting

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)