Lattice paths and pattern-avoiding uniquely sorted permutations

MaRDI QIDQ5074770zbMATH OpenFDO

Authors Hanna Mularczyk

Publication date 10 May 2022

Full work available at URL https://arxiv.org/abs/1908.04025, https://dmtcs.episciences.org/8403

zbMATH Keywords

lattice pathpermutation patternstack-sortinguniquely sorted permutationvalid hook configuration

Mathematics Subject Classification ID

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

Abstract: Defant, Engen, and Miller defined a permutation to be uniquely sorted if it has exactly one preimage under West's stack-sorting map. We enumerate classes of uniquely sorted permutations that avoid a pattern of length three and a pattern of length four by establishing bijections between these classes and various lattice paths. This allows us to prove nine conjectures of Defant.

Recommendations

• Uniquely sorted permutations
• Catalan intervals and uniquely sorted permutations
• Stack-sorting preimages of permutation classes
• Highly sorted permutations with respect to a 312-avoiding stack
• Sorting and preimages of pattern classes

Cites work

• scientific article; zbMATH DE number 5729471 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• 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 survey of stack-sorting disciplines
• Catalan intervals and uniquely sorted permutations
• Counting 3-stack-sortable permutations
• Descents in t-sorted permutations
• Fertility numbers
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Lattice path enumeration
• Multi-static enumeration of two-stack sortable permutations
• Patterns in permutations and words.
• Preimages under the stack-sorting algorithm
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Sorted and/or sortable permutations
• Stack words and a bound for 3-stack sortable permutations
• Stack-sorting, set partitions, and Lassalle's sequence
• Symmetry and unimodality in \(t\)-stack sortable permutations
• Two integer sequences related to Catalan numbers

Cited in

(14)

• Troupes, cumulants, and stack-sorting
• Catalan intervals and uniquely sorted permutations
• Counting 3-stack-sortable permutations
• Highly sorted permutations and Bell numbers
• Stack-sorting for Coxeter groups
• A distributive lattice structure connecting Dyck paths, noncrossing partitions and 312-avoiding permutations
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Stack-sorting, set partitions, and Lassalle's sequence
• Permutations avoiding 1324 and patterns in Łukasiewicz paths
• Stack-sorting with consecutive-pattern-avoiding stacks
• Fertilitopes
• Uniquely sorted permutations
• Further bijections to pattern-avoiding valid hook configurations
• Unimodality of a refinement of Lassalle's sequence

This page was built for publication: Lattice paths and pattern-avoiding uniquely sorted permutations

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